A New Solution for Josephus Problem Based on Vector Rotation
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.
万方数据
维普
