约瑟夫环程序设计报告书

1、精品附件4:课程设计报告书数据结构课程设计报告约瑟夫（Joseph ） 环组别 第七组组长组成员成绩指导教师计算机科学与技术系welcome精品2014年6月11日摘要约瑟夫环问题是典型的线性表的应用实例，其开发主要包括后台数据库的建立 和维护以及前端应用程序的开发两个方面。 对于前者要求建立起数据一致性和完 整性强、数据安全性好的库。而对于后者则要求应用程序功能完备，易使用等特 点。经过分析，我们使用 MICROSOFT公司的Microsoft Visual C+6.0 开发工 具，利用其提供的各种面向对象的开发工具， 尤其是数据窗口这一能方便而简洁 操作数据库的智能化对象，首先在短时间内建

2、立系统原型，然后，对初始原型系 统进行需求迭代，不断修正和改进，直到形成用户满意的可行系统。关键词：单循环链表；c语言；约瑟夫环；序言数据结构是研究数据元素之间的逻辑关系的一门课程， 以及数据元素及其关系 在计算机中的存储表示和对这些数据所施加的运算。 该课程设计的目的是通过课 程设计的综合训练，培养分析和编程等实际动手能力，系统掌握数据结构这门课 程的主要内容。本次课程设计的内容是用单循环链表模拟约瑟夫环问题，循环链表是一种首尾 相接链表，其特点是无须增加存储容量，仅对表的链接方式稍作改变，使表处理 更加灵活，约瑟夫环问题就是用单循环链表处理的一个实际应用。通过这个设计实例，了解单链表和单循

3、环链表的相同与不同之处， 进一步加深对链表结构类型 及链表操作的理解。通过该课程设计，能运用所学知识，能上机解决一些实际问题，了解并初步掌welcome精品握设计、实现较大程序的完整过程，包括系统分析、编码设计、系统集成、以及 调试分析，熟练掌握数据结构的选择、设计、实现以及操作方法，为进一步的应 用开发打好基础。章节安排摘要、序言1一、问题描述1、课程设计目的42、课程设计任务4二、设计过程1、设计思想（数据结构）42、设计表示（函数说明）53、详细设计（主要算法）64、用户手册（使用说明）6三、测试报告1、测试用例6welcome精品2、测试结果63、分析探讨7四、总结10五、附录（源程序

4、）10六、参考文献 16welcome精品章节安排：一、问题描述1、课程设计目的1 .掌握单向循环链表的建立。2 .掌握单向循环链表的操作。2、课程设计任务编号是1,2,的,nn个人按照顺时针方向围坐一圈，每个人只有一个密码（正 整数）。一开始任选一个正整数作为报数上限值 m,从第一个仍开始顺时针方向自 1开始顺序报数，报到m时停止报数。报m的人出列,将他的密码作为新的m值, 从他在顺时针方向的下一个人开始重新从 1报数，如此下去，直到所有人全部出列 为止。请设计一个程序求出出列顺序。1 .利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各个人的编号。2 .输入数据：建立输入函数处理输入

