猴子选大王问题.doc

这是17世纪的法国数学家加斯帕在数目的游戏问题中讲的一个故事：15个教徒和15 个非教徒在深海上遇险，必须将一半的人投入海中，其余的人才能幸免于难，于是想了一个办法：30个人围成一圆圈，从第一个人开始依次报数，每数到第九个人就将他扔入大海，如此循环进行直到仅余15个人为止。问怎样排法，才能使每次投入大海的都是非教徒。*问题分析与算法设计约瑟夫问题并不难，但求解的方法很多；题目的变化形式也很多。这里给出一种实现方法。题目中30个人围成一圈，因而启发我们用一个循环的链来表示。可以使用结构数组来构成一个循环链。结构中有两个成员，其一为指向下一个人的指针，以构成环形的链；其二为该人是否被扔下海的标记，为1表示还在船上。从第一个人开始对还未扔下海的人进行计数，每数到9时，将结构中的标记改为0，表示该人已被扔下海了。这样循环计数直到有15个人被扔下海为止。编辑本段约瑟夫问题的一般形式：约瑟夫问题是个有名的问题：N个人围成一圈，从第一个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉。例如N=6，M=5，被杀掉的人的序号为5，4，6，2，3。最后剩下1号。假定在圈子里前K个为好人，后K个为坏人，你的任务是确定这样的最少M，使得所有的坏人在第一个好人之前被杀掉。C+代码示例:#includeusing namespace std;void main()int n,m,a101,k,i,j,num; /计数器是从1开始的,所以100个人用101coutn;cout-100)cout玩家太多,请重新登陆此程序!endl;return;coutm;cout-endl;for(i=1;i=n;i+)a【i】=1;/注意百度百科里不让使用ASCII里的方括号，这里是中文字符集里的方括号，j=0;k=0;for(i=1;i=n+1;i+)if(a【i】=1)j=j+a【i】;if(j=m)j=0;a【i】=0;k+;if(k=n)num=i;break;if(i=n+1)i=0;cout最后获胜的玩家是第 num 号玩家!endl;cout- 0k+1 - 1k+2 - 2.k-2 - n-2k-1 - n-1变换后就完完全全成为了(n-1)个人报数的子问题，假如我们知道这个子问题的解：例如x是最终的胜利者，那么根据上面这个表把这个x变回去不刚好就是n个人情况的解吗？！变回去的公式很简单，相信大家都可以推出来：x=(x+k) mod n如何知道(n-1)个人报数的问题的解？对，只要知道(n-2)个人的解就行了。(n-2)个人的解呢？当然是先求(n-3)的情况 - 这显然就是一个倒推问题！好了，思路出来了，下面写递推公式：令f表示i个人玩游戏报m退出最后胜利者的编号，最后的结果自然是fn递推公式f1=0;f=(f+m) mod i; (i1)有了这个公式，我们要做的就是从1-n顺序算出f的数值，最后结果是fn。因为实际生活中编号总是从1开始，我们输出fn+1由于是逐级递推，不需要保存每个f，程序也是异常简单：c+#include int main()int n, m, i, s=0;printf (N M = ); scanf(%d%d, &n, &m);for (i=2; i=n; i+) s=(s+m)%i;printf (The winner is %dn, s+1);pascalvar n,m,i,s:integer;beginwrite(N M =);read(n,m);for i:=2 to n dos:=(s+m) mod i;writeln(The winner is ,s+1);end.这个算法的时间复杂度为O(n)，相对于模拟算法已经有了很大的提高。算n，m等于一百万，一千万的情况不是问题了。可见，适当地运用数学策略，不仅可以让编程变得简单，而且往往会成倍地提高算法执行效率。约瑟夫问题10e100版(from vijios)描述 Descriptionn个人排成一圈。从某个人开始，按顺时针方向依次编号。从编号为1的人开始顺时针“一二一”报数，报到2的人退出圈子。这样不断循环下去，圈子里的人将不断减少。由于人的个数是有限的，因此最终会剩下一个人。试问最后剩下的人最开始的编号。输入格式 Input Format一个正整数n，表示人的个数。输入数据保证数字n不超过100位。输出格式 Output Format一个正整数。它表示经过“一二一”报数后最后剩下的人的编号。样例输入 Sample Input9样例输出 Sample Output3时间限制 Time Limitation各个测试点1s注释 Hint样例说明当n=9时，退出圈子的人的编号依次为：2 4 6 8 1 5 9 7最后剩下的人编号为3初见这道题，可能会想到模拟。可是数据实在太大啦！我们先拿手来算，可知n分别为1，2，3，4，5，6，7，8.时的结果是1，1，3，1，3，5，7，1.有如下规律：从1到下一个1为一组，每一组中都是从1开始递增的奇数，且每组元素的个数分别为1，2，4.这样就好弄了！大体思路如下：read(a)b:=1,c:=1b为某一组的元素个数，c为现在所加到的数while c9 thenbeginc:=c+c div 10;c:=c mod 10;end;end;function cxiaoa:boolean;var i:integer;begincxiaoa:=false;for i:=105 downto 1 doif ca then break;end;procedure doubleb;var i:integer;beginfor i:=1 to 105 do b:=b*2;for i:=1 to 104 do if b9 thenbeginb:=b+b div 10;b:=b mod 10;end;end;procedure decc;var i,j:integer;beginfor i:=1 to 104 doif c=b then c:=c-b elsebeginj:=i+1;while cj=0 do inc(j);while ji dobegincj:=cj-1;cj-1:=cj-1+10;dec(j);end;c:=c-b;end;end;procedure fua;var i:integer;beginfor i:=1 to 104 doif ac then a:=a-c elsebegina:=a-1;a:=a+10;a:=a-c;end;end;procedure outit;var i,j:integer;beginfor i:=1 to 105 do a:=a*2;for i:=1 to 104 do if a9 thenbegina:=a+a div 10;a:=a mod 10;end;if a10 then a1:=a1-1 elsebeginj:=2;while aj=0 do inc(j);while j1 dobeginaj:=aj-1;aj-1:=aj-1+10;dec(j);end;a1:=a1-1;end;for i:=105 downto 1 do if a0 then begin j:=i;break;end;for i:=j downto 1 do write(a);end;beginreadln(s);la:=length(s);for i:=la downto 1 do a:=ord(sla+1-i)-ord(0);b1:=1;c1:=1;while cxiaoa dobegindoubleb;incc;end;decc;fua;outit;end.编辑本段约瑟夫问题的另外一个有名的例子：编辑本段猴子选大王一 问题描述：一堆猴子都有编号，编号是1，2，3 .m ,这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。二 基本要求：(1) 输入数据：输入m,n m,n 为整数，nm（2）中文提示按照m个猴子，数n 个数的方法，输出为大王的猴子是几号 ，建立一个函数来实现此功能C程序：#include #include#define LEN sizeof(struct monkey) /定义struct monkey 这个类型的长度struct monkeyint num;struct monkey *next;struct monkey *create(int m)struct monkey *head,*p1,*p2;int i;p1=p2=(struct monkey*)malloc(LEN);head=p1;head-num=1;for(i=1,p1-num=1;inum=i+1;p2-next=p1;p2=p1;p2-next=head;return head;struct monkey *findout(struct monkey *start,int n)int i;struct monkey *p;i=n;p=start;for(i=1;inext;return p;struct monkey *letout(struct monkey *last)struct monkey *out,*next;out=last-next;last-next=out-next;next=out-next;free(out);return next;int main()int m,n,i,king;struct monkey *p1,*p2;printf(请输入猴子的个数m:n);scanf(%d,&m);printf(每次数猴子的个数n :n);scanf(%d,&n);if(n=1)king=m;elsep1=p2=create(m);for(i=1;inum;free(p2);printf(猴王的编号是：%dn,king);return 0;pascal程序：vara:array1.10000 of integer;n,s,i,j:integer;beginread(m,n);for i:=1 to m do ai:=1;j:=0;for i:=1 to m dobegins:=0;while sn dobeginif jm then inc(j)else j:=1;s:=s+aj;end;write(j);aj:=0;end;end.#include int main()int n, m, i, s=0;printf (N M = ); scanf(%d%d, &n, &m);for (i=2; i=n; i+) s=(s+m)%i;printf (The winner is %dn, s+1);return 0;约瑟夫数学算法#include #include int main( void )int n, i = 0, m, p;scanf(%d%d, &n, &m); /n总人数，m步长while( +i n)p = p - n + (p - n - 1)/(m - 1);printf(%dn, p);getch();return 0;编辑本段笔算解决约瑟夫问题在M比较小的时候 ，可以用笔算的方法求解，M=2即N个人围成一圈，1，2，1，2的报数，报到2就去死，直到只剩下一个人为止。当N=2k的时候，第一个报数的人就是最后一个死的，对于任意的自然数N 都可以表示为N=2k+t,其中tn/2于是当有t个人去死的时候，就只剩下2k个人 ，这2k个人中第一个报数的就是最后去死的。这2k个人中第一个报数的人就是2t+1于是就求出了当M=2时约瑟夫问题的解：求出不大于N的最大的2的整数次幂，记为2k，最后一个去死的人是2(N-2k)+1M=3即N个人围成一圈，1，2，3，1，2，3的报数，报到2就去死，直到只剩下一个人为止。此时要比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),.,an于是可得：1、这一轮中最后一个死的是a(n-n mod 3),下一轮第一个报数的是a(n-n mod 3+1)2、若3|n,则最后死的人为新一轮的第F(n-n/3)个人若n mod 30 且f(n-n/3)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)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人，