《猴子选大王问题》由会员分享，可在线阅读，更多相关《猴子选大王问题（19页珍藏版）》请在金锄头文库上搜索。
1、15 个教这是 17 世纪的法国数学家加斯帕在数目的游戏问题中讲的一个故事： 徒和 15 个非教徒在深海上遇险，必须将一半的人投入海中，其余的人才能幸免于 难，于是想了一个办法： 30 个人围成一圆圈，从第一个人开始依次报数，每数到第 九个人就将他扔入大海，如此循环进行直到仅余 15 个人为止。问怎样排法，才能 使每次投入大海的都是非教徒。*问题分析与算法设计约瑟夫问题并不难，但求解的方法很多；题目的变化形式也很多。这里给出一 种实现方法。题目中 30 个人围成一圈，因而启发我们用一个循环的链来表示。可以使用结 构数组来构成一个循环链。结构中有两个成员，其一为指向下一个人的指针，以构 成环形的
2、链；其二为该人是否被扔下海的标记，为 1 表示还在船上。从第一个人开 始对还未扔下海的人进行计数，每数到 9 时，将结构中的标记改为 0，表示该人已 被扔下海了。这样循环计数直到有 15 个人被扔下海为止。 编辑本段 约瑟夫问题的一般形式：约瑟夫问题是个有名的问题： N 个人围成一圈，从第一个开始报数，第 M个将 被杀掉，最后剩下一个，其余人都将被杀掉。例如N=6，M=5，被杀掉的人的序号为5，4，6， 2，3。最后剩下 1 号。假定在圈子里前 K 个为好人，后 K 个为坏人，你的任务是确定这样的最少 M，使得所有的坏人在第一个好人之前被杀掉。C+代码示例 :#includeusingname
3、spacestd;voidmain()intn,m,a101,k,i,j,num;.n-2,n-1,0,1,2,.k-2并且从 k 开始报 0。现在我们把他们的编号做一下转换：k-0k+1-1k+2-2k-2-n-2k-1-n-1变换后就完完全全成为了 (n-1) 个人报数的子问题，假如我们知道这个子问题 的解：例如 x 是最终的胜利者，那么根据上面这个表把这个 x 变回去不刚好就是 n 个人情况的解吗？！ ！变回去的公式很简单， 相信大家都可以推出来： x=(x+k)modn如何知道 (n-1) 个人报数的问题的解？对，只要知道 (n-2) 个人的解就行了。 (n-2) 个人的解呢？当然是先
4、求 (n-3) 的情况 这显然就是一个倒推问题！好了，思路出来了，下面写递推公式：令f 表示 i 个人玩游戏报 m退出最后胜利者的编号，最后的结果自然是 fn递推公式f1=0;f=(f+m)modi;(i1)有了这个公式，我们要做的就是从 1-n 顺序算出 f 的数值，最后结果是 fn 。 因为实际生活中编号总是从 1 开始，我们输出 fn+1由于是逐级递推，不需要保存每个 f ，程序也是异常简单：c+#includeintmain()intn,m,i,s=0;printf(NM=);scanf(%d%d,&n,&m);for(i=2;i9thenc:=c+cdiv10;c:=cmod10;e
5、nd;end;functioncxiaoa:boolean;vari:integer;begincxiaoa:=false;fori:=105downto1doifcathenbreak;end;proceduredoubleb;vari:integer;fori:=1to105dob:=b*2;fori:=1to104doifb9thenbeginb:=b+bdiv10;b:=bmod10;end;end;proceduredecc;vari,j:integer;beginfori:=1to104doifc=bthenc:=c-belsebeginj:=i+1;whilecj=0doinc(
6、j);whilejidobegincj:=cj-1; cj-1:=cj-1+10; dec(j);end;c:=c-b;end;end;procedurefua;vari:integer;begin fori:=1to104doifacthena:=a-celsea:=a-1;a:=a+10;a:=a-c;end;end;procedureoutit;vari,j:integer;beginfori:=1to105doa:=a*2;fori:=1to104doifa9thenbegina:=a+adiv10;a:=amod10;ifa10thena1:=a1-1elsebeginj:=2;wh
7、ileaj=0doinc(j);whilej1dobeginaj:=aj-1;aj-1:=aj-1+10;dec(j);end;a1:=a1-1;end;fori:=105downto1doifa0thenbeginj:=i;break;end;fori:=jdownto1dowrite(a);readln(s);la:=length(s);fori:=ladownto1doa:=ord(sla+1-i)-ord(0);b1:=1;c1:=1;whilecxiaoadobegindoubleb;incc;end;decc;fua;outit; 编辑本段 约瑟夫问题的另外一个有名的例子： 编辑本
8、段 猴子选大王一问题描述：一堆猴子都有编号，编号是 1，2，3.m, 这群猴子（ m个）按照 1-m 的顺序围 坐一圈，从第 1 开始数，每数到第 N个，该猴子就要离开此圈，这样依次下来，直 到圈中只剩下最后一只猴子，则该猴子为大王。二基本要求：（1） 输入数据：输入 m,nm,n 为整数， nm（2）中文提示按照 m 个猴子，数 n 个数的方法，输出为大王的猴子是几号， 建立一个函数来实现此功能C程序：#include#defineLENsizeof(structmonkey)10000ofinteger;n,s,i,j:integer;beginread(m,n); fori:=1tomd
9、oai:=1;j:=0;fori:=1tomdobegins:=0;whilesndobeginifjmtheninc(j)elsej:=1;s:=s+aj;write(j);aj:=0;end;end.#includeintmain()intn,m,i,s=0;printf(NM=);scanf(%d%d,&n,&m);for(i=2;i=n;i+)s=(s+m)%i;printf(Thewinneris%dn,s+1);return0;约瑟夫数学算法#includeintmain(void)intn,i=0,m,p;scanf(%d%d,&n,&m);.,a(n-1),an从 a1 开 始 报 数 ， 一 圈 之 后 ， 剩 下 的 人 为a1,a2,a4,a5,.a(n-nmod3-1),a(n-nmod3+1),.,an 于是可得：1、这一轮中最后一个死的是 a(n-nmod3), 下一轮第一个报数的是 a(n-nmod3+1)2、若 3|n, 则最后死的人为新一轮的第 F(n-n/3) 个人若 nmod30 且 f(n-n/3)nmod3 则最后死的人为新一轮的第 F(n-n/3)-( nmod3)人3、新一轮第 k 个
