残酷的死亡游戏之约瑟夫问题，解法有特色，收获不一般
老张教育新思享2019-10-03 12:17
你好，今天我们一来了解闻名世界的“约瑟夫问题”，探索其间的数学奥秘吧！
1.约瑟夫问题与因式分解
约瑟夫问题又叫约瑟夫环或丢手绢问题。故事据说发生在古罗马时期，在罗马人占领乔塔帕特后，39个犹太人与Josephus及他的朋友躲到一个洞中，他们宁愿死也不要被敌人抓到，于是约定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下1个人重新报数，直到所有人都自杀身亡为止。但是Josephus和他的朋友并不想遵从，就开始想一开始要站在什么地方才能避免被处决。
Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。（图中内圈为排列顺序，外圈为自杀顺序）最后就剩下Josephus和他的朋友，也就不会再自杀了。
另一个版本是这样说的：约瑟夫斯问题是个蛮好玩的问题。这个问题来源于一个犹太叛徒，约瑟夫斯是犹太人，参与了对罗马的起义，并被任命为起义部队的军事长官。不过在后来罗马军团的进攻下，犹太人的起义很快失败了，约瑟夫斯带领这39名犹太士兵躲到了一个山洞中，山洞则被罗马人包围。士兵们坚贞不屈，宁可死也不肯投降，然而约瑟夫斯不想死，又不敢说出来。于是约瑟夫斯利用了犹太教中关于自杀耻辱的教义，说咱们不能自杀，咱们可以互相杀，怎么互相杀，谁来杀呢？
这样40人围成一圈，然后连续1,2,1,2……报数，所有报2的被同伴杀死，直到最后一个，最后一个自杀者承担教义中自杀的耻辱。约瑟夫斯是个数学家，他当然很快就知道自己应该站在哪个位置而不会被杀死。当所有人都被杀死后，他走出山洞，投降了罗马人。
2. 加帕斯的问题
17世纪的法国数学家加帕斯也讲过这样一个故事，15个教徒和15个非教徒在深海上遇险，只有将一半的人扔入海中，其余的人才能幸免于难，于是他们想到一个办法，30个人围成一个圆圈，从第一个人开始依次报数，每数到第九个人就将他扔入大海，如此循环进行直到仅余15个人为止。如何才能把非教徒都扔入大海呢？
其实这些都是约瑟夫问题，看似好像很难去判断，其实解决它的方法有很多。
3. 如何找到“约瑟夫”
假设有64名同学站成一个圆圈，按顺时针方向编号：1~64，现在从1号开始，按“1、2、1、2、1、2…”的方式报数，报到1的同学立即离开，不再参与。到最后只剩一个同学时报数停止，这个人就是约瑟夫。请问约瑟夫是多少号？
由于第一圈剩下的全部是偶数号2，4，6，8，……64。把它们全部用2除，得1，2，3，4，……32．这是第二圈重新编的号码。第二圈杀过之后，又把奇数号码都杀掉了，还剩下16个人。如此下去，可以想到最后剩下的必然是64号。 64＝2×2×2×2×2×2，它可以连续被2整除6次，是从1到64中质因数里2最多的数，因此，最后必然把64号剩下。从64＝2×2×2×2×2×2还可以看到，
因为它可以连续被2整除6次，是从1到64中能被2整除次数最多的数，因此最后必然把64号留下。
我们将约瑟夫问题拓展一下：
1、队列法：
n个人站一队列，一个一个开始，从1到k循环报数，报数为1到k-1的人重新站到队伍后面，报数为k的人淘汰。
2、列表法：
n个人站一队，每次循环淘汰掉队中接着上次报数开始的报数为k的人。这个方法需要记录每轮队伍报数完毕的最后一个数字。
3、循环链表法：
编号为 1-N 的 N 个士兵围坐在一起形成一个圆圈，从编号为 1 的士兵开始依次报数（1，2，3…这样依次报），数到 m 的 士兵会被杀死出列，之后的士兵再从 1 开始报数。直到最后剩下一士兵，求这个士兵的编号。
针对拓展问题3我们可以这样去做：
方法一：数组
在大一第一次遇到这个题的时候，我是用数组做的，我猜绝大多数人也都知道怎么做。方法是这样的：用一个数组来存放 1，2，3 … n 这 n 个编号，如图（这里我们假设n = 6, m = 3），
然后不停着遍历数组，对于被选中的编号，我们就做一个标记，例如编号 arr[2] = 3 被选中了，那么我们可以做一个标记，例如让 arr[2] = -1，来表示 arr[2] 存放的编号已经出局的了。
然后就按照这种方法，不停着遍历数组，不停着做标记，直到数组中只有一个元素是非 -1 的，这样，剩下的那个元素就是我们要找的元素了。我演示一下吧：
这种方法简单吗？思路简单，但是编码却没那么简单，临界条件特别多，每次遍历到数组最后一个元素的时候，还得重新设置下标为 0，并且遍历的时候还得判断该元素时候是否是 -1。感兴趣的可以动手写一下代码，用这种数组的方式做，千万不要觉得很简单，编码这个过程还是挺考验人的。这种做法的时间复杂度是 O(n * m), 空间复杂度是 O(n);
方法二：环形链表
学过链表的人，估计都会用链表来处理约瑟夫环问题，用链表来处理其实和上面处理的思路差不多，只是用链表来处理的时候，对于被选中的编号，不再是做标记，而是直接移除，因为从链表移除一个元素的时间复杂度很低，为 O(1)。当然，上面数组的方法你也可以采用移除的方式，不过数组移除的时间复杂度为 O(n)。所以采用链表的解决方法如下：
1、 先创建一个环形链表来存放元素：
2、然后一边遍历链表一遍删除，直到链表只剩下一个节点，我这里就不全部演示了
代码及核心代码这里图略，这种方法估计是最多人用的，时间复杂度为 O(n * m),空间复杂度是 O(n)。还有更好的方法吗？答有，请往下看
方法三：递归
其实这道题还可以用递归来解决，递归是思路是每次我们删除了某一个士兵之后，我们就对这些士兵重新编号，然后我们的难点就是找出删除前和删除后士兵编号的映射关系。
我们定义递归函数 f(n，m) 的返回结果是存活士兵的编号，显然当 n = 1 时，f(n, m) = 1。假如我们能够找出 f(n，m) 和 f(n-1，m) 之间的关系的话，我们就可以用递归的方式来解决了。我们假设人员数为 n, 报数到 m 的人就自杀。则刚开始的编号为1，m – 2，m – 1，m，m + 1，m + 2，…，n…
进行了一次删除之后，删除了编号为 m 的节点。删除之后，就只剩下 n - 1 个节点了，删除前和删除之后的编号转换关系为：
删除前 --- 删除后
… --- …
m - 2 --- n - 2
m - 1 --- n - 1
m ---- 无(因为编号被删除了)
m + 1 --- 1(因为下次就从这里报数了)
m + 2 ---- 2
… ---- …
新的环中只有 n - 1 个节点。且删除前编号为 m + 1, m + 2, m + 3 的节点成了删除后编号为 1， 2， 3 的节点。
假设 old 为删除之前的节点编号， new 为删除了一个节点之后的编号，则 old 与 new 之间的关系为 old = (new + m - 1) % n + 1。
这样，我们就得出 f(n, m) 与 f(n - 1, m)之间的关系了，而 f(1, m) = 1.所以我们可以采用递归的方式来做。代码这里略去了。
其实这些都是约瑟夫问题，看似好像很难去判断，其实解决它的方法有很多，期待你的留言讨论。
举报/反馈
0
0
收藏
分享
