约瑟夫环报告

约瑟夫环 计算机科学与技术专业 约瑟夫环问题 2008年1月5日 摘 要 当约瑟夫环中某人退出圆圈后，报数的工作要从下一个人开始继续，剩下的 人仍然是围成一个圆圈的，可以使用循环，由于退出圆圈的工作对应着表中结 点的删除操作，对于这种删除操作频繁的情况，选用效率较高的链表结构，为了 程序指针每一次都指向一个具体的代表一个人的结点而不需要判断，链表不带头 结点。所以，对于所有人围成的圆圈所对应的数据结构采用一个不带头结点的循 环链表来描述。设头指针为p，并根据具体情况移动。 为了记录退出的人的先后顺序，采用一个顺序表进行存储。程序结束后再输 出依次退出的人的编号顺序。由于只记录各个结点的number值就可以，所以定义一个整型一维数组。如：int quit[n];n为一个根据实际问题定义的一个足够大的整数。 解决问题的核心步骤： 1.建立一个具有n个链结点，无头结点的循环链表 2.确定第1个报数人的位置 3.不断地从链表中删除链结点，直到链表为空 2 目 录 一、 问题描述和分析 „„„„„„„„„„„„„„„„„ 5 二、 数据结构设计 „„„„„„„„„„„„„„„„„ 6 三、 算法设计 „„„„„„„„„„„„„„„„„„„ 7 四、 源代码说明 „„„„„„„„„„„„„„„„„„„ 10 五、 结果与分析 „„„„„„„„„„„„„„„„„„„ 13 3 图表目录 算法流程示意图 „„„„„„„„„„„„„„„„„„ 7 4 一、问题描述和分析 1. 问题描述 约瑟夫（Joeph）问题的一种描述是：编号为1,2,…,n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上 限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开 始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出 列顺序。 分析 n个人（编号0~(n-1))，从0开始报数，报到(m-1)的退出，剩下的人继续从0开始报数。求胜利者的编号。我们知道第一个人(编号一定是m%n-1) 出列之后，剩下的n-1个人组成了一个新的约瑟夫环（以编号为k=m%n的人开始）: k k+1 k+2 ... n-2, n-1, 0, 1, 2, ... k-2并且从k开始报0。 现在我们把他们的编号做一下转换： k --> 0 k+1 --> 1 k+2 --> 2 ... ... k-2 --> n-2 k-1 --> n-1 变换后就完完全全成为了(n-1)个人报数的子问题，假如我们知道这个子问 题的解：例如x是最终的胜利者，那么根据上面这个表把这个x 变回去不刚好就是n个人情况的解吗？！！变回去的公式很简单，相信大家都可以推出来： x‘=(x+k)%n如何知道(n-1)个人报数的问题的解？对，只要知道(n-2)个人的解就行了。(n-2)个人的解呢？当然是先求(n-3)的情况 ---- 这显然就是一个倒推问题！好了，思路出来了，下面写递推公式：令f表示i个人玩游戏报m退出最后胜利者的编号，最后的结果自然是f[n] 递推公式 f[1]=0; f=(f[i-1]+m)%i; (i>1) 有了这个公式，我们要做的就 是从1-n顺序算出f的数值，最后结果是f[n]。因为实际生活中编号总是从1开始，我们输出f[n]+1由于是逐级递推，不需要保存每个f，程序也是异常简单。 5 二、数据结构设计 1. 数据结构设计考虑 用单循环链表来模拟约瑟夫环，结点信息包括编号、密码、指向下一个结点 的指针，用三大主要的函数来实现功能，包括创建链表的函数、输出链表信息的 函数、删除结点也就是出队的函数、主函数等函数。 2. 逻辑结构与存储结构（用伪码描述） （1）主程序模块 Void main（）{ 初始化； do { 接受命令； 处理命令； }while（“命令”=“退出”）； } （2）创建链表模块 Static void creatlist（行参）{ 初始化； For{ 接受命令； 处理命令 } } （3）输出链表信息模块 static void PrntList(参数){ 定义变量并初始化； 输出命令； } （4）删除结点也就是出队模块 static void StatGame(参数){ 定义变量并初始化； While{ 开始报数； 输出结果；}} 6 三、算法设计 1．主要设计思想 设立一个标签，值为1执行循环语句，值为0跳出循环。循环语句里的for循环实现报数功能，也就是结点移动的功能，移动ikey个结点，再删除第ikey个结点，并把该结点的密码值赋给ikey，再从该结点的下一个结点移动，重复 上面的过程，结点全都删除后使标签的值为0，结束while循环，游戏结束。 2．算法流程示意图 1)主函数程序算法流程图 开始 输入n，m 创建单循环链 表 输出链表信息 开始游戏 输入a 是 a=1？ 否 结束 7 2)创建单循环链表函数流程图 开始 i<=n? 否 是 输入每人所持有 的密码 创建结点 结束 3)删除结点函数（出列函数）程序流程图 8 开始 假 iflag=1 真 假 icounter<=ike y 真 从1开始报数,报m结束 iflag=0 真 prv=pru 假 报m的人出列 结束 9 四、源代码及说明 （1） 主函数模块代码 circularlist pHead=NULL; int main(void) { int n, m， iflag=1 while(iflag=1){ printf("请输入总人数n="); scanf("%d",&n); printf("\n再请输入初始报数上限m="); scanf("%d",&m)； CreatList(&pHead,n); printf("\n输出所有人的信息如下:\n"); PrntList(pHead); printf("\n按照出列顺序输出每个人的编号:\n"); StatGame(&pHead, m); printf("\n约瑟夫环的游戏完成!\n"); printf("输入1开始建环做游戏，输入0退出该游戏，请选择!");scanf("%d",&i); } return 0; } 程序解释：该主函数用一个循环语句，来执行其它的函数的功能。从键盘输入总人 数和初始的报数上限，再调用创建链表的函数建环，后输出单循环链表的信息，再 调用StatGame（）函数，报到上限的那个结点从表中删除既出队，然后再选择输入 一个数确定是否继续游戏，输入1继续，输入0退出。 （2） 创建单循环链表函数模块代码 static void CreatList(circularlist * ppHead, const int n) { int i,ikey; Node *pNew, *pCur; for(i=1;i<=n;i++) { 10 printf("请输入第%d个人所持有的密码:",i); scanf("%d", &ikey); pNew=GetNode(i,ikey); if(*ppHead==NULL) { *ppHead=pCur=pNew; pCur->next=*ppHead; } else { pNew->next=pCur->next; pCur->next=pNew; pCur=pNew; } } 程序解释：用一个for循环来给链表的每个结点分配空间，并从键盘输入每人所 持有的密码，如果头结点的值为空，使其指向新生成的一个结点，新结点的next 指针指向头结点，如果不是，则当前结点的next的值赋给新结点的next，然后 当前结点的next值指向新结点，再当前结点的指针指向新结点，实现链表的建 立。 （3）删除结点函数代码 static void StatGame(circularlist * ppHead, int ikey) { int iCounter, iFlag=1; Node *pPrv, *pCur, *pDel; pPrv=pCur=*ppHead; while(iFlag) ! */ { for(iCounter=1;iCounter<=ikey;iCounter++) { pPrv=pCur; pCur=pCur->next; } if(pPrv==pCur) iFlag=0; pDel=pCur; Prv->next=pCur->next; 11 pCur=pCur->next; ikey=pDel->key; printf("第 %d个人出列, 所持有密码是: %d\n", pDel->id,pDel->key); free(pDel); } ppHead=NULL; } 程序解释：设立一个标签，值为1执行循环语句，值为0跳出循环。循环语句里的for循环实现报数功能，也就是结点移动的功能，移动ikey个结点，再删除第ikey个结点，并把该结点的密码值赋给ikey，再从该结点的下一个结点移动， 重复上面的过程，结点全都删除后使标签的值为0，结束while循环，游戏结束。 12 五、结果与讨论 1、 运行结果： 1） 运行程序后，初界面： 图5.1 初界面 2）输入总人数之后的界面： 3）输入初始报数上限后的界面： 4）输入所有人所持有的密码后的界面： 13 5）输入1之后的界面： 14 6）继续新一轮的游戏，结束后的界面： 7）输入0之后的界面： 15 致谢 通过这次课设我把以前以为没有实际用处的书本知识转化为了实际问题来 解决，很有意思，也觉得课设这种动手能力更高的学习方法有助于我们把兴趣放 在学习上。 虽然遇到了不少困难，但在老师和同学的帮助下，我顺利完成了这次课设。 非常感谢老师和同学的帮助！ 16 参考文献 [1] 数据结构（C语言版），北京：清华大学出版社，2002 [2] 数据结构课程设计，北京：机械工业出版社，2004 [3] C语言程序设计教程，上海：高等教育出版社，2006 17 附录 源程序 #include #include #define TRUE 1 #define FALSE 0 typedef struct Node { int id; /* 编号 */ int key; /* 密码 */ struct Node *next; } Node,* circularlist; /* 创建单向循环链表 */ static void CreatList(circularlist * pphead, const int n); /* 运行" 约瑟夫环"问题 */ static void StatGame(circularlist * pphead, int ikey); /* 打印循环链表 */ static void PrntList(const Node *); /* 得到一个结点 */ static Node *GetNode(const int, const int); /* 测试链表是否为空, 空为 TRUE空为FALSE */ static unsigned EmptyList(const Node *); int main(void) { int n, m; int iflag=1; while(iflag==1){ circularlist pHead=NULL; printf("请输入总人数n="); scanf("%d",&n); printf("\n再请输入初始报数上限m="); scanf("%d",&m); CreatList(&pHead,n); printf("\n------------输出所有的人信息如下:-------------\n"); PrntList(pHead); 18 printf("\n--------------按照出列顺序输出每个人的编号:---------------\n"); StatGame(&pHead, m); printf("\n约瑟夫环的游戏完成!\n"); printf("\n\n是否继续游戏?输入1继续，输入0退出，请选择!\n"); scanf("%d",&iflag); } return 0; } static void CreatList(circularlist * ppHead, const int n) { int i,ikey; Node *pNew, *pCur; for(i=1;i<=n;i++) { printf("请输入第%d个人所持有的密码:",i); scanf("%d", &ikey); pNew=GetNode(i,ikey); if(*ppHead==NULL) { *ppHead=pCur=pNew; pCur->next=*ppHead; } else { pNew->next=pCur->next; pCur->next=pNew; pCur=pNew; } } printf("约瑟夫环已建成,可以开始报数游戏!\n"); } static void StatGame(circularlist * ppHead, int ikey) { 19 int iCounter, iFlag=1; Node *pPrv, *pCur, *pDel; pPrv=pCur=*ppHead; /* 将pPrv初始为指向尾结点，为删除作好准备 */ while(pPrv->next!=*ppHead) pPrv=pPrv->next; while(iFlag) { for(iCounter=1;iCounter<=ikey;iCounter++) /*移动iCipher-1趟指针! */ { pPrv=pCur; pCur=pCur->next; } if(pPrv==pCur) /* 是否为最后一个结点了 */ iFlag=0; pDel=pCur; /* 删除pCur指向的结点，即有人出列 */ pPrv->next=pCur->next; pCur=pCur->next; ikey=pDel->key; printf("第 %d个人出列, 所持有密码是: %d\n", pDel->id,pDel->key); /* 这 个编号标识出列的顺序 */ free(pDel); } ppHead=NULL; /* 为了安全就给个空值 */ } static void PrntList(const Node *pHead) { const Node *pCur=pHead; if (EmptyList(pHead)) return; do 20 { printf("第 %d个人所持有的密码是: %d\n",pCur->id,pCur->key); pCur=pCur->next; } while (pCur!=pHead); } static Node *GetNode(const int iId,const int ikey) { Node *pNew; pNew=(Node *)malloc(sizeof(Node)); if(!pNew) { printf("存储分配不成功!\n"); exit(-1); } pNew->id=iId; pNew->key=ikey; pNew->next=NULL; return pNew; } static unsigned EmptyList(const Node *pHead) { if(!pHead) { printf("表是空的!\n"); return TRUE; } return FALSE; } 21