约瑟夫生死游戏课程设计

计算机学院信息管理与信息系统专业《程序设计综合课程设计》报告（2010/2011学年第一学期）学生姓名：学生班级：学生学号：指导教师：2011年01月04日I目录第一章需求分析.....................................................11.1课程设计目的..................................................11.2课程设计要求..................................................11.3课程设计目标与总体方案........................................11.4程序执行的命令................................................1第二章系统的功能...................................................22.1系统功能说明..................................................22.2系统功能解析..................................................2第三章系统的设计...................................................33.1JOSPHU链表的实现...............................................33.2循环链表......................................................33.3对程序的各个部分的详细介绍....................................33.3.1利用类定义构造成员函数以及成员.............................33.3.2定义成员函数..............................................43.3.3创建含有n个结点的单循环链表...............................53.3.4Josephu操作...............................................53.3.5主函数.....................................................63.4程序的流程....................................................7第四章程序的运行结果图.............................................84.1开始运行程序..................................................84.2先键入参加游戏的人数及报数间隔................................84.3按空格键运行程序..............................................9第五章总结........................................................10致谢...............................................................11附录一参考文献....................................................12附录二程序源代码..................................................13程序设计综合课程设计1约瑟夫生死游戏第一章需求分析1.1课程设计目的课程设计目的是为学生提供了一个既动手又动脑，独立实践的机会，将课本上的理论知识和实际有机的结合起来，锻炼学生的分析解决实际问题的能力。提高学生适应实际，实践编程的能力。通过实践让学生理论和实际操作相结合，更好的理解书面知识，并在巩固的基础上融会所学认识。1.2课程设计要求约瑟夫生死游戏：30个人围成一个圈由第一个人数起，依次报数，数到第九个人，便把他剔除，然后再从他的下一个人数起，数到第九个人，再将他剔除剩下15个乘客为止，问那些位置将是被扔下大海的位置。课程设计要求是将30个人改为n,报数（原为9），也改为任意正整数。根据得到的初始数据得到生者和死者的位置编号并输出。1.3课程设计目标与总体方案本实验设计的目标是运用循环链表来解决Josephu环问题，其中运用了许多链表中的基本操作使改程序能不只解决一个Josephu的简单链表，其中的Josephu函数则是用于，运用C++程序编写程序，实现队列的建立、插入和删除基本功能，在程序设计成功的基础上，进一步深化理解队列的作用和实现原理。1.4程序执行的命令构造链表、输入数据、执行报数输出出列人的序号结束。程序设计综合课程设计2第二章系统的功能2.1系统功能说明约瑟夫生死游戏确定n值更新链表输入输出构建链表图1系统功能程序图2.2系统功能解析如上图所示，本系统分为五个功能模块分别为：构建链表，确定n值，更新链表，输入，输出。下面就每个功能进行详细说明：（1）构建约瑟夫链表：使整个游戏在链表中运行，使得结点在删除时不需要移动大量的结点；（2）确定n的值：进而使链具化体，从而可以构建一个具体的链表；（3）更新链表：对剔除结点后的链表进行重新连接又，有构成了一个新的链表，使得循环继续进行；（4）输入：输入n的值进行链表具体化，输入间隔值m，使得间隔被确定，程序得以有效正确的进行；（5）输出：输出要剔除的结点的数值。程序设计综合课程设计3第三章系统的设计3.1Josphu链表的实现Josphu链表——链式表示和实现约瑟夫（Josephu）问题：已知N个人围坐在一张圆桌周围（不妨以1，2，……，N对每一个人依次编号），现在先从序号为K的人开始报数，数到m的那个人出列，他的下一个人又从1开始数，报数到m的人出列……直到所有人都出出列为止。给出出列的顺序。3.2循环链表队列的顺序表示和实现和顺序栈相似，在队列的顺序存储结构中，除了用一组地址连续的存储单元依次存放从队列头到队列尾的元素之外，尚需附设两个指针front和rear分别指示队列头元素及队列尾元素的位置。为了C语言中描述方便起见，在此我们约定，初始化建空队列时，令front=rear=0,每当插入新的队列尾元素时，“尾指针增1”；每当删除队列头元素时，“头指针增1”。因此，在非空队列中，头指针始终指向队列头元素，而尾指针始终指向队列尾元素的下一个位置从上述分析可见，在C++中不能用动态分配的一维数组来实现循环队列。如果用户的应用程序中设有循环队列，则必须为它设定一个最大队列长度；若用户无法预估所用队列的最大长度，则宜采用链队列。3.3对程序的各个部分的详细介绍编写本实验设计程序采用C++进行，在Visualc++6.0环境下运行。3.3.1利用类定义构造成员函数以及成员templateclassTclassList{public:List(){first=newLinkNodeT;first-link=first;}List(Tx){first=newLinkNodeT(x);first-link=first;}程序设计综合课程设计4List(ListT&L);~List(){}voidInsert(inti,Tx);TgetHead(){returnfirst-data;}LinkNodeT*getfirst(){returnfirst;}voidxiuf(LinkNodeT*a){first=a;}LinkNodeT*Locate(inti);protected:LinkNodeT*first;};3.3.2定义成员函数templateclassTListT::List(ListT&L){Tvalue;LinkNodeT*srcptr=L.getHead();LinkNodeT*destptr=first=newLinkNodeT;destptr-data=srcptr-data;while(srcptr-link!=first){value=srcptr-link-data;destptr-link=newLinkNodeT(value);destptr=destptr-link;srcptr=srcptr-link;last=srcptr;}};templateclassTLinkNodeT*ListT::Locate(inti){if(i0)returnNULL;LinkNodeT*current=first;intk=1;while(ki){current=current-link;k++;if(current==first)returnNULL;}returncurrent;};程序设计综合课程设计53.3.3创建含有n个结点的单循环链表templateclassTvoidListT::Insert(inti,Tx){LinkNodeT*current=Locate(i);if(current==NULL)return;LinkNodeT*newNode=newLinkNodeT(x);if(newNode==NULL){cout存储分配错误!endl;exit(1);}newNode-link=current-link;current-link=newNode;};3.3.4Josephu操作Josephu操作为本程序的重点，在本程序中我是利用了一个Josephu函数来解决该问题的，该函数是通过不断的循环、输出、再循环、再输出直到将Josephu链表中的一半元素被输出。函数如下：templateclassTvoidJosephus(ListT&Js,intn,intm){LinkNodeT*p=Js.Locate(1),*pre;inti,j;for(i=1;i=n/2;i++){if(m==1){cout出列的人是:p-dataendl;pre=p-link;Js.xiuf(p-link);deletep;p=pre;}else{for(j=1;jm;j++){pre=p;p=p-link;}程序设计综合课程设计6cout出列的人是p-dataendl;pre-link=p-link;if(p==Js.getfirst())Js.xiuf(p-link);//if(p=Js.getlast())Js.movelast(pre);deletep;p=pre-link;}}}3.3.5主函数voidmain(){Listintclist(1);inti,n,m;cout输入游戏者的人数和报数间隔：endl;cinnm;for(i=1;in;i++){clist.Insert(i,i+1);}Josephus(clist,n,m);}程序设计综合课程设计73.4程序的流程3.4.1流程图开始输入n、m的值创建链表计数删除结点连接链表i《=n/2结束否是图2程序流程图3.4.2流程图的说明开始进入程序，先确定n的值，然后，根据n得知建立链表，然后数数，确定输出的位置，输出数，更新链表，如果剩下的数小于等于n/2,则停止程序，否则继续计数进行循环直至结束程序。程序设计综合课程设计8第四章程序的运行结果图4.1开始运行程序程序的初始化图3程序初始化4.2先键入参加游戏的人数及报数间隔输入人数和报数间隔309图4确定n值及间隔值m程序设计综合课程设计94.3按空格键运行程序