约瑟夫斯问题求解.doc
《约瑟夫斯问题求解.doc》由会员分享,可在线阅读,更多相关《约瑟夫斯问题求解.doc(8页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、如有侵权,请联系网站删除,仅供学习与交流约瑟夫斯问题求解【精品文档】第 8 页实验一:约瑟夫斯问题求解一、 问题描述 1 实验题目:约瑟夫斯问题的一种描述是:编号为1,2,n的n个人按顺时针方向围坐一圈,每人持有一个密码9(正整数)。一开始任选一个正整数作为报数上限值m,从第一个人开始按照顺时针方向自1开始报数,报到m时停止报数,报m的人出列,将他的密码作为新的m值,从他在顺时针方向下一个人开始重新重新从1报数,如此下去,直至所有的人全部出列为止。试设计一个程序,按出列顺序印出各人编号。 2 基本要求:利用单向循环链表模拟此过程,按照出列的顺序印出各人编号。3 测试数据:n=7,7个人的密码依
2、次为3,1,7,2,4,8,4.m的初始值为6(正确的出列顺序应为6,1,4,7,2,3,5。 二、 需求分析 1 程序所能达到的基本可能:本程序能够按出列顺序印出各人编号,程序运行后显示提示信息,提示用户输入人数n,初始报数值m,n个人的密码,程序需自动考虑重复的,用户输入完毕后,程序自动输出运算结果。2 输入的形式及输入值范围 :输入人数n,初始报数值m,n个人的密码,所有值均为正整数int型。3 输出的形式: 输出的是按出列顺序印出各人编号,为正整数int型。4 测试数据要求 :测试数据要求为int型 三、 概要设计 1. 所用到得数据结构及其ADT 为了实现上述功能,应以单向循环链表有
3、序链表表示集合数据类型。 1. 单向循环链表抽象数据类型定义: typedef struct node ElemType data; ElemType num; struct node *next;SLNODE; 基本操作: struct node *create_sl(int n);/创建单向循环链表2. 主程序流程及其模块调用关系 1)创建循环链表的流程图2) 约瑟夫问题求解流程图3) 主函数流程图四、 详细设计 1. 实现每个操作的伪码,重点语句加注释 主程序:void main() SLNODE *head; int n,m; head=(SLNODE *)malloc(sizeof(
4、SLNODE); printf(/*/n); /初始界面 printf( 学号:031350102n); printf( 姓名:王亚文n); printf( 约瑟夫斯问题求解n); printf(/*/n); printf(输入总人数n=n); scanf(%d,&n); printf(输入初始报数值m=n); scanf(%d,&m); head=create_sl(n); Josephus(head,n,m);2.创建循环单链表struct node *create_sl(int n) SLNODE *p,*s,*head; ElemType x; int a; head=(SLNODE
5、*)malloc(sizeof(SLNODE); p=head; head-next=head; for(a=1;adata=x; s-num=a; if(head-next=head) head=s; else p-next=s; p=s; p-next=head; return head;3.约瑟夫斯问题求解:void Josephus(SLNODE *head,int n,int m) SLNODE *p,*q; int i; p=head; printf(出列序列:); while(p-next!=p) for(i=1;inext; m=p-data; /读取新的密码值 printf(
6、%4d,p-num); q-next=p-next; /删除p节点 free(p); p=q-next; printf(%4dn,p-num); 4. 函数调用关系图 主函数中调用了struct node *create_sl(int n);void Josephus(SLNODE *head,int n,int m);两个函数五、 调试分析 1. 设计与调试过程中遇到的问题分析、体会 1)创建单链表时,一开始写的程序是void create_sl(SLNODE *head ,int n),并没有没有报错,但最后运行时却不是想象的结果,然后尝试在主函数中写一个printf函数看一下创建表是否创
7、建成功,事实证明并没有,后来改成了struct node *create_sl(int n);解决了这个问题,再次就是建表的时候发现最后一个数并不是我输入的数,然后就是开始改那个循环=函数,发现我虽然是读了7个数,但第7个数并没有赋值给链表,原错误函数:p=head; head-next=head;printf(请输入密码值n);scanf(%d,&x);for(a=1;adata=x; s-num=a; if(head-next=head) head=s; else p-next=s; p=s;经过修正后的函数:p=head; head-next=head; for(a=1;adata=x;
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 约瑟夫 问题 求解
限制150内