《约瑟夫环问讲解课件.ppt》由会员分享，可在线阅读，更多相关《约瑟夫环问讲解课件.ppt（17页珍藏版）》请在三一办公上搜索。
1、题69-类约瑟夫环问题,有n个人围成一圈，顺序排号。从第一个人开始报数（从1到3报数），凡报到3的人退出 圈子，问最后留下的是原来第几号的那位。,如何来确定人出局的顺序如何实现最后一位数完又从第一位开始数的问题如何判断某人是否出局流程图代码,如何来确定人出局的顺序？ 我们可以把点名看成是不重复的，比如，有N个人，第一轮后剩N1个人、第二轮剩N2个人以此类推；那么，第二轮的地M个人可以看做第N+M次被点名。因此被淘汰的总是能被3整除的。,如何实现最后一位数完又从第一位开始数的问题？,很简单，我们可以用模运算（%）来完成。 比如： 1%3=1； 2%3=2; 3%3=0; 4%3=1。因此我们可以
2、用 j=i%n+1 （j表示人的序号，n表示场上还剩的人数，i表示点名次数） 来实现上述循环,如何判断某人是否出局,我们可以用数组aj来表示每个人，下标j表示他的序号，数组元素的值组表示他在场与否，比如：aj=0表示他已出局;aj=1表示他还在场。,流程图,源代码,#include#includeint main() int n ; printf(please input the vuale of n:n) ; scanf(%d,while(count!=0) j=i%n+1; if(aj=1) passwd+ ; if(passwd%3=0) aj=0 ; count- ; i+ ; pri
3、ntf(the last nember is %d:n,j); system(pause) ; return 0 ;,用指针实现,定义两个数列：一个表示队列(person)，一个存放出列顺序(pout)先把数组person赋值（0表示已出列）找出出列顺序用temp表示循环计数用指针p的移动计算出列顺序1.temp在0到m间循环， 指针p在数组上随着temp的增加而移动 当temp等于m时，标记指针所指向的值为0，表示该元素已出列m- 把已出列的元素移动到数组po数组2.当指针移动到队尾的时候，指针重新指向开头 当指针指向已出列的元素（值为0）时，指针向后移动temp不增加 打印po得到出列顺序
4、,代码,#includestdio.h#includestdlib.hvoid goout(int p,int po,int n,int m) ;main() int *preson=NULL,*pout=NULL ; /出队顺序初值为-1 ; int n,i,m; printf(Please input the value of n:n); scanf(%d,reson = (int *) malloc(n * sizeof (int); /申请动态数组 pout=(int*)malloc(n*sizeof(int); if (preson = NULL|pout=NULL) printf(
5、No enough memory!n); exit(0); /为队列元素赋初值 for (i=0;in;i+) presoni=i+1; printf(列队原始数据编号值: n) ; for (i=0;in;i+) printf(preson%d=%dt,i,presoni); /输出赋值结果 printf(n) ;,rintf(Please input the value of trun m:n); scanf(%d,m); goout(preson,pout,n,m); /调用函数 ，将出队顺序放入数组pout中 printf(出队顺序: n) ; for (i=1;i=n;i+) pri
6、ntf(poit%d=%dt,i,pouti-1) ; printf(n) ; free(preson); free(pout); system(pause) ;,void goout(int pp,int po,int n,int m) int i,temp,*p; /temp用于循环计数 p=pp ; /指针p指向队列数组的首地址 for (i=0;in;i+) temp=0 ; while (tempm) /开始循环报数，temp的 变化为0,1,2 if(*p!=0) /当该元素还在队列中时, if(p=(pp+n) /指向队尾时 p=pp ; /指针重新回到头 else p=p+1
7、; temp=temp+1 ; else if(p=(pp+n),/如果到达队尾，指针重新回到队头 p=pp ; p=p+1; /跳过出列的元素 p=p-1 ; /队列长度减一 poi=*p ; /生成输出队列顺序 *p=0 ; /标记成已经出队 ,用链表解决,建立一个循环链表从第一个开始到第N个分别赋上相应的值开始循环报数。报到需要出列的号码M的时候，从链表中删除该节点如此循环，直到只剩下一个节点是结束程序剩下那个节点的值即最后出列那个人的地址,代码,#includestdio.h#includestdlib.h struct child int num ; int next ; ;void
8、 OutQueue(int m,int n,int s,struct child ring) ;main() struct child ring100 ; int i,m,n,s ; printf(请输入人数n(199):) ; scanf(%d, ,rintf(人员编号为:n) ; /输出人员编号 for (i=1;i=n;i+) printf(%6d,ringi.num) ; if(i%10=0) printf(n) ; printf(n请输入开始报数的编号m(1100):) ; scanf(%d,void OutQueue(int m,int n,int s,struct child ring) int i,j,count ; if (m=1) j=n ; else j=m-1 ; for (count=1;count=n;count+) i=0 ; while (i!=s) j=ringj.next ; if (ringj.num!=0) i+ ; printf(%6d,ringj.num) ; ringj.num=0 ; if (count%10=0) printf(n) ; ,Thanks,
