黑马程序员技术交流社区

标题: 约瑟夫环问题全攻略 [打印本页]
作者: fantacyleo    时间: 2014-9-20 16:21
标题: 约瑟夫环问题全攻略
本帖最后由 fantacyleo 于 2014-9-20 16:24 编辑
已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列。他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌上只剩下一个人，请输出最后剩下的这个人在原先n个人中的编号

因为是入学基础测试题库中的题目，这道题在黑马论坛上可谓经久不衰，隔三差五便能看到相关帖子。追根溯源，这个问题出现在公元1世纪，以犹太历史学家Josephus（约瑟夫）命名，称为”约瑟夫环问题“。

话说当年Josephus和他手下的40名士兵在Yodfat（在今以色列）被罗马军队包围，他们决定宁死不降。这41个人围坐成一圈，由某个人开始数1，紧挨他右边的人数2。。。数到3的人就自杀，然后下一个人重新从1开始数。Josephus幸运地（或有预谋地？）成了最后剩下的人，随后他向罗马人投降。后人将约瑟夫记载的这个情节转化为数学问题，这就是我们现在看到的”约瑟夫环问题”。为了讨论方便，我们以n=5, m = 3为例。

第一个出局的是3号。接下来4号又从1开始报数，显然此时问题转化为n=4, m=3的约瑟夫环问题。学过算法的同学应该一眼就看出这里有递归模式：问题结构相同，但规模缩小了。如果看不出来递归也不要紧，有个“笨”办法可以用，那就是一轮一轮地模拟报数和出局过程，直至剩下最后一人。模拟的关键在于用什么样的数据结构表示n个人。主要有两种思路：数组模拟和链表模拟

数组模拟就是用int[] people = new int[n]; 来代表n个人。由于Java中数组一经定义其长度就无法改变，因而难以通过删除元素来模拟”出局“（不是完全不可以，比如通过移动数组元素来模拟出局，但很麻烦，毕竟增删是数组结构的弱项）。解决方法是通过不同的值来区分是否留在场上，比如1表示在场，0表示已出局。这样，一开始people[j](0 <= j <= 4)都为1。设置一个计数变量count，外加一个remaining变量表示剩下的人数（初始化为5），一轮一轮地遍历people数组：如果people[j]＝1，count++，否则跳过，count不变。count到3就将对应的people置为0，count也重置为0，remaining--。当remaining＝1时，数组中那个＝1的下标就是题目所求的编号。

链表模拟和数组模拟思路差不多，但利用了链表可增删方便的特点，可以将出局者直接删除，避免了数组思路中每轮都要遍历n个人的效率损失。但是从算法的角度来说，链表模拟和数组模拟耗费的时间是同一数量级的，都是O(mn)。JDK API中，LinkedList可作为链表使用，可定义LinkedList<Integer> people = new LinkedList<Integer>(); 将1－5存入people链表，和数组模拟类似地操作，但对报到3的链表元素加以删除。当链表的size为1时，那个剩下的元素即为所求编号。

模拟的思路很直观，用来应付入学考试是完全ok的，也能帮大家复习数组和集合的基本操作。不过正如上一段所说，模拟的效率不太高，渐近时间复杂度是O(mn)；而且当n很大时，还有不小的内存空间开销。要想提高算法的时间和空间效率，我们还是回到之前提过的”不太直观“的递归模式：n=5, m = 3时。第一个出局的是3号。接下来4号又从1开始报数，此时问题转化为n=4, m=3的约瑟夫环问题。而当剩下一个人时，我们就可以不用再递归，问题也解决了。据此，我们马上可以写出如下递归代码：
  1. public int josephusRing(int n, int m) {
  2.     if (n == 1)
  3.         return 1;
  4.     else
  5.         return josephusRing(n - 1, m);
  6. }
复制代码

这段代码比模拟解法的时间效率要高，仅为O(n)。不幸的是，这段代码是错误的，因为题目要求输出最后剩下的那个人在原先n个人中的编号，而这段代码永远只能返回1。尽管我们知道最后剩下的那个人一定是最后一轮的”1号“，但却未必是原先n个人中的”1号“。这就引出了约瑟夫环问题中最核心也最费脑子的部分：最后剩下的”1号“在原先n个人中是几号呢？显然，除非你是天才，要想一眼看出这个对应关系是不可能的。而递归的一个好处就是不需要你一眼看出这么大跨度的关系，只需要搞清楚 josephusRing(n, m)和 josephusRing(n-1, m)之间的关系即可。

首先我们要知道，给定n和m的约瑟夫环问题，第一个出局的是几号。大家可能会脱口而出"m号"，但如果n < m呢？比如n=2, m = 3，显然出局的就不是3号，而是1号（1号报1，2号报2，1号报3）。n < m时，我们数到n后接下来又要回到1号继续数n+1，也就是要数多圈，最后数到m的应该是m % n号。而当n > m时，我们数到m就用不了一圈，此时”出局者是m % n号“仍然成立。当n=m时，出局者也是m号，但m % n = 0，不能正确给出出局者的编号。因此我们暂且分两种情况：n=m时，第一个出局的是m号，否则第一个出局的是m % n号

