约瑟夫生死游戏课程设计(含源代码可以运行) (1)

122839855 贡献于2018-06-08

作者 Microsoft  创建于2018-06-07 07:56:00   修改者陈  修改于2018-06-07 07:56:00字数3368

文档摘要: 约瑟夫双向生死游戏是在约瑟夫生者死者游戏的基础上,正向计数后反向计数,然后再正向计数。具体描述如下:30个旅客同乘一条船,因为严重超载,加上风高浪大,危险万分;因此船长告诉乘客,只有将全船一半的旅客投入海中,其余人才能幸免遇难。无奈,大家只得同意这种办法,并议定30个人围成一圈,由第一个人开始,顺时针依次报数,数到第9人,便把他投入大海中,然后从他的下一个人数起,逆时针数到第5人,将他投入大海,然后从他逆时针的下一个人数起,顺时针数到第9人,再将他投入大海,如此循环,直到剩下15个乘客为止。问哪些位置是将被扔下大海的位置。
关键词:

 湖南商学院 数据结构与算法 课程设计  题 目 约瑟夫双向生死游戏 学生姓名 梁子嫣 学 号 140920043 学 院 计算机工程与信息学院 专业班级 计科1402 指导教师 蒋伟进 职 称 教授 2016年 6月 26日 目录 第一章 需求分析 1 1.1课程设计要求 1 1.2课程设计目标与总体方案 1 1.3程序执行的命令 1 第二章 算法描述 2 2.1算法描述 2 2.2系统图形说明 3 第三章 系统的设计 4 3.1创建双向链表 4 3.2约瑟夫算法 4 3.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(i<=n/2) //删除一半的结点 {从p指向的结点沿链前进m-1步; 删除第m个结点(q所指向的结点); p指向q的下一个结点; 输出其位置q->data; 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(peopleOfNow>alivePepole) { //找到顺时针要删除节点的前一节点p for(int i =1; inext; } //删除顺时针时的节点 node* toBeDeleted = p->next; printf("deadman = %d\n",toBeDeleted->value); node* nextToDeleted = toBeDeleted->next; p->next = nextToDeleted; nextToDeleted->left = p; free(toBeDeleted); peopleOfNow--; if(peopleOfNow>alivePepole) //防止不需要再删除节点了,所以要先判断 { //找到逆时针时要删除节点的前一节点 node* s = nextToDeleted; for(int i =1; ileft; } //删除逆时针时的节点 node* tobeDeleted = s->left; printf("deadman = %d\n",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(peopleOfNow>alivePepole) { //找到顺时针要删除节点的前一节点p for(int i =1; inext; } //删除顺时针时的节点 node* toBeDeleted = p->next; printf("deadman = %d\n",toBeDeleted->value); node* nextToDeleted = toBeDeleted->next; p->next = nextToDeleted; nextToDeleted->left = p; free(toBeDeleted); peopleOfNow--; if(peopleOfNow>alivePepole) //防止不需要再删除节点了,所以要先判断 { //找到逆时针时要删除节点的前一节点 node* s = nextToDeleted; for(int i =1; ileft; } //删除逆时针时的节点 node* tobeDeleted = s->left; printf("deadman = %d\n",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; }

下载文档到电脑,查找使用更方便

文档的实际排版效果,会与网站的显示效果略有不同!!

需要 10 金币 [ 分享文档获得金币 ] 0 人已下载

下载文档