《约瑟夫斯问题求解》由会员分享，可在线阅读，更多相关《约瑟夫斯问题求解（10页珍藏版）》请在金锄头文库上搜索。
1、word实验一：约瑟夫斯问题求解一、 问题描述 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
2、，4，7，2，3，5。 二、 需求分析 1 程序所能达到的根本可能：本程序能够按出列顺序印出各人编号，程序运行后显示提示信息，提示用户输入人数n,初始报数值m，n个人的密码，程序需自动考虑重复的，用户输入完毕后，程序自动输出运算结果。2 输入的形式与输入值X围 ：输入人数n,初始报数值m，n个人的密码，所有值均为正整数int型。3 输出的形式： 输出的是按出列顺序印出各人编号，为正整数int型。4 测试数据要求 ：测试数据要求为int型 三、 概要设计 1. 所用到得数据结构与其ADT 为了实现上述功能，应以单向循环链表有序链表表示集合数据类型。 1. 单向循环链表抽象数据类型定义： type
3、def 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(SLNODE); printf(/*/n); /初始界面 printf(
4、学号：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);struct node *create_sl(int n) SLNODE *p,*s,*head; ElemType x; int a; head=(SLNODE *)malloc(sizeof(SLNODE); p=head; head-next=hea
5、d; 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(%4d,p-num); q-next=p-next; /删除p节点 free(p); p=q
6、-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函数看一下创建表是否创建成功，事实证明并没有，后来改成了struct node *create_sl(int n);
7、解决了这个问题，再次就是建表的时候发现最后一个数并不是我输入的数，然后就是开始改那个循环=函数，发现我虽然是读了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; s-num=a; if(head-next=head) head=s; else p-ne
8、xt=s; p=s; 2建表成功之后开始解决本次的主问题约瑟夫斯求解问题，本问题主要考虑循环终止条件，一开始写的是head-next=head;发现经常运行错误，后来修正用p-next!=p，然后最后一个p值单独写一句输出printf(%4dn,p-num);中间的句子就是找到报数值然后删除，注意保存要删除节点的密码值，并没有什么大问题。还有一个问题，就是在开始的时候创建单链表并没有想到要用序号值num，最开始定义单链表的语句：typedef struct node ElemType data; struct node *next;SLNODE; 然后就会在创建链表赋值时和解决约瑟夫斯问题时都
9、要重新定义一个变量x进展计数，增加了程序的复杂度最后修正为：typedef struct node ElemType data; ElemType num; struct node *next;SLNODE; 3) 剩下的还有一些小问题，比如少打了一个字母，打错一个字母，这些程序会报错，不属于逻辑错误，所以解决起来也比拟快，2. 主要算法的时间复杂度分析 创建单链表的时间复杂度为On;约瑟夫斯问题的时间复杂度与n值有关，也与每个人的密码值有关,时间复杂度Omn;空间复杂度为On;六、 使用说明程序运行后显示提示信息，提示用户输入人数n,初始报数值m，n个人的密码，用户按照提示输入完毕后，程序自
10、动输出运算结果。七、 测试结果 八、 附录 #include #include #include #include typedef int ElemType;typedef struct node ElemType data; ElemType num; struct node *next;SLNODE; /单链表的定义struct node *create_sl(int n);void Josephus(SLNODE *head,int n,int m);int main() /主函数 SLNODE *head; int n,m; time_t rawtime; struct tm * ti
11、meinfo; time (&rawtime); timeinfo = localtime (&rawtime); head=(SLNODE *)malloc(sizeof(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); printf (Current local time and date: %s, asctime(timeinfo); return 0;struct node *create_sl(int n) SLNODE *p,*s,*head; ElemType x; int a; head=(SLNODE *)malloc(sizeof(SLNODE); p=head; head-next=head; for(a=1;a=n;a+) /循环直到输入n个密码值跳出循环 s=(SLNODE *)malloc(sizeof(SLNODE); printf(请输入第%d个人的密码值n,a
