实验一、约瑟夫问题.doc

实验一：约瑟夫问题求解一、 问题描述1、实验题目： 约瑟夫（Josephus）问题的一种描述是：编号为1，2，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上线值m，从第一个人开始按顺时针方向自1开始报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向下一个人开始重新从1报数，如此下去，直至所有的人全部出列为止。2、基本要求： 试设计一个程序，按出列顺序印出个人编号。3、测试数据： m的初值为20；n=7，7个人的密码依次为：3，1，7，2，4，8，4。 的初值为6，正确的出列顺序应为：6，1，4，7，2，3，5。二、 需求分析、本程序用来求出含有密码的约瑟夫问题，可以输出所有人的出列顺序。 2 、程序运行后显示提示信息，提示用户输入一圈的人数n，接着输入每个人的密码，最后提示输入初始密码。 3、用户输入完毕后，程序自动输出运算结果。三、 概要设计1、设计思路 n个人围成一圈，每个人的手中都有一个密码，这个密码决定了下一次报数的上限。 游戏规则： 给定一个初始密码 循环报数，报到密码值的人要出列，依次类推，直到所有的人都出列本程序要求输入的内容：n个人的密码及初始密码；本程序要求输出的内容：n个人出列的顺序。2、数据结构 为了实现上述功能，可以采用链式存储结构。采用链式存储结构，定义了一个存储个人信息的结构体，及两个自定 义函数，分别用于创建链表和约瑟夫出列操作。链表抽象数据类型的定义： #define SLNODE struct slnodeADT SLNODE 数据对象：D= |SLNODE, i=1,2,3. 数据关系：R= ADT SLNODE; 自定义函数: void create_SLnode(SLNODE *p,int n)/创建队列 创建链表，为N个人分配密码 void Josef(SLNODE *p,int n)/进行约瑟夫操作 输入初始密码m; for() 将出列的结点删除，并输出出列序号； 本程序的保护模块： 结构体模块 主程序模块 自定义函数模块调用关系：主函数模块结构体模块自定义函数模块 3、程序设计主要算法的流程图： create_SLnode( )算法流程图 Josef( )算法流程图四、详细设计1、元素类型、结点的类型及指针 #define SLNODE struct slnodeSLNODE/每个结点的结构体int num;/num代表序号int code;/code代表密码SLNODE *next; 2、自定义函数： void create_SLnode(SLNODE *p,int n)/创建队列，并将其尾指针指向第一个序号SLNODE *r,*s;s=p;int i,m;cout请给这n个人分配密码：endl;for(i=0;in;i+)cout请给第i+1个人输入密码：m;r=(SLNODE *)malloc(sizeof(SLNODE);r-code=m;r-num=i+1;r-next=s-next;s-next=r;s=s-next;p=p-next;s-next=p;void Josef(SLNODE *p,int n)/进行约瑟夫操作p=p-next;int m;int i,j; SLNODE *r;cout请输入初始密码：m;cout依次出列的序号为:endl;for(i=0;inext;for(i=0;in-2;i+)for(j=0;jnext;coutnext)-numnext)-code;r=p-next;p-next=r-next;if(m%2=0)coutnumendlnext)-numendl;elsecoutnext)-numendlnumendl; 3、主函数： int main()SLNODE *p;int n;cout请输入一圈的人数：n;p=(SLNODE *)malloc(sizeof(SLNODE);p-next=NULL;create_SLnode(p,n);Josef(p,n);return 0; 4、函数的调用关系：主函数main()调用自定义函数void create_SLnode(SLNODE *p,int n);/*创建队列*/与void Josef(SLNODE *p,int n);/*进行约瑟夫操作*/。五、 调试分析1、程序中将每个人的序号及密码用结构体的形式定义，并将其存储在链表中。2、在调试过程中遇到很多问题，比如，输出地序号有一个是重复的，经过仔细查程序，发现有一个指针所指向的空间不在循环链表内。3、用一个类似循环链表的链表来存储结点。为什么说是类似呢？因为开始时申请了一个带头结点的链表，但是尾指针并不是指向头指针的，而是指向头指针所指向的结点的，相当于循环链表有一个“小尾巴”。起初是将尾指针指向头指针的，构成了一个循环链表，但是由于头结点的存在，使出列算法不统一，因此才采用了这种类似循环链表的结构，但是，头结点就会造成所谓的内存泄露。4、算法的时空分析： 由于采用循环链表，元素个数为n个，设有一个指向序号1的指针*p。void create_SLnode(SLNODE *p,int n);/*创建队列*/与void Josef(SLNODE *p,int n);/*进行约瑟夫操作*/的操作的时间复杂度都是O（n）。六、使用说明 程序运行后用户根据提示输入“一圈的人数”n，然后程序会提示用户为这n 个人分配密码，输入完毕后，程序将自动给出出列的序号。七、结果1、 2、附录八、附录源程序文件清单：#include#include#define SLNODE struct slnodeSLNODE/每个结点的结构体int num;/num代表序号int code;/code代表密码SLNODE *next;void create_SLnode(SLNODE *p,int n);/创建队列void Josef(SLNODE *p,int n);/进行约瑟夫操作int main()SLNODE *p;int n;cout请输入一圈的人数：n;p=(SLNODE *)malloc(sizeof(SLNODE);p-next=NULL;create_SLnode(p,n);Josef(p,n);return 0;void create_SLnode(SLNODE *p,int n)/创建队列，并将其尾指针指向第一个序号SLNODE *r,*s;s=p;int i,m;cout请给这n个人分配密码：endl;for(i=0;in;i+)cout请给第i+1个人输入密码：m;r=(SLNODE *)malloc(sizeof(SLNODE);r-code=m;r-num=i+1;r-next=s-next;s-next=r;s=s-next;p=p-next;s-next=p;void Josef(SLNODE *p,int n)/进行约瑟夫操作p=p-next;int m;int i,j; SLNODE *r;cout请输入初始密码：m;cout依次出列的序号为:endl;for(i=0;inext;for(i=0;in-2;i+)for(j=0;jnext;coutnext)-numnext)-code;r=p-next;p-next=r-next;if(m%2=0)coutnumendlnext)-numendl;elsecoutnext)-numendlnumendl;九、扩展采用顺序存储结构实现若采用顺序存储结构，利用动态申请两个数组，容量为N，分别存放密码与 序号，还有两个自定义函数，分别用于创建链表和约瑟夫出列操作。、概要设计 1、数据结构 数组的抽象数据类型的定义： ADT RN 数据对象：D= |int, i=1,2,3. 数据关系：R= ADT RN; 自定义函数： void Create_Code(int a,int b,int n);/*为n个人创建密码，a代表密码，b代表序号*/ 动态申请两个数组，容量为N，并为N个人分配密码 void Josef(int a,int b,int n,int m);/*对这n个人进行约瑟夫操作，并输出出列序号，m代表初始密码*/ 输入初始密码m; for() 将出列的结点删除，并输出出列序号； 本程序的保护模块： 结构体模块 主程序模块 自定义函数模块调用关系：自定义函数模块主函数模块 2、程序设计主要算法的程序流程图：Create_Code( )的算法流程图：Josef( )的程序流程图： 、详细设计 1、自定义函数： void Create_Code(int a,int b,int n)int i;cout请给这n个人分配密码：endl;for(i=0;in;i+)bi=i+1;cout第i+1个人的密码为：ai;void Josef(int a,int b,int n,int m)int i,j,k;cout请输入初始密码：m;k=(m-1)%n;/如果初始密码mn的情况cout依次出列的序号为：endl;/*算法核心，将出列的人从数组中删除， 并且只对前n-2个人用此算法*/for(i=0;in-2;i+)coutbkendl;m=ak;for(j=k;jn-i-1;j+)bj=bj+1;aj=aj+1;if(k+m)%(n-i-1)=0)k=n-i-2;elsek=(k+m)%(n-i-1)-1;/*当只剩下两人时，判断密码的奇偶性，决定出列顺序即可*/if(ak%2=0)coutb(k+1)%2endl;coutbkendl;elsecoutbkendl;coutb(k+1)%2endl; 2、主函数 int main()int n;int m=20;cout请输入一圈的人数：n;int *a=new intn;int *b=new intn;Create_Code(a,b,n);Josef(a,b,n,m);return 0; 3、函数的调用关系 主函数main()调用自定义函数void Create_Code(int a,int b,int n);/*为n个人创建密码，a代表密码，b代表序号*/与void Josef(int a,int b,int n,int m);/*对这n个人进行约瑟夫操作，并输出出列序号，m代表初始密码*/。、调试分析1、程序中首先提示用户输入总人数n，然后再主函数中动态申请了两个一维数组，分别存放序号及密码，然后通过Create_Code()函数进行密码分配。2、Josef（）函数中的算法，是通过寻找规律而来，利用每出列一个人，就将该人之后的所有元素依次向前移动一格，这样可以做到算法统一。3、在调试过程中，遇到很多问题，总是会少一个输出，经过仔细查程序，终于发现了这个Bug追求算法统一时，却将循环的次数与标号没有对应。4、算法的时空分析（1）void Create_Code(int a,int b,int n)的时间复杂度为O（n），空间复杂度为O（1）；void Josef(int a,int b,int n,int m);的时间复杂度为O（n），空间复杂度为O（n）。、使用说明 程序运行后用户根据提示输入“一圈的人数”n，然后程序会提示用户为这n个人 分配密码，输入完毕后，程序将自动给出出列的序号。、调试结果（程序调试结果参见链式结构的调试结果，二者的模式完全相同。）、源程序文件清单：#includevoid Create_Code(int a,int b,int n);/为n个人创建密码，a代表密码，b代表序号void Josef(int a,int b,int n,int m);/对这n个人进行约瑟夫操作，并输出出列序号，m代表初始密码int main()int n;int m=20;cout请输入一圈的人数：n;int *a=new intn;int *b=new intn;Create_Code(a,b,n);Josef(a,b,n,m);return 0;void Create_Code(int a,int b,int n)int i;cout请给这n个人分配密码：endl;for(i=0;in;i+)bi=i+1;cout第i+1个人的密码为：ai;void Josef(int a,int b,int n,int m)int i,j,k;cout请输入初始密码：m;k=(m-1)%n;/如果初始密码mn的