湖南大众传媒学院网络传媒系《算法与数据结构》课程设计报告姓名：班级：学号：指导教师：年月日课程设计综合成绩评定设计题目一：约瑟夫生者死者游戏考核项目分值AC得分设计情况（共70分）设计工作量与难度20设计工作量大与设计有一定难度设计工作量与难度一般，基本达到了要求设计方案15设计方案正确、合理设计方案较正确、基本合理，但不是最优设计完成情况35完成了选题的设计内容，设计功能完整，相关算法设计正确，程序结果正确、直观性好基本完成了选题的设计内容及主要选题功能，相关算法设计基本正确，程序结果正确设计报告（共15分）报告组织结构及内容10内容组织及结构合理、内容充实、层次清晰、图表得当内容组织及结构较合理、内容较充实、层次较清晰、图表应用基本得当报告排版格式5格式规范，完全符合要求格式基本规范，基本符合要求设计态度（共15分）15设计态度认真、积极设计态度比较认真综合得分课程设计综合成绩（折合为优、良、中、及格与不及格计）其它说明：目录TOC\o"1-3"\h\z\uHYPERLINK\l"_Toc185566256"1.约瑟夫生者死者游戏PAGEREF_Toc185566256\h1HYPERLINK\l"_Toc185566257"1.1项目简介PAGEREF_Toc185566257\h1HYPERLINK\l"_Toc185566258"1.2设计思路PAGEREF_Toc185566258\h1HYPERLINK\l"_Toc185566259"1.3数据结构PAGEREF_Toc185566259\h2HYPERLINK\l"_Toc185566260"1.4运行结果PAGEREF_Toc185566260\h2HYPERLINK\l"_Toc185566266"2.总结与分析PAGEREF_Toc185566266\h4HYPERLINK\l"_Toc185566267"附录PAGEREF_Toc185566267\h5HYPERLINK\l"_Toc185566269"附录约瑟夫生者死者游戏程序源代码PAGEREF_Toc185566269\h51.约瑟夫生者死者游戏1.1项目简介约瑟夫生者死者游戏的大意是：30个旅客同乘一条船，因为严重超载，加上风高浪大，危险万分；因此船长告诉乘客，只有将全船一半的旅客投入海中，其余人才能幸免遇难。无奈，大家只得同意这种办法，并议定30个人围成一圈，由第一个人开始，依次报数，数到第9人，便把他投入大海中，然后从他的下一个人数起，数到第9人，再将他投入大海，如此循环，直到剩下15个乘客为止。问哪些位置是将被扔下大海的位置。1.2设计思路本游戏的数学建模如下：假设n个旅客排成一个环形，依次顺序编号1，2，…，n。从某个指定的第1号开始，沿环计数，每数到第m个人就让其出列，且从下一个人开始重新计数，继续进行下去。这个过程一直进行到剩下k个旅客为止。本游戏的要求用户输入的内容包括：1.旅客的个数，也就是n的值；2.离开旅客的间隔数，也就是m的值；3.所有旅客的序号作为一组数据要求存放在某种数据结构中。本游戏要求输出的内容是包括1.离开旅客的序号；2.剩余旅客的序号；所以，根据上面的模型分析及输入输出参数分析，可以定义一种数据结构后进行算法实现。1.3数据结构为了解决这一问题，可以用长度为30的数组作为线性存储结构，并把该数组看成是一个首尾相接的环形结构，那么每投入大海一个乘客，就要在该数组的相应位置做一个删除标记，该单元以后就不再作为计数单元。这样做不仅算法较为复杂，而且效率低，还要移动大量的元素。用单循环链表解决这一问题，实现的方法相对要简单得多。首先要定义链表结点，单循环链表的结点结构与一般的结点结构完全相同，只是数据域用一个整数来表示位置；然后将它们组成具有30个结点的单循环链表。接下来从位置为1的结点开始数，数到第8个结点，就将下一个结点从循环链表中删去，然后再从删去结点的下一个结点开始数起，数到第8个结点，再将其下一个结点删去，如此进行下去，直到剩下15个结点为止。为了不失一般性，将30改为一个任意输入的正整数n，而报数上限（原为9）也为一个任选的正整数k。这样该算法描述如下：(1)创建含有n个结点的单循环链表；(2)生着与死者的选择：p指向链表的第一个结点，初始i置为1；while(i<=n/2)//删除一半的结点｛从p指向的结点沿链前进k-1步；删除第k个结点（q所指向的结点）；p指向q的下一个结点；输出其位置q->data;