跳到主要内容

约瑟夫环

转载自：约瑟夫环——公式法（递推公式）

什么是约瑟夫环？​

约瑟夫问题是个著名的问题：N 个人围成一圈，第一个人从 1 开始报数，报 M 的将被杀掉，下一个人接着从 1 开始报。如此反复，最后剩下一个，求最后的胜利者。

例如只有三个人，把他们叫做 A、B、C 他们围成一圈，从 A 开始报数，假设报 2 的人被杀掉。

  • 首先 A 开始报数，他报 1。侥幸逃过一劫。
  • 然后轮到 B 报数，他报 2。非常惨，他被杀了
  • C 接着从 1 开始报数
  • 接着轮到 A 报数，他报 2。也被杀死了。
  • 最终胜利者是 C

普通解法​

刚学数据结构的时候，我们可能用链表的方法去模拟这个过程，N 个人看作是 N 个链表节点，节点 1 指向节点 2，节点 2 指向节点 3，……，节点 N-1 指向节点 N，节点 N 指向节点 1，这样就形成了一个环。

然后从节点 1 开始 1、2、3…… 往下报数，每报到 M，就把那个节点从环上删除。下一个节点接着从 1 开始报数。最终链表仅剩一个节点。它就是最终的胜利者。

缺点：

要模拟整个游戏过程，时间复杂度高达 O(n∗m)O(n * m) ,当 n，m 非常大（例如上百万，上千万）的时候，几乎是没有办法在短时间内出结果的。

公式法​

约瑟夫环是一个经典的数学问题，我们不难发现这样的依次报数，似乎有规律可循。为了方便导出递推式，我们重新定义一下题目。

问题： N个人编号为1，2，……，N，依次报数，每报到M时，杀掉那个人，求最后胜利者的编号。

这边我们先把结论抛出了。之后带领大家一步一步的理解这个公式是什么来的。

f(N,M)=(f(N−1,M)+M)%Nf(N,M)=(f(N−1,M)+M)\%N

f(N,M)f ( N , M ) 表示，N 个人报数，每报到 M 时杀掉那个人，最终胜利者的编号 f(N−1,M)f ( N − 1 , M ) 表示，N -1 个人报数，每报到 M 时杀掉那个人，最终胜利者的编号

下面我们不用字母表示每一个人，而用数字。

1、2、3、4、5、6、7、8、9、10、11

表示 11 个人，他们先排成一排，假设每报到 3 的人被杀掉。

  • 刚开始时，头一个人编号是 1，从他开始报数，第一轮被杀掉的是编号 3 的人。
  • 编号 4 的人从 1 开始重新报数，这时候我们可以认为编号 4 这个人是队伍的头。第二轮被杀掉的是编号 6 的人。
  • 编号 7 的人开始重新报数，这时候我们可以认为编号 7 这个人是队伍的头。第三轮被杀掉的是编号 9 的人。
  • ……
  • 第九轮时，编号 2 的人开始重新报数，这时候我们可以认为编号 2 这个人是队伍的头。这轮被杀掉的是编号 8 的人。
  • 下一个人还是编号为 2 的人，他从 1 开始报数，不幸的是他在这轮被杀掉了。
  • 最后的胜利者是编号为 7 的人。

下图表示这一过程（先忽视绿色的一行）

现在再来看我们递推公式是怎么得到的！

将上面表格的每一行看成数组，这个公式描述的是：幸存者在这一轮的下标位置

f(1,3)f(1,3)：只有 1 个人了，那个人就是获胜者，他的下标位置是 0 f(2,3)=(f(1,3)+3)%2=3%2=1f ( 2 , 3 ) = ( f ( 1 , 3 ) + 3 ) \% 2 = 3 \% 2 = 1：在有2个人的时候，胜利者的下标位置为1 f(3,3)=(f(2,3)+3)%3=4%3=1f ( 3 , 3 ) = ( f ( 2 , 3 ) + 3 ) \% 3 = 4 \% 3 = 1：在有3个人的时候，胜利者的下标位置为1 f(4,3)=(f(3,3)+3)%4=4%4=0f ( 4 , 3 ) = ( f ( 3 , 3 ) + 3 ) \% 4 = 4 \% 4 = 0：在有4个人的时候，胜利者的下标位置为0 …… f(11,3)=6f ( 11 , 3 ) = 6

很神奇吧！现在你还怀疑这个公式的正确性吗？上面这个例子验证了这个递推公式的确可以计算出胜利者的下标，下面将讲解怎么推导这个公式。

问题1： 假设我们已经知道 11 个人时，胜利者的下标位置为 6。那下一轮 10 个人时，胜利者的下标位置为多少？

答： 其实吧，第一轮删掉编号为 3 的人后，之后的人都往前面移动了 3 位，胜利这也往前移动了 3 位，所以他的下标位置由 6 变成 3。

问题2： 假设我们已经知道 10 个人时，胜利者的下标位置为 3。那下一轮 11 个人时，胜利者的下标位置为多少？

答： 这可以看错是上一个问题的逆过程，大家都往后移动 3 位，所以 f(11,3)=f(10,3)+3f ( 11 , 3 ) = f ( 10 , 3 ) + 3 。不过有可能数组会越界，所以最后模上当前人数的个数, f(11,3)=(f(10,3)+3)%11f ( 11 , 3 ) = (f ( 10 , 3 ) + 3) \% 11

问题3： 现在改为人数改为 N，报到 M 时，把那个人杀掉，那么数组是怎么移动的？

答： 每杀掉一个人，下一个人成为头，相当于把数组向前移动 M 位。若已知 N-1 个人时，胜利者的下标位置位 f(N−1,M)f ( N − 1 , M ) ,则 N 个人的时候，就是往后移动 M 位，因为有可能数组越界，超过的部分会被接到头上，所以还要模 N，既 f(N,M)=(f(N−1,M)+M)%nf ( N , M ) = ( f ( N − 1 , M ) + M ) \% n

注： 理解这个递推式的核心在于关注胜利者的下标位置是怎么变的。每杀掉一个人，其实就是把这个数组向前移动了 M 位。然后逆过来，就可以得到这个递推式。

因为求出的结果是数组中的下标，最终的编号还要加 1

下面给出代码实现：

int cir(int n, int m) {
    int p = 0;
    // 这里其实是一个逆推的过程，i 可以看作是人数
    for (int i = 2; i <= n; i++) {
        p = (p + m) % i;
    }
    return p + 1;
}