约瑟夫环问题实验报告书讲解

算法与程序设计实验报告实验课程：约瑟夫环问题专业：计算机与科学技术班级：学号：姓名：一、课程设计的目的（需求分析）【实验内容与要求】问题描述：编号是1,2,„,n(n0)的n个人按照顺时针方向围坐一圈，每人持有一正整数密码。开始时任选一个正整数作为报数上限值m，从某个人开始按顺时针方向自1开始顺序报数，报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。令n最大值取30。设计一个程序来求出出列顺序，并输出结果。【基本要求】：利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各人的编号。【实现提示】由于该问题是由古罗马著名史学家Josephus提出的问题演变而来，所以通常称之为Josephus问题。Josephus问题的解决需要采用循环链表，先构造一个有n个结点的单循环链表，再给出一个报数上限值m(假设m1)，在链表的首结点开始从1计数，计到m时，对应的结点从链表中删除，然后在被删除结点的下一个结点又从1开始计数，直到最后一个结点从链表中删除算法结束。本设计采用的是不带头结点的循环链表，其中循环链表中结点的结构如下：typedefstruct{intnum;intcipher;structnode*next;}linklist;该问题可由两部分组成，分别由如下两个算法完成：（1）建立一个由头指针head指示的有n个结点的约瑟夫单循环链表creat。（2）寻找、输出和删除head所指的单循环链表的第m个结点select。该算法由如下具体步骤组成：①在head中的第一个结点起循环记数找第m个结点；②输出该结点的num值，把该结点的cipher(密码)值赋给m；③删除该结点；④转去执行①,直到所有结点被删除为止。二、测试数据进入程序，显示“1.开始游戏0.退出游戏”输入非0数进入游戏，输入0退出游戏。进入游戏后显示“输入总人数”，输入大于0的整数；若输入错误，则光标处清空，重新输入。后提示“输入开始人的序号”；范围是大于零，小于总人数的整数，若输入错误，则光标处清空，重新输入。后提示“输入间隔数字”，范围是任意正整数；若输入错误，则光标处清空，重新输入。按回车键，显示结果，并重新询问“1.开始游戏0.退出游戏”。三、算法思想首先，设计实现约瑟夫环问题的存储结构。由于约瑟夫环本身具有循环性质，考虑采用循环链表，为了统一对表中任意节点的操作，循环链表不带头结点。循环链表的结点定义为如下结构类型：typedefstructnode{intdata;structnode*next;}LNode;其次，建立一个不带头结点的循环链表并由头指针p指示。最后，设计约瑟夫环问题的算法。1、工作指针first，r，s，p，q初始化2、输入人数（n）和报数（m）3、循环n次，用尾插法创建链表intstart=k-1;LNode*s,*p,*L=0,*t;if(start==0)start=n;while(n!=0){s=(LNode*)malloc(sizeof(LNode));if(L==0)p=s;if(n==start)t=s;s-data=n;s-next=L;L=s;n--;}p-next=L;returnt;}LNode*GetNode(LNode*p)/*出队函数*/{LNode*q;for(q=p;q-next!=p;q=q-next);q-next=p-next;free(p);return(q);}4、输入报数的起始人号数k;5、循环n次删除结点并报出位置（其中第一个人后移k个）当in时移动指针k-1次s-next=L;删除p结点的后一结点qq=p;q-next!=p;q=q-nextq-next=p-next;报出位置后freeq;计数器i++;四、流程图五、源代码#includestdlib.h#includestdio.htypedefstructnode{intdata;structnode*next;}LNode;main(){LNode*Create(int,int);LNode*GetNode(LNode*);intPrint(LNode*,int);LNode*p;intn,k,m;intflag;while(1){printf(1.开始游戏0.退出游戏\n);scanf(%d,&flag);if(!flag)break;do{printf(请输入个数：\n);scanf(%d,&n);//输入个数if(n30||n1){printf(个数在1到30之间\n);return1;}}while(n=0);do{printf(输入开始人的序号(1~%d),n);scanf(%d,&k);}while(k=0||kn);do{printf(输入间隔数字);scanf(%d,&m);}while(m=0);p=Create(n,k);Print(p,m);}return0;}LNode*Create(intn,intk)/*创建循环链表*/{intstart=k-1;LNode*s,*p,*L=0,*t;if(start==0)start=n;while(n!=0){s=(LNode*)malloc(sizeof(LNode));if(L==0)p=s;if(n==start)t=s;s-data=n;s-next=L;L=s;n--;}p-next=L;returnt;}LNode*GetNode(LNode*p)/*出队函数*/{LNode*q;for(q=p;q-next!=p;q=q-next);q-next=p-next;free(p);return(q);}Print(LNode*p,intm)/*输出函数*/{inti;printf(出队编号:\n);while(p-next!=p){for(i=1;i=m;i++)p=p-next;printf(%d,p-data);p=GetNode(p);}printf(%d\n,p-data);return0;