约瑟夫生死游戏课程设计(含源代码可以运行)约瑟夫生死游戏课程设计(含源代码可以运行)
题 目 约瑟夫双向生死游戏 学生姓名 梁子嫣 学 号 140920043 学 院 计算机工程与信息学院 专业班级 计科1402 指导教师 蒋伟进 职 称 教授
2016年 6月 26日
目录
第一章 需求分析 ................................................... 3 1.1课程设计要求 .................................................. 3 1.2课程设计目标与总体方案 .....
约瑟夫生死游戏课程
(含源代码可以运行)
题 目 约瑟夫双向生死游戏 学生姓名 梁子嫣 学 号 140920043 学 院 计算机工程与信息学院 专业班级 计科1402 指导教师 蒋伟进 职 称 教授
2016年 6月 26日
目录
第一章 需求分析 ................................................... 3 1.1课程设计要求 .................................................. 3 1.2课程设计目标与总体
........................................ 3 1.3程序执行的命令 ...............................错误~未定义书签。
第二章 算法描述 ................................................... 4 2.1算法描述 .....................................错误~未定义书签。
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 系统图形说明
约瑟夫生死游戏
构建确定更新输入输出链表n值链表
第三章 系统的设计
3.1 创建双向循环链表;
node* createList(int num)
{
node* head = (node*)malloc(sizeof(node));
head->value = 1;
node* p = head;
for(int i = 1;i
value = i+1;
p->next = pNext;
pNext->left = p;
p = pNext;
}
>next = head; p-
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));
>value = 1; head-
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;
}
本文档为【约瑟夫生死游戏课程设计(含源代码可以运行)】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑,
图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。