c++ - 约瑟夫斯算法

我正在阅读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

有人能举例说明吗？

最佳答案

如果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;
}

第一个人（从一开始就是第十个人）被杀后，剩下n-1个人所以我们打电话给josephus(n – 1, k)来得到有n-1人的位置。
但是josephus(n – 1, k)返回的位置将从位置1再次考虑它。因此，我们在它上面加上k-1，取它的模量，因为有n元素，加上1使位置n，而不是1-indexed。
参考：http://www.geeksforgeeks.org/josephus-problem-set-1-a-on-solution/