c - 谜题：谁赢了比赛？

Question

一群孩子围成一圈。第一个孩子被选中，他们从那个孩子开始顺时针计数，直到达到一个固定的数字（n，在游戏开始时给出）。当计数达到 n 时，第 n 个位置的孩子被淘汰。游戏从下一个孩子开始再次继续，直到剩下一个孩子。您的目标是打印直到最后一个孩子的位置。

例如，如果有 10 个孩子，固定数 n 为 6，那么最后一个孩子的位置是 3。

有没有更好的编程算法来解决这个问题？

PS 我知道我们可以使用数组或其他数据结构轻松地做到这一点。我只想要最好的策略，最好是数学方法。

Answer 1

我认为最简单的方法仍然是写一个重复（几乎是维基百科所说的，给 Jan Dvorak 投票）：

T(1) = 0
T(c) = (T(c-1)+n) mod c

或者，写成 C（没有递归）：

int non_fatal_josephus(int children, int n) {
    int result = 0;
    for(int i=2; i<=children; i++)
        result = (result + n) % i;

    return result + 1; //to make it one-based
}

复发解释：

T(c) 的意思是“如果我们从 c 个孩子开始，哪个孩子会赢”。

T(1) = 0 因为如果我们只有 1 个孩子，她已经赢了（第 1 个孩子，索引 0）。

一般情况是我们总是消除第n个孩子（索引n-1），一旦我们消除了她，我们就重新开始计数（c-1）个孩子，但这一次，我们不是从索引0开始，而是从索引 n。这解释了 +n：T(c-1) 假设计数从 0 开始。我们使用 +n 来移动子索引，就好像我们从索引 n 开始一样。