资源描述：
《约瑟夫环c语言的实现验证报告》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、约瑟夫环姓学系班名号别信息与电子系级计算填写日期2010年10月30一•问题描述约瑟夫(Joseph)问题的一种描述是：编号为1,2,n的n个人按顺时针方向围坐一圈，每人持有一个密码(正整数)。一开始任选一个正整数作为报数上限值m,从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人岀列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求岀出列顺序o二.基本要求利用利用顺序表存储结构及单向循环链表存储结构模拟约瑟夫环，按照出列的顺序
2、印出各人的编号三•测试数据m的上限为20,初值为6；(1)对于门二7,7个人的密码依次为：3,1,7,2,4,8,4进行测试。(2)对于从键盘输入的n和n个人的密码进行测试。用数组实现约瑟夫环程序代码：#includevoidmain(){intnum[100];intm,n,i,k=0,s二0;int*p=num;printf("输入初始密码和人数n");scanf("%d%cT,&m,&n);printfC个人密码，z);for(i=1;i<=n;i++)scanf("%d",&num[i
3、]);i二1；while(s<=(n-1))//当未退出人数(s)大于等于一时执行循环体{if(*(p+i)!二0)k++;if(k二二m){printf(，z%d〃，i);m=*(p+i);*(p+i)二0;//对退出的人编号置零k二0;s++；}i++；if(i二二(n+1))//当循环到最后一位时返回到第一位i二1；}}测试数据结果:CdT:UsersStyleDesktopDebugCppl.exe*输入初始密码和人数n67个人密码31724846147235Pressanykeytocontinue
4、五・用链表实现约瑟夫环程序代码：#incIude#incIudetypedefstruetIist{intnum;intpassward;struet丨ist*next;}node;node*creatlist(intn){node*p,*q,*head;inti二1;head二(node*)maIIoc(sizeof(node));head->num=i;printff请输入第1个密码:，z);scanf("%d"，&head->passward);p二head;for(i=2;
5、i<=n;i++){q二(node*)maIIoc(sizeof(node));if(q=0)return0;printfC请输入第%4个人的密码i);scanf(，，%d，/,&q->passward);q->num二i;p->next二q;P二q；}p->next二head;returnhead;}voidjosephus(node*1,intk){inti;node*p=l,*q,*s;while(p->next!二p){for(i二1;inext;}printfC%d，z,p-
6、>num);k=p->passward;s二p;q->next二p->next;p二p->next;free(s);}printfr%d，z,p->num);printf(，，<，);}voidmain(){node*l;intn,k;printfC请输入实验人数：“)；scanf("%d",&n);printf("请输入初始key的值：〃);scanf("%cT,&k);丨二crea11ist(n);josephus(I,k);}测试数据结果:请输入实验人数：7请输入材站key的值:6请输入寬1个密科：3请鎰入重
7、2个人的密码:1请输入童3个人的密利:?请输入寬4个人的密箱:2请输入第5个人的密箱:4请输入童6个人的密柜）:8请输入寬?个人的密码：46147235Pressanykeytocontinue六：学习体会和实验中遇到的问题约瑟夫环，经过理解，可以认为是一个数学应用题：已知n个人围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到桌周围的人全部出列。用数组实现约瑟夫环的过程中，我第一个遇到的问题是理解了实验问题，但算法无法写成表达式，怎
8、样让数组中的元素重复剔除，后来通过网络上的学习和同学的参考理解了。在数组的实现过程中，我感觉最难的是循环的剔除。用链表实现过程中，我觉得通过指针的操作比较麻烦，但总体思路比较好操作。在这次学习中，我觉得数组和指针的应用比较广泛，链表代替数组来实现一些问题我还不熟练，要更多的学习和练习。2Wr320ud3Lam广东陶粒，广东陶粒厂h
