约瑟夫斯问题谁知道?

约瑟夫斯问题谁知道?
约瑟夫斯问题
谁知道?

约瑟夫斯问题谁知道?
约瑟夫问题
约瑟夫问题是个有名的问题：N个人围成一圈,从第一个开始报数,第M个将被杀掉,最后剩下一个,其余人都将被杀掉.例如N=6,M=5,被杀掉的人的序号为5,4,6,2,3.最后剩下1号.
假定在圈子里前K个为好人,后K个为坏人,你的任务是确定这样的最少M,使得所有的坏人在第一个好人之前被杀掉.

约瑟夫问题是个有名的问题：N个人围成一圈，从第一个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉。例如N=6，M=5，被杀掉的人的序号为5，4，6，2，3。最后剩下1号。
假定在圈子里前K个为好人，后K个为坏人，你的任务是确定这样的最少M，使得所有的坏人在第一个好人之前被杀掉。
举个例子：
有64名战士被敌人俘虏了。敌人命令他们拍成一圆圈，编上号码1，2，3…，6...

全部展开

约瑟夫问题是个有名的问题：N个人围成一圈，从第一个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉。例如N=6，M=5，被杀掉的人的序号为5，4，6，2，3。最后剩下1号。
假定在圈子里前K个为好人，后K个为坏人，你的任务是确定这样的最少M，使得所有的坏人在第一个好人之前被杀掉。
举个例子：
有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号。

收起

约瑟夫斯 应该知道...