c++ - 约瑟夫斯算法

Question

我正在阅读约瑟夫斯问题的算法。

我遇到了以下算法：

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/