c - 谜题:谁赢得了比赛？

Question

一群 child 围成一圈。选择第一个 child ，他们从那个 child 开始顺时针计数，直到达到固定数字(n，在游戏开始时给出)。当计数达到 n 时，第 n 个位置的 child 被淘汰。游戏从下一个 child 开始再次继续，这个过程一直持续到剩下一个 child 。你的目标是打印剩下的 child 的位置。

For example, if there are 10 children and the fixed number n is 6, the position of the last child who remains till the last is 3.

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

P.S. I know that we can easily do this using arrays or other data structures. I just want the best strategy, preferably a mathematical approach.

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 个 child 开始，哪个 child 会赢”。

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

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