约瑟夫斯问题求解

1、实验一：约瑟夫斯问题求解一、问题描述1 实验题目：约瑟夫斯问题的一种描述是：编号为1,2,n的n个人按顺时针方向围坐一圈，每人持有一个密码9（正整数）。一开始任选一个正整数作为报数上限值m从第一个人开始按照顺时针方向自1开始报数，报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他在顺时针方向下一个人开始重新重新从1报数，如此下去，直至所有的人全部出列为止。试设计一个程序,按出列顺序印出各人编号。2 .基本要求：利用单向循环链表模拟此过程，按照出列的顺序印出各人编号。3 .测试数据：n=7,7个人的密码依次为3,1,7,2,4,8,4.m的初始值为6（正确的出列顺序应为6,1,4,7,

2、2,3,5o二、需求分析1 .程序所能达到的基本可能：本程序能够按出列顺序印出各人编号，程序运行后显示提示信息，提示用户输入人数n,初始报数值m,n个人的密码，程序需自动考虑重复的,用户输入完毕后，程序自动输出运算结果。2 .输入的形式及输入值范围：输入人数n,初始报数值m,n个人的密码,所有值均为正整数int型。3 .输出的形式：输出的是按出列顺序印出各人编号，为正整数int型。4 .测试数据要求：测试数据要求为int型三、概要设计1 .所用到得数据结构及其ADT为了实现上述功能,应以单向循环链表有序链表表示集合数据类型。2 .单向循环链表抽象数据类型定义：typedefstructnode

