约瑟夫斯问题求解

约瑟夫斯问题求解

ID:12817352

大小:752.50 KB

页数:10页

时间:2018-07-19

约瑟夫斯问题求解_第1页
约瑟夫斯问题求解_第2页
约瑟夫斯问题求解_第3页
约瑟夫斯问题求解_第4页
约瑟夫斯问题求解_第5页
资源描述:

《约瑟夫斯问题求解》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

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的初始值

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

3、.单向循环链表抽象数据类型定义:typedefstructnode{ElemTypedata;ElemTypenum;structnode*next;}SLNODE;基本操作:structnode*create_sl(intn);//创建单向循环链表2.主程序流程及其模块调用关系1)创建循环链表的流程图2)约瑟夫问题求解流程图3)主函数流程图四、详细设计1.实现每个操作的伪码,重点语句加注释主程序:voidmain(){SLNODE*head;intn,m;head=(SLNODE*)malloc(sizeof(SLNODE));printf("/****

4、*********************************/");//初始界面printf("学号:031350102");printf("姓名:王亚文");printf("约瑟夫斯问题求解");printf("/*************************************/");printf("输入总人数n=");scanf("%d",&n);printf("输入初始报数值m=");scanf("%d",&m);head=create_sl(n);Josephus(head,n,m);}2.创建循环单链表

5、structnode*create_sl(intn){SLNODE*p,*s,*head;ElemTypex;inta;head=(SLNODE*)malloc(sizeof(SLNODE));p=head;head->next=head;for(a=1;a<=n;a++)//循环直到输入n个密码值跳出循环{s=(SLNODE*)malloc(sizeof(SLNODE));printf("请输入第%d个人的密码值",a);scanf("%d",&x);s->data=x;s->num=a;if(head->next==head)head=s;else

6、p->next=s;p=s;}p->next=head;returnhead;}3.约瑟夫斯问题求解:voidJosephus(SLNODE*head,intn,intm){SLNODE*p,*q;inti;p=head;printf("出列序列:");while(p->next!=p){for(i=1;inext;}m=p->data;//读取新的密码值printf("%4d",p->num);q->next=p->next;//删除p节点free(p);p=q->next;}printf("%4

7、d",p->num);}4.函数调用关系图主函数中调用了structnode*create_sl(intn);voidJosephus(SLNODE*head,intn,intm);两个函数五、调试分析1.设计与调试过程中遇到的问题分析、体会1)创建单链表时,一开始写的程序是voidcreate_sl(SLNODE*head,intn),并没有没有报错,但最后运行时却不是想象的结果,然后尝试在主函数中写一个printf函数看一下创建表是否创建成功,事实证明并没有,后来改成了structnode*create_sl(intn);解决了这个问题,再次就是建

8、表的时候发现最后一个数并不是我输入的数,然后就是开始改那个循环=函

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。