知道了第一个出局的是m % n号，新一轮n-1和m的约瑟夫环问题中的1号是原先n个人中的几号就不难回答了。当n=m时，新一轮的1号就是原先的1号，当n≠m时，新一轮的1号是原先的（m % n） + 1号。这里我们发现，当m=n时，(m % n)尽管无法给出正确的出局者编号，但 m % n + 1却给出了正确的新一轮的１号在原先ｎ个人中的编号，因此之前分的两种情况可以合并为一种：给定n和m的约瑟夫环问题，当第一个人出局后形成的新一轮n-1和m的约瑟夫环问题中的1号是原先n个人中的ｍ % n + 1号。

确定了新一轮的１号，其他号顺推就可以了。比如新一轮的２号是原先的 m % n + ２号。。。新一轮的ｋ号是原先的 m % n + ｋ号。如果我们从ｎ个人围成的圆圈来看，新一轮约瑟夫环问题相当于把圆圈顺时针旋转，将原先的１号转到原先的m % n + 1号位置。要注意的是，m % n + ｋ可能会大于ｎ。比如说ｎ＝５，ｍ＝３时，第一个出局的是３号，接下来4号又从1开始报数，此时剩下的4个人的编号和它们在n=5时的编号对应关系如下：
              
n=4时的编号
   n＝5时的编号
1
4
2
5
3
1
4
2

从上表可知，当ｋ＝３时，ｍ % n + k＝６ > 5，这时相当于转过了一圈，要重新从１开始数，因此当ｍ % n + k > n时，我们要将它对ｎ取模，即(ｍ % n + k) % n。所以最后得到结论：m % n + k 小于等于ｎ时，新一轮n-1和m的约瑟夫环问题中的ｋ号是原先n个人中的(m % n + k)  号；m % n + k 大于ｎ时，新一轮n-1和m的约瑟夫环问题中的ｋ号是原先n个人中的(m % n + k) % n号。有了这个递推公式，加上已知 最后一轮剩下的一定是１号, 我们可以改写之前的递归代码：
  1. public int josephusRing(int n, int m) {
  2.     if (n == 1)
  3.         return 1;
  4.     else {
  5.         int k = josephusRing(n - 1, m);
  6.         return (k + m % n) > n ? (k + m % n) % n : k + m % n;
  7.     }
  8. }
复制代码

现在的递归代码在逻辑上是正确的。但是，n稍微取大一点就会出现栈溢出，我在JDK 1.7上测试发现n＝10000时已然溢出。大家如果在java上用递归算过前n个数的和会发现n＝7000也足以产生溢出了。为了让代码能够处理更大的n，我们需要手动进行优化。

像上面这样递归出现在函数最后一条语句的递归叫作”尾递归“，尾递归的一个重要特性是它可以写成一个等价的循环版本，从而消除递归，避免了栈溢出。函数式编程语言如Lisp、scheme都包含对尾递归的优化，让程序员可以用递归更加清晰自然地表达算法又不失运行时的效率。遗憾的是，像Java这样的命令式语言通常对尾递归没有进行优化，你写递归，它就老老实实按递归执行，栈溢出在所难免。我们需要手动将递归改写为循环。改写的思路是：递归的终结条件(本题中是n==1)作为循环的初始条件，递归的递归部分(本题中的else语句块)作为循环体。
  1. public int josephusRing(int n, int m) {
  2.     int k = 1;
  3.     for (int i = 2; i <= n; i++) {
  4.         k = (k + m % i) > i ? (k + m % i) % i : k + m % i;
  5.     }
  6.    return k;
  7. }
复制代码
作者: JerryJava    时间: 2014-9-20 16:23
真心感谢你！！ 请问你是已经录取了还是正在备战？ 能否交个朋友～
作者: fantacyleo    时间: 2014-9-20 16:23
占楼备用^_^
作者: fantacyleo    时间: 2014-9-20 16:37
本帖最后由 fantacyleo 于 2014-9-20 16:41 编辑
JerryJava 发表于 2014-9-20 16:23
真心感谢你！！ 请问你是已经录取了还是正在备战？ 能否交个朋友～

还在备战中。 我现在很少上qq，你可以到微博上找我
                                                http://weibo.com/u/3180577330
，或者发邮件fantacyleo@hotmail.com
作者: JerryJava    时间: 2014-9-20 16:41
fantacyleo 发表于 2014-9-20 16:37
还在备战中。

我觉得你可以拿到满分～ 重要的你的表达和推理都太完美了～佩服+膜拜。
作者: JerryJava    时间: 2014-9-20 16:42
fantacyleo 发表于 2014-9-20 16:37
还在备战中。 我现在很少上qq，你可以到微博上找我
                                                http://weibo.com/u/3180577330
，或者发邮件

一样，我几乎不用qq，邮箱联系！最后决定报哪个班了吗？
作者: fantacyleo    时间: 2014-9-20 16:46
JerryJava 发表于 2014-9-20 16:42
一样，我几乎不用qq，邮箱联系！最后决定报哪个班了吗？

没有，我主要是现在抽不出4个月脱产时间，很纠结
作者: JerryJava    时间: 2014-9-20 16:50
fantacyleo 发表于 2014-9-20 16:46
没有，我主要是现在抽不出4个月脱产时间，很纠结

了解，希望能成为同学～你这个朋友我交定了～
给你发邮件了，请看下～



欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2