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

湖南商学院
数据结构与算法
课程设计

题 目
约瑟夫双向生死游戏
学生姓名
梁子嫣
学 号
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;i<num;i++)
{
node* pNext = (node*)malloc(sizeof(node));
pNext->value = 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; i<num1 - 1;i++)
{
p = p->next;
}
//删除顺时针时的节点
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; i<num2 -1;i++)
{
s = s->left;
}
//删除逆时针时的节点
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;i<num;i++)
{
node* pNext = (node*)malloc(sizeof(node));
pNext->value = 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; i<num1 - 1;i++)
{
p = p->next;
}
//删除顺时针时的节点
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; i<num2 -1;i++)
{
s = s->left;
}
//删除逆时针时的节点
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;
} 目　录
第一章 可行性研究报告概述 1
1.1项目名称 1
1.2项目承担单位 1
1.3项目建设地点 1
1.4可研报告编制单位 1
1.5项目概述及主要经济技术指标 1
第二章 编制目的、依据、原则和范围 5
2.1编制目的 5
2.2编制依据 5
2.3编制原则 5
2.4可行性研究的范围 6
第三章 建设的必要性 7
3.1符合国家“十一五”规划纲要和循环经济要求 7
3.2环境保护和节能降耗的需要 8
3.3企业可持续发展的需要 9
第四章 项目建设条件 10
4.1主体工程概况 10
4.2厂址选择 12
4.3公用设施及社会依托条件 12
第五章 改造规模与产品方案 15
5.1改造规模 15
5.2生产方案 15
第六章 生产设备节电技改方案 16
6.1企业能耗现状分析 16
6.2改造设备运行参数 16
6.3技术方案、设备方案 17
6.4项目建议改造方案 22
6.5消耗定额 25
6.6小结 25
第七章 项目实施机构和项目法人 28
7.1项目实施机构 28
7.2项目法人 28
第八章 环境保护 28
第八章 环境保护 29
第九章 社会经济效益 31
9.1环境效益 31
9.2社会效益 31
第十章 节约和合理利用能源 33
10.1节能依据及标准 33
10.2节能设计原则 33
10.3能耗分析 33
10.4节能措施及节能效果分析 34
第十一章 环境安全与劳动保护 35
11.1安全 35
11.2劳动保护 36
第十二章 生产管理与人员编制 38
12.1生产管理 38
12.2人员编制 38
第十三章 项目实施进度 39
13.1 建设工期 39
13.2 项目实施时期各阶段进度建议 39
第十四章 项目招标方案 41
第十五章 投资估算及资金筹措 42
15.1投资估算 42
15.2资金筹措 43
第十六章 经济评价 44
16.1项目周期 44
16.2成本参数 44
16.3损益类参数 44
16.4经济评价结果 45
第十七章 结论 47
17.1结论意见及总的评价、存在的问题和建议 47