3、ElemTypedata;ElemTypenum;structnode*next;SLNODE;基本操作：structnode*create_sl（intn）;/创建单向循环链表3 .主程序流程及其模块调用关系1）创建循环链表的流程图开始2）约瑟夫问题求解流程图开始p=head;i=lNP-3）主函数流程图开始，结束四、详细设计1.实现每个操作的伪码，重点语句加注释主程序：voidmain()SLNODE*head;intn,m;head二(SLNODE*)malloc(sizeof(SLNODE);printf(',printf("printf(',prin/*/n

4、/vAxvAxxix、X>xvLxvix不不不不不不不不/学号：031350102hz，);姓名：王亚文王)；约瑟夫斯问题求解n);pt16僦*'/*辎燹%人数n=n););scanf(96d，&n);printf(M输入初始报数值m=n");scanf(d，&m);head=create_sl(n);Josephus(head,n,m);)2.创建循环单链表structnode*createsi(intn)初始界面SLNODE*p,*s,*head;ElemTypex;inta;head二(SLNODE*)malloc(sizeof(SLNODE);p

5、二head;head->next=head;for(a=l;a<=n;a+)/循环直到输入n个密码值跳出循环(s=(SLNODE*)malloc(sizeof(SLNODE);printfC请输入第1个人的密码值n,a);scanf(d”,&x);s->data=x;s->num=a;if(head-next二二head)head=s;elsep-next=s;P=S；)p->next=head;returnhead;4 .约瑟夫斯问题求解：voidJosephus(SLNODE*head,intn,intm)(SLNODE*p,*q;inti;p=hea

6、d;printfC出列序列：);while(p->next!=p)(for(i=l;i<m;i+)/报数报的m时跳出循环(Q=P；p=p->next;m=p->data;/读取新的密码值printfC%4dz，,p->num);删除P节点q_>next=p->next;/free(p);p=q_>next;)printf(4dn，p->num);5 .函数调用关系图主函数中调用了structnode*create_sl(intn);voidJosephus(SLNODE*head,intn,intm);两个函数五、调试分析1 .设计与调试过

7、程中遇到的问题分析、体会1) 创建单链表时，一开始写的程序是voidcreate_sl(SLNODE*head,intn),并没有没有报错，但最后运行时却不是想象的结果，然后尝试在主函数中写一个printf函数看一下创建表是否创建成功，事实证明并没有，后来改成了structnode*create_sl(intn);解决了这个问题，再次就是建表的时候发现最后一个数并不是我输入的数，然后就是开始改那个循环二函数，发现我虽然是读了7个数，但第7个数并没有赋值给链表，原错误函数：p=head;head->next=head;printf(请输入密码值n)；scanf&x);for(a=l

8、;a<n;a+)/循环直到输入n个密码值跳出循环s=(SLNODE*)malloc(sizeof(SLNODE);printf(请输入密码值n");s->data=x;s->num=a;if(head-next二二head)head=s;elsep->next=s;P=s;经过修正后的函数：p=head;head->next=head;for(a=l;a<=n;a+)/循环直到输入n个密码值跳出循环(SLNODE*)malloc(sizeof(SLNODE);printfC请输入第1个人的密码值n,a);s->data=x;s->num

9、=a;if(head-next二二head)head=s;elsep->next=s;P=s;2)建表成功之后开始解决本次的主问题约瑟夫斯求解问题,本问题主要考虑循环终止条件,一开始写的是head->next=head;发现经常运行错误，后来修正用p->next!=p,然后最后一个p值单独写一句输出printf(%4dn,p->num);中间的句子就是找到报数值然后删除，注意保留要删除节点的密码值,并没有什么大问题。还有一个问题，就是在开始的时候创建单链表并没有想到要用序号值num最开始定义单链表的语句:typedefstructnodeElemTypedata;str

10、uctnode*next;x进行SLNODE;然后就会在创建链表赋值时和解决约瑟夫斯问题时都要重新定义一个变量计数，增加了程序的复杂度最后修正为:typedefstructnodeElemTypedata;ElemTypenum;structnode*next;比如少打不属于SLNODE;3)剩下的还有一些小问题,了一个字母，打错一个字母，这些程序会报错，逻辑错误，所以解决起来也比较快，2.主要算法的时间复杂度分析创建单链表的时间复杂度为0(n);约瑟夫斯问题的时间复杂度与n值有关，也与每个人的密码值有关，时间复杂度0(mn;空间复杂度为0(n);六、使用说明程序运行后显示提示信息，提示用户输

11、入人数n,初始报数值mn个人的密码，用户按照提示输入完毕后，程序自动输出运算结果。七、测试结果。wC:DociiBentsandSetting，hp桌面Debug031350102.exe'I学号z031350102姓名3王亚文约瑟夫斯问题求解除人总人数nP陆人初始报数值",输入第1个人的密码值3输入第2个人的密码值也输入笫3个人的密码值输入第4个人的密码值,输入第2人的密阴值情输入第6个人的密码值R情输入勒个人的密利值H出列序列：6147235Currentlocaltineanddate：FriOct301B：26：142015Pressanykeytocontinue-

12、八、附录# include<stdio.h># include<malloc.h># include<stdlib.h># inelude<time.h>typedefintElemType;typedefstructnodeElemTypedata;ElemTypenum;structnode*next;SLNODE;/单链表的定义structnode*create_sl(intn);voidJosephus(SLNODE*head,intn,intm);intmain()/主函数SLNODE*head;intn,m;timetrawtime;

13、structtm*timeinfo;time(&rawtime);timeinfo=localtime(&rawtime);初始界面*printf(V*An");/head二(SLNODE*)malloc(sizeof(SLNODE);printf(n学号：031350102n")；printfC1姓名：王亚文nn);printf(-约瑟夫斯问题求解n")；*printf(V*An");printf("输入总人数n=n");scanf("d”,&n);printfC1输入初始报数值m=n")

14、;scanf("%d",&m);head=create_sl(n);/仓U建单牵连表Josephus(head,n,m);printf("Currentlocaltimeanddate:%sM,asctime(timeinfo);return0;)structnode*create_sl(intn)(SLNODE*p,*s,*head;ElemTypex;inta;head=(SLNODE*)malloc(sizeof(SLNODE);p二head;head->next=head;for(a=l;a=n;a+)/循环直到输入n个密码值跳出循环s=(S

15、LNODE*)malloc(sizeof(SLNODE);printfC请输入第d个人的密码值n,a);scanf(d”,&x);s->data=x;s->num=a;if(head->next=head)head=s;elsep->next=s;P二s;)p->next=head;returnhead;voidJosephus(SLNODE*head,intn,intm)/约瑟夫斯问题求解SLNODE*p,*q;inti;p=head;printfC出列序列while(p->next!=p)(for(i=l;i<m;i+)/(q=P；p=p->next;m=p->data;/printfC%4dz/,p->num);q->next=p->next;/free(p);程序运行到第m个人跳出循环读取新的密码值删除P节点p=q->next;printf(4dn，p->num);九、实验收获和感想通过本实验首先是解决了约瑟夫斯问题，利用计算机快速解决这个问题，其次在程序编写过程中慢慢掌握了循环单链表的一些用法以及注意事项，因为距离上次学习c语言已经有很长一段时间，这次确实遇到了很多