Question

谁知道约瑟夫斯问题怎么解

传说古代有一批人被蛮族俘虏了，敌人命令把他们围成圈，编上123……然后把一号杀了，三号杀了然后每隔一个人就杀，最后剩下一个人，那就是约瑟夫斯，若，这批俘虏有一百人，那约瑟夫斯是第几号？若为200人呢，300人呢，有什么规律么？
欢迎回答

提示该问答中所提及的号码未经验证，请注意甄别。

Answer 1

题目]：听过这样一个古老的传说：有64名战士被敌人俘虏了。敌人命令他们拍成一圆圈，编上号码1，2，3…，64。敌人把1号杀了，又把3号杀了，他们隔着一个杀一个这样转着圈杀。最后只剩下一个人，这个人就是约瑟夫斯。请问约瑟夫斯是多少号？（这就是“约瑟夫斯”问题。）
这个问题解答起来比较简单：敌人从1号开始，隔一个杀一个，第一圈把所有的奇数号码的战士圈杀光了。剩下的32名战士需要重新编号，而敌人在第二圈杀死的是重新编号的奇数号码。
由于第一圈剩下的全部是偶数号2，4，6，…，64。把它们全部用2去除，得1，2，3，…，32。这是第二圈编的号码。第二圈杀过以后，又把奇数号码都杀掉了，还剩16个人。如此下去，可以想到最后剩下的必然是64号。
64=26，它可以连续被2整除6次，是从1到64中能被2整除次数最多的数，因此，最后必然把64 号留下。
如果有65名战士被俘，敌人还是按上述的方法残杀战士，最后还会剩下约瑟夫斯吗？
经过计算，很容易得到结论，不是。因为第一个人被杀后，也就是1号被杀后，第二个被杀的是必然3号。如果把1号排除在外，那么还剩下的仍是64人，新1号就是3号。这样原来的2号就变成了新的64 号，所以剩下的必然是2号。
进一步的归类，不难发现如果原来有2k个人，最后剩下的必然2k号；如果原来有2k+1个人，最后剩下2号；如果原来有2k+2个人，最后剩下4号……如果原来有2k+m个人，最后剩下2m号.
比如：原来有100人，由于100=64+36=26+36，所以最后剩下的就是36×2=72号；又如：原来有111人，由于100=64+47=26+47，所以最后剩下的就是47×2=94号。