一种基于向量旋转的Josephus问题的新解法

A New Solution for Josephus Problem Based on Vector Rotation

文章针对数据结构中经典的Josephus问题,提出了一种基于向量旋转(rotate)算法的Josephus问题的新解法.这种解法通过不断对存储初始编号序列的一维向量进行旋转操作,可以不必开辟辅助存储空间,就地将初始编号序列逐步转换为出队编号序列,每次旋转操作在序列的首端产生一个出队编号,余下的序列继续旋转,如此不断进行直到最后只剩一个编号.进一步的算法复杂度理论分析表明,这种新解法的时间复杂度为O(n2),空间复杂度为O(1)。最后利用C++STL标准模板库提供的rotate库函数,给出了新解法的一个简洁的C++代码实现.新解法利用旋转算法将有限长的一维向量作为逻辑上的环来操作,通过旋转不断缩小的环来逐步求解,算法思想直观易懂,而且便于利用标准库提供的旋转算法函数模板来具体实现,在Josephus问题的进一步应用研究及数据结构和算法分析的教学上均有一定价值.

Based on vector rotation algorithm a new solution to the classic Josephus problem is provided.Firstly,sorted initial numbers are stored in a one-dimension vector.Then the vector is rotated by an operation called ring shift left.After the rotation,the number which should leave now is right on the first place of the vector.The next leaving number is revealed by the same rotation applied on the vector constructed by the remaining numbers.Step by step,the initial vector is transformed to the result vector.By further analysis,it is showed that the time complexity of this solution is O(n2)and the space complexity is O(1).Lastly,based on the rotate function provided by the C++STL(standard template library),a concise C++code of this new solution is provided.