约瑟夫（Josephus）问题

这是17世纪的法国数学家加斯帕在《数目的游戏问题》中讲的一个故事：15个教徒和15 个非教徒在深海上遇险，必须将一半的人投入海中，其余的人才能幸免于难，于是想了一个办法：30个人围成一圆圈，从第一个人开始依次报数，每数到第九个人 就将他扔入大海，如此循环进行直到仅余15个人为止。问怎样排法，才能使每次投入大海的都是非教徒。
不过，现在经常在各类的笔试中出现的是由此延伸出来的所谓的“出列问题”，大致是这样的：
20个小孩排成一个环，从其中的一个小孩开始，从1报数，报到三的倍数的小孩需要出列，如此循环的数下去，问最后剩下的哪个小孩！
这里我们主要讨论“出列问题”，如果这个题目是以选择题的形式出现，恐怕大家使用最多的方法是在演算纸上模拟这个过程，找出最后剩下的人，在那种场合恐怕这是最切实可行的办法。如果是以程序设计的形式出现，大家也许会用数组或者是链表的形式来实现，可是，无论如何，我们似乎也走步出模拟整个过程的圈圈。
在《具体数学》英文版的第80页用数学思维给出了一种巧妙的解法，具体分析如下：

1. 第一轮结束后，第一个小孩应该数20,第二个小孩21，第四个小孩是22 ...，尝试着从这中间找出规律，在本轮还能留下的小孩数的数肯定是不能被三整除的数，不妨设为3k+1, 3k+2，那么在下轮他们数的数呢？其实这个很好算，设小孩的个数为n，从n+1算，每当从1开始算的跳三个数时，从n+1考试算的跳2个数，这样下轮的人所数的数分别为2k+1+n, 2k+2+n...
2. 因为是数到三的倍数的小孩出列，所以第k个出列的小孩肯定数的是3k，第n个出列的当然是3n了。
3. 所以我们可以从后向前倒推，最后算出第n个出列的小孩的最初位置。数N=2k+t+n的小孩上次数3k+t=3k+(N-2k-n)=k+N-n；因为1<=t<=2;所以k=(N-t-n)/2=(N-n)/2-t/2,(N-n)/2-2/2<=k<=(N-n)/2-1/2,又因为k>0，所以k=取整{(N-n)/2-1/2}。3k+t=(N-n-1)/2+N-n。

最后给出伪代码如下:

N = 3*n;
while N >; n do
    N = (N-n-1)/2+N-n;
return N;

参考链接: