约瑟夫问题的猴子选择国王。

一堆猴子有数字，数字是1，2，3...m m .这群猴子(m)按照1-m的顺序坐成一个圈，从1开始数，每数到第n个，猴子就会离开圈，以此类推，直到圈里只剩下最后一只猴子，那么猴子就是国王。

约瑟

密码问题

问题描述:N个数字为1，2，3，...，n顺时针坐成一圈，每人拿一个密码(正整数)。从名称

编号为1的人从1开始顺时针方向报数，报数到指定编号M时停止报数，向M报数的人将出列，并将

作为新的M值，他的密码从顺时针方向的下一个人开始，从1开始往回数，以此类推，直到全部。

直到所有人都出了队列。请设计一个程序找出列表顺序，其中N≤30，m和密码值从键盘输入。

二。基本要求:

(1)输入数据:输入m，n m，n为整数，n < m

(2)中文提示按照m只猴子的方法，数N个数，猴子输出的个数是多少为王，建立一个函数实现这个函数，通过编写解决约瑟夫问题。

当m较小时，可以通过笔算求解。

M=2

也就是说，n个人组成一个圈，1，2，1，2，向2报到死亡，直到只剩下一个人。

当n = 2 k时，第一个报数的人是最后一个死的。

对于任意自然数，n可以表示为n = 2 k+t，其中t

所以t人死了，就只剩下2 k人了，这2 k人中第一个死的就是最后一个。这2 k人中第一个报数的人是2t+1。

于是我找到了M=2时约瑟夫问题的解:

求最大的2的不大于n的整数次幂，记为2 k，最后死的人是2 (n-2 k)+1。

M=3

就是n个人组成一个圈，当1，2，3，1，2，3报数到3就死了，直到只剩下一个人。

这比M=2时要复杂得多。

我们以N=2009为例。

当N=2009，M=3时，最后被杀的人记为F(2009，3)，也可以简单记为F(2009)。

假设这种情况下还剩n人，下一轮会杀[n/3]人，[]表示四舍五入，还剩n-[n/3]人。

设n人为A1，A2，...，A (N-1)，An。

从a1开始报数。一圈下来，剩下的人分别是A1，A2，A4，A5，...A (n-n mod 3-1)，A (n-n mod 3+1)，...，安。

所以你可以得到:

1.a(n-n mod 3)是本轮最后一个死的，a(n-n mod 3+1)是下一轮第一个报数的。

2.如果3|n，最后死的人是新一轮的F(n-[n/3])人。

如果n mod 3≠0且f (n-[n/3])

如果n mod 3≠0且f(n-[n/3])& gt；N mod 3，最后死的人是新回合的F(n-[n/3])-(n mod 3)人。

3.新的第K个人对应原来的3 *[(K-1)/2]+(K-1)mod 2+1个人。

综合1，2，3，我们可以得到:

F(1)=1，F(2)=2，F(3)=2，F(4)=1，F(5)=4，F(6)=1，

当f (n-[n/3])时

当f (n-[n/3])>:在n mod 3处，k=F(n-[n/3])-(n mod 3)，F(n)= 3 *[(k-1)/2]+(k-1)mod 2+1。

这个算法需要计算[log(3/2)2009]次，数量不超过22，可以用笔计算。

所以:

第一圈，669人会被杀。这一圈最后一个被杀的人是2007年，剩下1340人。

第二圈，446人死亡，还剩894人。

第三圈，298人死亡，还剩596人。

第四圈198被杀，还剩398人。

第五圈132人阵亡，还剩266人。

第六圈杀了88人，剩下178人。

第七圈杀了59人，剩下119人。

第八圈，39人死亡，还剩80人。

第九圈，26人被杀，还剩54人。

第十圈18被杀，还剩36人。

十一圈，杀了12人，剩下24人。

十二圈，杀了8个人，剩下16个人。

十三圈，杀5人，剩下11人。

十四圈，死了三个人，剩下八个人。

十五圈，死了两个，还剩六个。

F(1)=1，F(2)=2，F(3)=2，F(4)=1，F(5)=4，F(6)=1，

然后推回去。

F(8)= 7 F(11)= 7 F(16)= 8 F(24)= 11 F(36)= 16 F(54)= 23 F(80)= 31 F(119)= 43 F(178

F(596)= 191 F(894)= 286 F(1340)= 425 F(2009)= 634