约瑟夫环报告

《约瑟夫环报告》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、计算机科学与技术专业《数据结构与算法》课程设计报告题目约瑟夫环问题作者指导教师2008年1月5日21摘要当约瑟夫环中某人退出圆圈后，报数的工作要从下一个人开始继续，剩下的人仍然是围成一个圆圈的，可以使用循环表，由于退出圆圈的工作对应着表中结点的删除操作，对于这种删除操作频繁的情况，选用效率较高的链表结构，为了程序指针每一次都指向一个具体的代表一个人的结点而不需要判断，链表不带头结点。所以，对于所有人围成的圆圈所对应的数据结构采用一个不带头结点的循环链表来描述。设头指针为p，并根据具体情况移动。为了记录退出的人的先后顺序，采用一个顺序表进行存储。程序结束后

2、再输出依次退出的人的编号顺序。由于只记录各个结点的number值就可以，所以定义一个整型一维数组。如：intquit[n];n为一个根据实际问题定义的一个足够大的整数。解决问题的核心步骤：1.建立一个具有n个链结点，无头结点的循环链表2.确定第1个报数人的位置3.不断地从链表中删除链结点，直到链表为空21目录一、问题描述和分析……………………………………………5二、数据结构设计……………………………………………6三、算法设计…………………………………………………7四、源代码说明…………………………………………………10五、结果与分析……………………………

3、……………………1321图表目录算法流程示意图………………………………………………721一、问题描述和分析1.问题描述约瑟夫（Joeph）问题的一种描述是：编号为1,2,…,n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。2．分析n个人（编号0~(n-1))，从0开始报数，报到(m-1)的退出，剩下的

4、人继续从0开始报数。求胜利者的编号。我们知道第一个人(编号一定是m%n-1)出列之后，剩下的n-1个人组成了一个新的约瑟夫环（以编号为k=m%n的人开始）:kk+1k+2...n-2,n-1,0,1,2,...k-2并且从k开始报0。现在我们把他们的编号做一下转换：k-->0k+1-->1k+2-->2......k-2-->n-2k-1-->n-1变换后就完完全全成为了(n-1)个人报数的子问题，假如我们知道这个子问题的解：例如x是最终的胜利者，那么根据上面这个表把这个x变回去不刚好就是n个人情况的解吗？！！变回去的公式很简单，相信大家都可以推出来：x

5、‘=(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，程序也是异常简单。21二、数据结构设计1.数据结构设计考虑用

6、单循环链表来模拟约瑟夫环，结点信息包括编号、密码、指向下一个结点的指针，用三大主要的函数来实现功能，包括创建链表的函数、输出链表信息的函数、删除结点也就是出队的函数、主函数等函数。2.逻辑结构与存储结构（用伪码描述）（1）主程序模块Voidmain（）{初始化；do{接受命令；处理命令；}while（“命令”=“退出”）；}（2）创建链表模块Staticvoidcreatlist（行参）{初始化；For{接受命令；处理命令}}（3）输出链表信息模块staticvoidPrntList(参数){定义变量并初始化；输出命令；}（4）删除结点也就是出队模块st

7、aticvoidStatGame(参数){定义变量并初始化；While{开始报数；输出结果；}}21三、算法设计1．主要设计思想设立一个标签，值为1执行循环语句，值为0跳出循环。循环语句里的for循环实现报数功能，也就是结点移动的功能，移动ikey个结点，再删除第ikey个结点，并把该结点的密码值赋给ikey，再从该结点的下一个结点移动，重复上面的过程，结点全都删除后使标签的值为0，结束while循环，游戏结束。2．算法流程示意图1)主函数程序算法流程图开始输入n，m创建单循环链表输出链表信息开始游戏输入aa=1？结束否是212)创建单循环链表函数流程图

8、开始i<=n?输入每人所持有的密码创建结点结束是否3)删除结点函数（出列函数）程