5、的数据，输入m的初值n,输入每个人的密码, 建立单向循环链表。3 .输出形式：建立一个输出函数，将正确的出列顺序输出。二、设计过程1、设计思想（数据结构）首先，设计实现 瑟夫环问题的存储结构。由于约瑟夫环本身具有循环性质，考 虑采用循环链表，为了统一对表中任意节点的操作，循环链表不带头结点。循环链表的结点定义为如下结构类型：welcome精品struct Lnode /*定义链表 */(int number;int password;struct Lnode *next;Lnode,*p,*q,*head;其次，建立一个不带头结点的循环链表并由头指针first指示。最后，设计约瑟夫环问题的算法

6、。2、设计表示(函数说明)1、循环链表抽象数据类型定义struct Lnode /* 定义链表 */(int number;int password;struct Lnode *next;Lnode,*p,*q,*head;2、本程序包含一下几个模块(1)创建单链表for(i=1;i<=n;i+) /*建立单链表 */welcome精品(if(i=1)(head=p=(structLnode*)malloc(sizeof(struct Lnode);)else(q=(struct Lnode*)malloc(sizeof(struct Lnode);p->next=q;p=q;)(

7、3)形成循环链表p->next=head; /*形成循环链表*/(4)主函数模块int main ()3、详细设计(主要算法)welcome精品4、用户手册（使用说明）正确的执行完程序后，进去程序显示屏。首先按任意键继续，然后输入初始密码，紧接着输入测试人的数量n,其次依次输入测试人的密码，最后输入报数 上限值m ,完成后将进行结果的输出。三、测试报告1、测试用例.测试数据：m的初值为20,n=7,7个人的密码依次为3,1,7,2,4,7,4,首先m=6, 则正确的输出是什么？2、测试结果welcome精品约瑟夫环程序设计f H7须告奉勖邦德的荣谭r?码前密为人3 1 7 Z 4 7 4

8、 7倒珥酗码酗耐酗ni密密密密密密密3 hJhu.hJ.hyhHJ.hHJ.hdJ- AAAAAA61:m 4/N 人12 3 4567字 7) 避第第第第第第第戴:&靛 正测入人人人人人人人日13、分析与探讨无论是用链表实现还是用数组实现都有一个共同点：要模拟整个游戏过程，不仅程序写起来比较烦，而且时间复杂度高达O(nm),当n, m非常大(例如上百万，上千万)的时候，几乎是没有办法在短时间内出结果的。我们注意到原问题仅仅是要求出最后的胜利者的序号，而不是要读者模拟整个过程。因此如果要追求效率，就要打破常规，实施一点数学策略。为了讨论方便，先把问题稍微改变一下，并不影响原意：问题描述

9、：n个人(编号0(n-1),从0开始报数，报到m-1的退出welcome精品,剩下的人继续从0开始报数。求胜利者的编号。我们知道第一个人（编号一定是（m-1）%n）出列之后，剩下的n-1个人组 成了一个新的约瑟夫环（以编号为k=m%n的人开始）：k k+1 k+2 . n-2, n-1,0, 1,2, . k-2并且从k开始报0。现在我们把他们的编号做一下转换：k -> 0k+1 -> 1k+2 -> 2.k-3 -> n-3k-2 -> n-2序列 1 : 0, 1,2, 3 n-2, n-1序列 2: 0, 1,2, 3 k-2, k,，n-2, n-1序列

10、3 : k, k+1, k+2, k+3,，n-2, n-1, 1,2,3,k-2,序列 4: 0, 1,2, 3 ，5, 6, 7, 8,，n-3, n-2变换后就完完全全成为了（n-1）个人报数的子问题，假如我们知道这个子问题的解：例如x是最终的胜利者，那么根据上面这个表把这个x变回去不刚好就是n个人情况的解吗？ ！ ！变回去的公式很简单，相信大家都可以推 出来：k=m%n;welcome精品x' = x+k = x+ m%n ; 而 x+ m%n 可能大于 nx'= (x+ m%n)%n = (x+m)%n得至U x ' =(x+m)%n如何知道(n-1)个人报数

11、的问题的解？对，只要知道(n-2)个人的解就行 了。(n-2)个人的解呢？当然是先求(n-3)的情况-这显然就是一个倒推问 题！好了，思路出来了，下面写递推公式：令f表示i个人玩游戏报m退出最后胜利者的编号，最后的结果自然是 fn.递推公式：f1=0;fi=(fi-1+m)%i; (i>1)有了这个公式，我们要做的就是从1-n顺序算出f的数值，最后结果是 fn o我们输出fn由于是逐级递推，不需要保存每个，程序也是异常简单： (注意编号是0 - n-1)#include <stdio.h>int main(void)int n, m, i, s=0;printf ("

12、;N M =");scanf("%d%d", &n, &m);for (i=2; i<=n; i+)s=(s+m)%i;welcome精品printf ("The winner is %dn", s);return 0 ;)时间复杂度为O(n),相对于模拟算法已经有了很大的提高。算 n, m等 于一百万，一千万的情况不是问题了。可见，适当地运用数学策略，不仅可 以让编程变得简单，而且往往会成倍地提高算法执行效率。参照上面提供的思路，我认为可以类似的得到一个更易于明白的方法， 设有(1,2,3,，k-1 , k, k+1 ,

13、，n) n个数，当k出列时，那么 有k+1 ->1k+2 ->2n ->n-k1 ->n-k+1 . .k-1 ->n-1由上面一组式子可以推出，若知道新产生的 n-1个数中某个数x,那么 很显然可以推出x在原数列里的位置，即x ' = (x+k ) %n,由此，我们可以 得到一个递推公式f1=1welcome精品fn=(fn-1+k)%n(n>1 )如果你认为上式可以推出约瑟夫环问题的解，很不幸，你错了，上面的递推公式中，在某种情况下，fn-1+k 会整除n,如n=2 , k=3 ,这时我们修要对上式进行修正，fn=(fn-1+k)%n;if(fn

14、=0)fn=n;问题得解。程序代码如下：#include<stdio.h>int main()int n,k,s=1;scanf("%d%d”,&n,&k);for(int i=2;i<=n;i+=1)s=(s+k)%i;if(s=0)s=i;printf("ans=%dn",s);return 0;当然，我们还可以用递归方法解决此问题：#include<stdio.h>int main()welcome精品(int jos(int n,int k);int n,k,s;scanf("%d%d",&

15、amp;n,&k);s=jos(n,k);printf("ans=%dn",s);return 0;)int jos(int n,int k)(int x;if(n=1)x=1;else x=(jos(n-1,k)+k)%n;if(x=0)x=n;return x;四、总结我的这次数据结构课程设计的题目是：约瑟夫环，通过对该题目 的设计，我加深了对数据结构及存储结构的理解，进一步地理解和掌握 了课本中所学的各种数据结构，尤其是对单循环链表上基本运算的实 现，学会了如何把学到的知识用于解决实际问题，锻炼了自己动手的能 力。通过这次数据结构课程设计，我感受最深的就是对于

16、循环链表welcome精品的使用，可以说对循环链表有了比以前更进一步的认识，以前只是一知半解的，如果只给个题目自己根本不能把程序完整地编写出来，所以这次课程设计最大的收获就在于对循环链表有了一定的理解，包括其中的一系列操作，如建立一个循环链表，删除链表中的一个结点， 增加一个结点等。在调试程序的时候我也有所体会，虽然约瑟夫环问题不是很难，但调试的时候还是会出现很多错误，因此我们不能认为容易就不认真对待。在以后的学习中，要能不断发现问题，提出问 题，解决问题，从不足之处出发，在不断学习中提高自己。 两周的 课程设计很短暂，但其间的内容是很充实的，在其中我学习到了很多 平时书本中无法学到的东西，积

17、累了经验，锻炼了自己分析问题，解 决问题的能力，并学会了如何将所学的各课知识融会，组织起来进行 学习，总而言之这两周中我学到很多，受益匪浅。五、附录（源程序）#include<stdio.h>#include<stdlib.h>#include<windows.h>#include "string.h"struct Lnode /* 定义链表 */welcome精品(int number;int password;struct Lnode *next;Lnode,*p,*q,*head;int main(void)(system(&quo

18、t;color 0a");system("titleO。邦德的荣耀。");printf(" n");printf(" ，n");printf("”n");printf("n");welcome精品printf（" ，n"）;printf（" 方printf（" "n"）;int n; /n 个人int i; int m; /初始报数上限值int j, k, s, u;char ch;char mima100="007

19、"char input100;printf（" 约瑟夫环程序设计nn"）;printf（"007倾 情 奉 献nn"）;printf（"O 。邦德的荣耀邦德的荣耀nn"）;printf（"密码为 007n"）;/system（"pause"）;welcome精品for(k=0,s=3;k<=2;k+,s-)(printf("请输入密码：n");gets(input);if(strcmp(mima,input)=0)/ 比较字符串 mima 和 input 的大

20、小，此时相等(printf("密码正确!n");break;else(printf("密码错误，你还有d次机会n”,s-1);while(s=1)(return 0;welcome精品for(u=0;u+)/ 套上for循环以判断是否继续进行(printf("输入测试人的数量n:"); /*输入测试人的数量*/scanf("%d",&n);loop:if(n<=0) /*检验n是否满足要求，如不满足重新输入n值*/(printf("n n 是错的!n'n");printf("

21、;请再次输入 n:");scanf("%d",&n);goto loop;for(i=1;i<=n;i+) /* 建立单链表 */(if(i=1)(head=p=(struct Lnode*)malloc(sizeof(structLnode);welcome精品else(q=(struct Lnode*)malloc(sizeof(struct Lnode);p->next=q;p=q;printf("请输入第%d个人的密码：",i); /*输入每个人所持有的密码值*/scanf("%d”,&(p->password);p->number=i;p->next=head; /*形成循环链表*/p=head;printf("请输入数字 m:");scanf("%d",&m);printf("密码是:")；for (j=1;j<=n;j+) /*输出各人的编号*/(for(i=1;i<m;i+,p=p->next);welcome精品m=p->