大家看看我写的约瑟夫环(O(N))算法有没有问题

谢谢ansjsun和xlaohe1的回复，让我找到了自己程序的错误。虽然自己思路正确，但是一行代码写错，等于白搭，我要多加练习

这个游戏相当于：每一轮干掉一个人之后，由这个位置开始重新编号：这个人的下一个变成0号，下下个变成1号，依次类推，被干掉的人前一个则变成了n-2号（别忘了是个环）。然后由新的0号开始再进行下一轮报数。 由于涉及取模，我们先把编号改为从0开始。

在任一轮中，随便选定一个人，他在本轮的号码是x。这说明他距离上次被干掉的人距离是x + 1。假定当前剩下n'个人，那么之前被干掉的人在上一轮的号码就应该是m % n - 1 （别忘了从0号开始），其中n = n' + 1。因此现在选定这个人在上一轮的号码应该是 [(m % n) - 1 + (x + 1)] % n = [（m - 1 + x + 1)] % n = (m + x) % n。

现在，用F(n)来表示某个人在某一轮的位置，那么上面的x就是F(n') = F(n-1)，代入可得F(n) = (F(n - 1) + m) % n。你想知道第k轮被干掉的人在最开始的位置，就让F(r) = m % r 作为边界条件。其中r = N - k + 1, N是最开始的人数。例如说N是20，你要知道在第3轮被干掉的人的序号，就用F(18) = m % 18来做递归边界。你要知道留到最后的人（也就是在第N轮才被干掉的人），就用F(1) = m % 1 = 0来做边界条件。

实际实现时，不需要用递归，从边界条件开始倒过来递推就行了。

O（1）时间搞定的问题

我不信。除非你已经把结果都生成好了

是可以查表的

上代码