约瑟夫问题


约瑟夫问题

前言

约瑟夫问题是个著名的问题: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(nm)$ ,当 n 、m 非常大(例如上百万,上千万)的时候,几乎是没有办法在短时间内出结果的。

公式法

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

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

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

递推公式:
$$
f(N,M)=(f(N−1,M)+M)\%N
$$
$f(N,M)$ 表示,$N$ 个人报数,每报到 $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 的人从 1 开始重新报数,这时候我们可以认为编号 7 这个人是队伍的头。第三轮被杀掉的是编号 9 的人。

……

第九轮时,编号 2 的人从 1 开始重新报数,这时候我们可以认为编号 2 这个人是队伍的头。这轮被杀掉的是编号 8 的人。

下一个人还是编号为 2 的人,他从 1 开始报数,不幸的是他在这轮被杀掉了。

最后的胜利者是编号为 7 的人。

下图表示这一过程(先忽视绿色的一行)。

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

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

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

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

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

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

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

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

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

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

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

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

下面给出代码实现:

public int cir(int n, int m) {
    int p=0;
    for(int i=2;i<=n;i++)
    {
        p=(p+m)%i;
    }
    return p+1;
}

文章作者: wenjun
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 wenjun !
评论
 上一篇
Spring AOP Spring AOP
Spring AOP基本概念什么是 AOP ? AOP 是 Aspect Oriented Programming(面向切面编程) 的简称,和 OOP(面向对象编程)一样是一种编程思想,是对 OOP 的一种补充。 AOP 旨在将横切关注点
2020-05-25
下一篇 
蓄水池采样算法 蓄水池采样算法
蓄水池采样算法问题描述分析采样问题经常会被遇到,比如: 从 100000 份调查报告中抽取 1000 份进行统计。 从一本很厚的电话簿中抽取 1000 人进行姓氏统计。 从 Google 搜索 “Ken Thompson” ,从中抽取 1
2020-05-19
  目录