湖南商学院
数据结构与算法
课程设计
题    目
约瑟夫双向生死游戏
学生姓名
梁子嫣
学    号
140920043
学    院
计算机工程与信息学院
专业班级
计科1402
指导教师
蒋伟进
职    称
教授
2016年
6月
26日源代码1080p在线
               

2.2系统图形说明    3
附录    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步；

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。