约瑟夫环问题实验报告书.doc

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