训练算法思维是所有CSers的首要任务。--by 咸鱼之友
算法思维的训练是计算机专业学生的必修课，是入门课也是一辈子修炼的课程。可惜，这一方面的训练我们不但缺乏强调，而且还缺乏实际可行的训练课程。本文试图以求解Josephus问题为实例来讲解一个完整的问题求解过程，展示几种常用的手段。如果读者可以在此学到问题求解过程的若干要点，并以此指导自己的日常学习，则善莫大焉。
据说这是著名犹太历史学家 Josephus的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁死也不要被俘，于是计划了一种自杀方式，所有人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从，Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。
这个问题可以表达成这个形式：n个人围成一圈并从1开始依次编号，从第一个人开始数，将第k个人将被杀掉。如此循环直到最后剩下一个人。求最后生存者的编号是什么？将此问题求解记为J(n)。以下首先考虑k=2的情形。下图表达了这个问题在n=10时的结构。
在拿到一个问题之后，我们通常会做什么？建议：先拿些小的数字进行计算分析，然后猜一猜，再试一试。比如：先取n=10，计算得到J(n)=5，于是我们猜，也许如果n为偶数，则J(n)=n/2 。当n=2时，猜想还是对的。可惜，试多几个值之后，就发现，事实并非如此。比如：n=4时，猜想就被推翻了。
也许我们还必须给出一个更理想的猜想。回到小数值分析上，我们画了一个表格来表示。从表格中我们发现，所有的结果都是奇数。其实，这个猜想也非常合理，因为第一轮就消除了所有的偶数字。特别是，如果n是偶数，第一轮过后，我们回到了一个与初始情形类似的状况，不同的是，人数少了一半，而且大家的号码都变了。
比如，假设初始有2n个人（偶数个人），第一轮过后，我们得到：
这与初始为n个人时的情形相同，只不过编号发生了改变，变成了2n-1 。于是，如果我们知道了J(n)的解，我们就很轻易地得到J(2n)的解。也就是说：
J(2n) = 2*J(n) – 1 n>=1
利用这个公式，我们很快得到某些更大的n时的解。比如：J(20) = 2J(10)-1 =25-1=9 。接着就要考虑，如果n为奇数又会如何呢？
如果有2n+1个人，经过一轮后，会得到：
同样，我们也得到了类似初始为n人的情形，只不过，这次编号变成了2n+1，于是得：
J(2n) = 2*J(n) + 1 n>=1
至此，我们得到了一种非常有效的递归式的解题方案，不断应用以上公式，即使对某些很大的数，我们也能很快地得到答案。考虑到这个Josephus问题是关乎生死的大问题，我们还要进一步分析，试图求解一个封闭型的解。
我们又回归到原始的“试数-猜”的过程。幸运的是，我们可以利用以上递归式，构造更大的一张表格。
很容易注意到，数字”1”在循环出现，而且出现的位置对应的n值似乎总是2的某次乘方，即为2^m （注：^ 代表指数运算）。以m为指标将解分成若干组，1个成员的组，2个成员的组，4个成员的组，8个成员的组……如果对组内成员的解从1开始进行编号，那么解就是2t+1。那么我们猜，如果n=2^m + t ，
J(n=2^m + t) = 2t + 1 , m >=0 且 0 <= t < 2^m
现在我们需要使用问题求解中的另一个手段，证明。此处我们运用的是归纳法进行证明。首先，验证，m = 0 时公式成立，这是归纳基础。然后分两种情况：t为偶数和t为奇数的情形。考虑t为偶数，如果2^m + t = 2n 可得：
= 2*( 2 * t/2 + 1 ) – 1 [由归纳假设]
= 2t + 1
t为奇数的情形类似可证，留做练习。总之，结论得证！
例1：试求J(1024)。此时，
n = 2^10 +0，所以J(1024)=1。
例2:J(1050) = 2 * 26 + 1=53。
例3:J(100) = 2 * 36 + 1 =73。
至此，可以很客观地说，在k=2的情形下，我们已经得到了非常好的解答。只是在此关乎生死的大问题上，我们还需要进一步考虑，我们能否有更好的解决办法？似乎“2^m + l ”这种公式能给我们非常有益的启发（通常说的专业直觉！），二进制！如果，我们把n与l表达成二进制的形式，我们得到：
注意到，b_m必须为1，就是说，n=2^m+1的第m位二进制比特必须为1，请回忆下2^m意味什么。l就是n的末尾m-1个比特，2l是对l进行一次左移操作，而2l+1 就是在2l的末尾加1，也等同与加上一个b_m。也就是说，J(n)的值等于对n进行一次循环左移。Amazing！这里看懵了的可以参考一下CSI讲解1:二进制及其相关操作。
小结一下本例中的求解过程：试数，猜，验证或者证明；再试，再猜，再证明……然后再对方法求精、优化与推广。把Josephus问题推广到一般情形的求解不在此讨论，留给大家自行阅读。
声明，本文内容来自非常著名的教科书《具体数学》(在网上可以轻易找到该书开源免费电子版本)，我只是进行了裁剪与翻译，所有观点与实例都不具原创性。因为感觉这样的思维训练在我们的教学中极为缺乏，而此实例又相当有趣，所以记录下来推荐给大家。
Concrete Mathematics: A Foundation for Computer Science. 作者: Ronald L. Graham, Donald E. Knuth, Oren Patashnik. 出版年: 1994-3-10, 页数: 672, ISBN: 9780201558029
2017年07月整理
