Josephus算法

Question

我在读Josephus Problem的算法。

我遇到了以下算法：

int josephusIteration(int n,int k) {
    int a=1;
    for(int i=1;i<=n;i++) {
        a=(a+k-1)%i+1;
    }
    return a;
}

我不能理解它的逻辑。假设n=5和k=2。

i=1, a=1
i=2, a=1
i=3, a=3
i=4, a=1
i=5, a=3

有没有人能举个例子来解释一下？

Answer 1

如果为n = 5和k = 2，则安全位置为3。首先，杀死位置2的人，然后杀死位置4的人，然后杀死位置1的人。最后，位置5的人被杀死。所以位置3的人幸免于难。

我已经读过你的代码，但我想在下面建议一个更容易理解的递归解决方案。

// this function returns the position of the person alive
int josephus(int n, int k)
{
  if (n == 1)
    return 1;
  else
    /* The position returned by josephus(n - 1, k) is adjusted because the
       recursive call josephus(n - 1, k) considers the original position 
       k%n + 1 as position 1 */
    return (josephus(n - 1, k) + k-1) % n + 1;
}

在第一个人(从一开始就是第k个)被杀后，剩下n-1个人。因此，我们调用josephus(n – 1, k)来获得n-1个人的职位。

但josephus(n – 1, k)返回的位置将从位置1再次考虑。因此，我们将k-1添加到该位置，并将其模取为n，因为存在n元素，并添加1以使位置为1-indexed而不是0-indexed。

参考：http://www.geeksforgeeks.org/josephus-problem-set-1-a-on-solution/