约瑟夫之问（约瑟夫问题（PASCAL））

这是一个古老的传说：有６４名战士被敌人俘虏了，敌人命令他们排成一个圆圈，编上号码１，２，３，…，６４，敌人把１号杀了，又把３号杀了，他们是隔一个杀一个这样转着圈杀，最后剩下一个人，这个人就是约瑟夫斯，请问约瑟夫斯是多少号？这就是“约瑟夫斯问题”。

这个问题是比较容易解答的：敌人从１号开始，隔一个杀一个，第一圈把奇数号码的战士全杀死了。剩下的３２名战士需要重新编号，而敌人在第二圈杀死的是重新编排的奇数号码。

由于第一圈剩下的全部是偶数号２，４，６，８，…，６４。把它们全部用２除，得１，２，３，４，…，３２，这是第二圈重新编的号码，第二圈杀过之后，又把奇数号码都杀掉了，还剩下１６个人，如此下去，可以想到最后剩下的必然是６４号。

６４＝２６，它可以连续被２整除６次，是从１到６４中能被２整除次数最多的数，因此，最后必然把６４号剩下，从６４＝２６还可以看到，是转这６圈之后，把约瑟夫斯剩下来的。

如果有６５名战士被俘，敌人还是按上述方法残杀战士，最后剩下的还是６４号约瑟夫斯吗？

不是了，因为第一个人被杀后，也就是１号被杀后，第二个被杀的必然是３号，如果把１号排除在外，那么剩下的仍是６４个人，对于剩下这６４个人，新１号就应该是原来的３号，这样原来的２号就变成新的６４号了，所以剩下的必然是原来的２号。

对于一般情况来说，如果原来有２ｋ个人，最后剩下的必然是２ｋ号；如果原来有２ｋ＋１个人，最后剩下的是２号；如果原来有２ｋ＋２个人，最后剩下的是４号……如果原来有２ｋ＋ｍ个人，最后剩下的是２ｍ号。

比如，原来有１００人，由于１００＝６４＋３６＝２６＋３６，所以最后剩下的是２×３６＝７２号；又比如，原来有１１１人，由于１１１＝６４＋４７＝２６＋４７，所以最后剩下的是２×４７＝９４号。

下面把问题改一下：不让被俘的战士站成圆圈，而排成一条直线，然后编上号码，从１号开始，隔一个杀一个，杀过一遍之后，然后再重新编号，从新１号开始，再隔一个杀一个，问最后还是约瑟夫斯吗!

答案是肯定的，最后剩下的仍然是约瑟夫斯。

如果战俘人数是６５人呢？剩下的还是约瑟夫斯，只要人数不超过１２８人，也就是人数小于２７，那么最后剩下的总是约瑟夫斯，因为从１到１２８中间，能被２整除次数最多的就是６４，而敌人每次都是杀奇数号留偶数号，所以６４号总是最后被留下的人。

据说著名犹太历史学家 Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始，越过k-2个人（因为第一个人已经被越过），并杀掉第k个人。接着，再越过k-1个人，并杀掉第k个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。问题是，给定了和，一开始要站在什么地方才能避免被处决？Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。
17世纪的法国数学家加斯帕在《数目的游戏问题》中讲了这样一个故事：15个教徒和15 个非教徒在深海上遇险，必须将一半的人投入海中，其余的人才能幸免于难，于是想了一个办法：30个人围成一圆圈，从第一个人开始依次报数，每数到第九个人就将他扔入大海，如此循环进行直到仅余15个人为止。问怎样排法，才能使每次投入大海的都是非教徒。
*问题分析与算法设计
约瑟夫问题并不难，但求解的方法很多；题目的变化形式也很多。这里给出一种实现方法。
题目中30个人围成一圈，因而启发我们用一个循环的链来表示，可以使用结构数组来构成一个循环链。结构中有两个成员，其一为指向下一个人的指针，以构成环形的链；其二为该人是否被扔下海的标记，为1表示还在船上。从第一个人开始对还未扔下海的人进行计数，每数到9时，将结构中的标记改为0，表示该人已被扔下海了。这样循环计数直到有15个人被扔下海为止。