约瑟夫生死游戏(含源代码可以运行).doc

湖南商学院数据结构与算法课程设计题 目约瑟夫双向生死游戏学生姓名梁子嫣学 号140920043学 院计算机工程与信息学院专业班级计科1402指导教师蒋伟进职 称教授2016年6月26日 目录第一章 需求分析11.1课程设计要求11.2课程设计目标与总体方案11.3程序执行的命令1第二章 算法描述22.1算法描述22.2系统图形说明3第三章 系统的设计43.1创建双向链表43.2约瑟夫算法43.4主函数6第四章 程序的运行结果图7附录8约瑟夫生死游戏第一章 需求分析1.1项目简介 约瑟夫双向生死游戏是在约瑟夫生者死者游戏的基础上，正向计数后反向计数，然后再正向计数。具体描述如下：30个旅客同乘一条船，因为严重超载，加上风高浪大，危险万分；因此船长告诉乘客，只有将全船一半的旅客投入海中，其余人才能幸免遇难。无奈，大家只得同意这种办法，并议定30个人围成一圈，由第一个人开始，顺时针依次报数，数到第9人，便把他投入大海中，然后从他的下一个人数起，逆时针数到第5人，将他投入大海，然后从他逆时针的下一个人数起，顺时针数到第9人，再将他投入大海，如此循环，直到剩下15个乘客为止。问哪些位置是将被扔下大海的位置。1.2设计思路 本游戏的数学建模如下：假设n个旅客排成一个环形，依次顺序编号1，2，n。从某个指定的第1号开始，沿环计数，数到第m个人就让其出列，然后从第m+1个人反向计数到m-k+1个人，让其出列，然后从m-k个人开始重新正向沿环计数，再数m个人后让其出列，然后再反向数k 个人后让其出列。这个过程一直进行到剩下q个旅客为止。本游戏的要求用户输入的内容包括：1. 旅客的个数，也就是n的值；2. 正向离开旅客的间隔数，也就是m的值；3. 反向离开旅客的间隔数，也就是k的值；4. 所有旅客的序号作为一组数据要求存放在某种数据结构中。本游戏要求输出的内容是包括1. 离开旅客的序号；2. 剩余旅客的序号；所以，根据上面的模型分析及输入输出参数分析，可以定义一种数据结构后进行算法实现。第二章 系统的功能2.1 系统文字描述(1) 创建含有n个结点的双向循环链表；(2) 生着与死者的选择：p指向链表的第一个结点，初始i置为1；while(idata;i自增1；从p指向的结点沿链后退k-1步；删除第k个结点（q所指向的结点）；p指向q的上一个结点；输出其位置q-data;i自增1；(3) 输出所有生者的位置。2.2 系统图形说明第三章 系统的设计3.1 创建双向循环链表；node* createList(int num) node* head = (node*)malloc(sizeof(node); head-value = 1; node* p = head; for(int i = 1;ivalue = i+1; p-next = pNext; pNext-left = p; p = pNext; p-next = head; head-left = p; return head; 3.2 生者与死者的选择int deleteList(node* head, int num1,int num2,int totalPeople,int alivePepole)/num1代表顺时针数 num2代表逆时针数 node* p = head; int peopleOfNow = totalPeople; while(peopleOfNowalivePepole) /找到顺时针要删除节点的前一节点p for(int i =1; inext; /删除顺时针时的节点 node* toBeDeleted = p-next; printf(deadman = %dn,toBeDeleted-value); node* nextToDeleted = toBeDeleted-next; p-next = nextToDeleted; nextToDeleted-left = p; free(toBeDeleted); peopleOfNow-; if(peopleOfNowalivePepole) /防止不需要再删除节点了，所以要先判断 /找到逆时针时要删除节点的前一节点 node* s = nextToDeleted; for(int i =1; ileft; /删除逆时针时的节点 node* tobeDeleted = s-left; printf(deadman = %dn,tobeDeleted-value); node* leftToBeDeleted = tobeDeleted-left; s-left = leftToBeDeleted; leftToBeDeleted-next = s; free(tobeDeleted); peopleOfNow-; p = leftToBeDeleted; return 0; 3.3 主函数 int main() node* head = createList(30); deleteList( head, 9,5,30,15); return 0; 第四章 程序运行结果附录 源代码#include stdio.h #include stdlib.h struct node int value; node* left; node* next; Node; /创建双向的循环链表 node* createList(int num) node* head = (node*)malloc(sizeof(node); head-value = 1; node* p = head; for(int i = 1;ivalue = i+1; p-next = pNext; pNext-left = p; p = pNext; p-next = head; head-left = p; return head; int deleteList(node* head, int num1,int num2,int totalPeople,int alivePepole)/num1代表顺时针数 num2代表逆时针数 node* p = head; int peopleOfNow = totalPeople; while(peopleOfNowalivePepole) /找到顺时针要删除节点的前一节点p for(int i =1; inext; /删除顺时针时的节点 node* toBeDeleted = p-next; printf(deadman = %dn,toBeDeleted-value); node* nextToDeleted = toBeDeleted-next; p-next = nextToDeleted; nextToDeleted-left = p; free(toBeDeleted); peopleOfNow-; if(peopleOfNowalivePepole) /防止不需要再删除节点了，所以要先判断 /找到逆时针时要删除节点的前一节点 node* s = nextToDeleted; for(int i =1; ileft; /删除逆时针时的节点 node* tobeDeleted = s-left; printf(deadman = %dn,tobeDeleted-value); node* leftToBeDeleted = tobeDeleted-left; s-left = leftToBeDeleted; leftToBeDeleted-next = s; free(tobeDeleted); peopleOfNow-; p = leftToBeDeleted; return 0; int main() node* head = createList(30); deleteList( head, 9,5,30,15); return 0; 目录第一章 可行性研究报告概述11.1项目名称11.2项目承担单位11.3项目建设地点11.4可研报告编制单位11.5项目概述及主要经济技术指标1第二章 编制目的、依据、原则和范围52.1编制目的52.2编制依据52.3编制原则52.4可行性研究的范围6第三章 建设的必要性73.1符合国家“十一五”规划纲要和循环经济要求73.2环境保护和节能降耗的需要83.3企业可持续发展的需要9第四章 项目建设条件104.1主体工程概况104.2厂址选择124.3公用设施及社会依托条件12第五章 改造规模与产品方案155.1改造规模155.2生产方案15第六章 生产设备节电技改方案166.1企业能耗现状分析166.2改造设备运行参数166.3技术方案、设备方案176.4项目建议改造方案226.5消耗定额256.6小结25第七章 项目实施机构和项目法人287.1项目实施机构287.2项目法人28第八章 环境保护28第八章 环境保护29第九章 社会经济效益319.1环境效益319.2社会效益31第十章 节约和合理利用能源3310.1节能依据及标准3310.2节能设计原则3310.3能耗分析3310.4节能措施及节能效果分析34第十一章 环境安全与劳动保护3511.1安全3511.2劳动保护36第十二章 生产管理与人员编制3812.1生产管理3812.2人员编制38第十三章 项目实施进度3913.1 建设工期3913.2 项目实施时期各阶段进度建议39第十四章 项目招标方案41第十五章 投资估算及资金筹措4215.1投资估算4215.2资金筹措43第十六章 经济评价4416.1项目周期4416.2成本参数4416.3损益类参数4416.4经济评价结果45第十七章 结论4717.1结论意见及总的评价、存在的问题和建议47