约瑟夫生死游戏编程.doc

一：【内容与要求】约瑟夫游戏的大意是：每30 个旅客同乘一条船，因为严重超载，加之风高浪大，危（wei）险万分；因此船长告诉乘客，惟独将全船一半的旅客投入还中，其余人材干避免遇难。

无奈，大家只得允许这种办法，并议定30 个人围成一圈，由第一个人数起，挨次报数，数到第9人，便把他投入大海中，然后再从他的下一个人数起，数到第9 人，再将他扔进大海中，如此循环地进行，直到剩下15 个乘客为止。

问哪些位置是将被扔下大海的位置。

二：概要设计利用链表循环来解决。

首先，就必须先定义一个链表，按照所需要的长度进行定义，然后令其为指针指向头指针，即完成为了一个循环链表的创建。

接下来先打印链表输出。

其次，就是算法实现，需要利用指针来进行，数据域标记人员编号，先用一个指针循环查找，找到第一个需要删除的人，标记为1，先输出节点数，再进行删除。

挨次循环查找，直到被删除的节点数量为总人数的一半的时候则结束。

三：程序执行流程图否三：详细代码结构1. 链表的创建(1) 创建头节点Josephring(){head=new Node;//为头结点申请空间head->no=1;//为数据域赋值head->next=head;//形成循环链表}(2) 循环插入链表void Josephring::CreateJosephus(int n){Node*s=head;//标记头结点totalnum=n;for(int i=2;i<=n;i++){ Node*w=new Node;//新建一个节点w->no=i;w->next=head;s->next=w;s=w;//S 作为尾指针}}首先申请一个节点，并且W 指针指向它，然后从2 开始赋值，此时先令新节点的W 指针指向头结点，再令S 指针指向它，挨次循环插入创建。

2. 打印输出链表void Josephring::show(){cout<<head->no<<"\t";//先输出头节点Node*q=head->next;while(q!=head){cout<<q->no<<"\t";q=q->next;}}先打印输出头结点，然后循环判定，将不等于头结点的全部输出。

第一章问题背景约瑟夫生死游戏是一款生死抉择的游戏，由于某种原因，需要在一群人中踢出一部分人，被踢出的人将会面临死亡的威胁，因此大家都不想成为那个被踢除的那个人，但是又必须踢出一些人才能保证其他人的安全，你的位置会影响你的生死，所以位置的选择很重要。

2.1系统总需求如果有r个人，需要剔除w个人，让他们围成一个圈，由第一个人数起，依次报数，数到第s个人，便把他剔除，然后再从他的下一个人数起，数到第s 个人，再将他剔除，直至剔除了w个人时停止，没剔除的则生还。

2.2 功能需求约瑟夫生死游戏能够精确的找到死亡者的位置，并且能够灵活的确定剔除第几个人，以及要剔除多少人，并且能够对很多人的情况下迅速确定生者和死者的位置。

整个游戏主要分为几个模块：队列初始化，入队，查找死亡位置，排序，生者位置的确定，输出死者位置。

队列初始化：对队列中每个人进行初始化。

入队：对每个人进行赋值，并且进行入队操作。

查找死亡位置：通过一控制块控制入队，出队，从而找到死亡位置，并且把死亡位置保存到数组。

排序：把死亡位置按从小到大进行排序，以便观看结果。

生者位置的确定：通过已经确定的死亡位置来确定生者位置，并对生者位置进行输出。

输出死者位置:对已排序的死亡位置进行输出。

2.3 数据需求第i个人员信息=i-1;总人数；踢除第几个人；剔除人数；3.1 系统体系结构约瑟夫生死游戏通过通过一控制块控制入队，出队，找到死亡位置，从而确定生者位置。

主要包括确定死亡位置和确定生者位置。

约瑟夫的软件结构如图3.1所示。

3.2各子功能模块设计3.2.1确定死亡位置（1）功能：通过通过一控制块控制入队，出队，找到死亡位置，并保存死亡位置。

（2）程序流程图：约瑟夫生死游戏的程序流程图如图3.2所示。

3.3数据结构设计3.3.1员工信息数据结构设计人员信息包括每个人员位置对应的值，以及队头，队尾的位置。

typedef struct{DATATYPE data[maxsize];//队中元素int front,rear; //队头元素下标、队尾元素后面位置的下标} SEQQUEUE;第四章系统实现4.1人机交互部件本系统的一个重要特点就是系统启动之后，同时显示主窗口，主窗口为可用，必须在主窗口中进行赋值才可运行。

课程设计报告约瑟夫生者死者游戏学生姓名：专业：班级：学号:指导教师：2017年3月29日目录一、实验题目 (3)二、实验目的 (3)三、实验要求 (3)四、实现过程 (4)1、总体设计： (4)2、详细设计： (5)3、调试分析： (9)4、运行结果： (9)5、实验总结： (11)五、参考文献 (12)一、实验题目约瑟夫生者死者游戏二、实验目的本次课程设计的主要目的是综合运用所学的数据结构知识解决Jonsepu环问题，侧重对循环链表等相关内容的综合应用，使自己能进一步熟悉掌握数据结构的基础知识，进一步提升自己的解决问题和编程调试能力，为后续专业课程的学习打下良好的基础。

三、实验要求设计要求本游戏的数学建模如下：假设n个旅客排成一个环形，依次顺序编号1，2，…，n。

从某个指定的第1号开始，沿环计数，每数到第m个人就让其出列，且从下一个人开始重新计数，继续进行下去。

这个过程一直进行到剩下k个旅客为止。

本游戏的要求用户输入的内容包括：1. 旅客的个数，也就是n的值；2. 离开旅客的间隔数，也就是m的值；3. 所有旅客的序号作为一组数据要求存放在某种数据结构中。

本游戏要求输出的内容是包括1. 离开旅客的序号；2. 剩余旅客的序号；四、实现过程1、总体设计：1.主流程图：2.Out函数流程图2、详细设计：1.结构体typedef struct Jonse/*定义结构体*/ {int code;/*编号（分配位置）*/struct Jonse *next;}jonse;2.链表的构造函数jonse * Create(int n)/*建立n个节点的单向循环链表函数*/ {Jonse *h,*p;int i;h=(Jonse *)malloc(sizeof(Jonse));/*为头结点分配空间*/ p=h;for(i=1;i<=n;i++)/*建立n个节点的单向链表*/{p->code=i;if(i<n){p->next=(Jonse *)malloc(sizeof(Jonse));/*创建新节点*/p=p->next;}}p->next=h;/*返回头结点，完成单向循环链表的建立*/return h;}3.输出链表的函数void ShowList(Jonse *h)/*打印链表函数*/{Jonse *p;p=h;do{printf("%d\t",p->code);p=p->next;}while(p!=h);}4.实现将人剔除的函数void Out(Jonse *h,int i,int d,int s)/*出队函数*/{int c;c=s;Jonse *p,*q;int k;p=h;for(q=h;q->next!=h;q=q->next);/*初始化链表*/for(k=1;k<i;k++)/*次循环功能：设置好开始报数的人所在位置*/{q=p;p=p->next;}while(p!=p->next)/*循环删除队列结点*/{for(k=1;k<d;k++)/*数数*/{q=p;p=p->next;}printf("%d ",p->code);/*输出被踢节点的位置*/ q->next=p->next;free(p);/*释放被踢出的结点*/p=NULL;/*让p指针赋值为空指针*/p=q->next;flag++;if(num-flag==c)break;}printf("\n剩余游客的编号:\n");//free(p);/*释放被踢出的结点*/p=NULL;/*让p指针赋值为空指针*/p = h;do{printf("%d ",p->code);p=p->next;}while(p!=h);printf("\n");}3、调试分析：程序的编写和调试基本正常。

实验1约瑟夫环问题背景约瑟夫问题（Josephus Problem）据说著名犹太历史学家Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。

然而Josephus 和他的朋友并不想遵从，Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。

原题：用户输入M,N值，N个人围成一个环，从0号人开始数,数到M,那个人就退出游戏，直到最后一个人求最后一个剩下的人是几号？问题描述设编号为1-n的n(n>0)个人按顺时针方向围成一圈．首先第1个人从1开始顺时针报数．报m的人(m 为正整数)．令其出列。

然后再从他的下一个人开始，重新从1顺时针报数，报m的人，再令其出列。

如此下去，直到圈中所有人出列为止。

求出列编号序列。

基本要求需要基于线性表的基本操作来实现约瑟夫问题需要利用顺序表来实现线性表输入输出格式输入格式：n，m输出格式1：在字符界面上输出这n个数的输出序列输出格式2：将这n个数的输出序列写入到文件中测试用例（举例）输入：10，3输出：3 6 9 2 7 1 8 5 10 4课后选做内容（1）使用单链表来实现之（2）使用循环链表来实现之课后习题请以O（n）的时间复杂度来实现约瑟夫问题。

HUNAN UNIVERSITY实验报告题目：约瑟夫环问题学生姓名**学生学号***********专业班级 ******* 指导老师****完成日期****/**/**一、需求分析（1）编号为1-n的n个人按顺时针方向围成一圈．首先第1个人从1开始顺时针报数．报m的人(m 为正整数)．令其出列。

然后再从他的下一个人开始，重新从1顺时针报数，报m的人，再令其出列。

黄淮学院“数据结构”课程设计报告系（院）：计算机科学系设计题目：专业班级：小组成员：指导教师：完成时间：2009~2010学年第二学期[问题描述]约瑟夫（Joeph）问题的一种描述是：编号为1,2,…,n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。

一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。

报m 的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。

试设计一个程序求出出列顺序。

[基本要求]利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。

[测试数据]m的初值为20；密码：3，1，7，2，4，8，4（正确的结果应为6，1，4，7，2，3，5）。

[实现提示]程序运行后首先要求用户指定初始报数上限值，然后读取各人的密码。

设n≤30。

一、需求分析二、概要设计说明本程序中用到的所有抽象数据类型的定义、主程序的流程以及各程序模块之间的层次(调用)关系。

typedef struct Node{int Index; 在当前环中所处的位置，即编号int Password; 在当前环中的所带的密码struct Node *next;}JosephuNode;使用单循环链表创建约瑟夫环JosephuNode *Creat_Node(int numbers)约瑟夫环void Josephu(JosephuNode *head,int Password)三、详细设计实现概要设计中定义的所有数据类型，对每个操作只需要写出伪码算法；对主程序和其他模块也都需要写出伪码算法。

本程序主要是以建立单循环链表的形式，建立起一个约瑟夫环，然后根据之前创立的结点，输入结点里的一些数据，如下typedef struct Node{int Index; 在当前环中所处的位置，即编号int Password; 在当前环中的所带的密码struct Node *next;}JosephuNode;程序有主函数开始，首先，提示输入创建约瑟夫环环数以及每个环上所带的密码。

约瑟夫生死游戏(C++)数据结构实现本文档为约瑟夫生死游戏的C++数据结构实现文档，旨在详细介绍如何使用C++语言实现约瑟夫生死游戏的功能。

1：引言1.1 背景约瑟夫生死游戏是一个经典的数学问题，由约瑟夫·斯特恩提出。

问题描述如下：有n个人围成一圈，从某个人开始，每次顺时针报数m个人，报到m的人出局，直到剩下最后一个人为止。

1.2 目的本文档旨在指导开发人员使用C++语言实现约瑟夫生死游戏的功能，包括实现报数、出局等基本操作，并提供相应的测试样例和使用说明。

2：设计2.1 数据结构设计约瑟夫生死游戏的核心是一个环形链表，链表中的每个节点代表一个人。

每个节点包含两部分数据：该人的编号和指向下一个节点的指针。

链表的最后一个节点指向第一个节点，形成环形结构。

2.2 算法设计- 初始化链表：根据输入的人数创建相应数量的节点，并通过指针连接起来，形成环形链表。

- 报数出局：从指定的起始位置开始顺时针遍历链表，依次报数，当报到m时，将该节点从链表中移除。

- 判断游戏结束：当只剩下最后一个节点时，游戏结束。

2.3 功能设计- 初始化游戏：根据输入的人数和报数间隔，创建约瑟夫生死游戏实例。

- 开始游戏：执行报数出局操作，直到游戏结束。

- 获取胜利者：返回最后剩下的节点的编号。

3：实现下面给出C++语言实现约瑟夫生死游戏的核心代码。

```cppinclude<iostream>using namespace std;// 定义环形链表节点结构体struct Node {int id;Node next;};class JosephusGame {public:// 构造函数，初始化环形链表JosephusGame(int n, int m) {// 创建第一个节点Node firstNode = new Node;firstNode->id = 1;firstNode->next = NULL;// 依次连接剩余节点Node prevNode = firstNode;for (int i = 2; i <= n; i++) { Node newNode = new Node; newNode->id = i;newNode->next = NULL;prevNode->next = newNode;prevNode = newNode;}// 最后一个节点和第一个节点，形成环形结构prevNode->next = firstNode;// 初始化成员变量this->head = firstNode;this->count = n;this->interval = m;}// 游戏主循环void playGame() {Node currentNode = this->head;while (this->count > 1) {// 找到要出局的节点的前一个节点for (int i = 1; i < this->interval; i++) { currentNode = currentNode->next;}// 删除当前节点Node removedNode = currentNode->next; currentNode->next = removedNode->next; delete removedNode;this->count--;// 移动当前节点到下一个节点currentNode = currentNode->next;}}// 获取胜利者的编号int getWinner() {return this->head->id;}private:Node head; // 链表头节点int count; // 当前剩余人数int interval; // 报数间隔};int mn() {int n, m;cout << \。

/*约瑟夫（Josephus）问题：n 个人围坐成一圈，从1 开始顺序编号；游戏开始，从第一个人开始由 1 到m 循环报数，报到m 的人退出圈外，问最后留下的那个人原来的序号。

[分析] 本题首先要定义一个数组，其元素个数为n。

n定义为常变量，以便定义数组。

数组元素的值标识该人是否出局，1在圈内，0出局。

值为0的元素不参加报数。

可用一个整型数k做计数器，采用倒计数，记录留下的人数。

[提示]数组是线性排列的，而人是围成圈的，用数组表示要有一种从数组尾部跳到其头部的技巧，即下标加1除以n求余数。

*/#include<iostream>using namespace std;const int n=50;//参加人数可以在此修改const int m=40;//循环报数值可以在此修改int main(){char jose[n];int i,j=0,k;for(i=0;i<n;i++) jose[i]=1;for(k=n;k>=1;k--){i=0;while(1){if(jose[j]==1){i++;if(i==m){jose[j]=0;break;}}j=(j+1)%n;}}cout<<"最后留下的那个人原来的序号:"<<j<<endl;return 0;}注意:下面这个题目用到了枚举，我没有讲，但希望大家自己能自学。

两队选手每队5人进行一对一的比赛，甲队为A、B、C、D、E，乙队为J、K、L、M、N，经过抽签决定比赛配对名单。

规定A不和J比赛，M不和D及E比赛。

列出所有可能的比赛名单。

解：这是一个组合问题，使用穷举法。

共有5个位置，设甲队5名队员位置不变，乙队改变队员位置，进行配对。

注意第1个位置可在5个队员中任选一个，以后的位置必须扣除已选过的队员。

并扣除不能配对的情况，即得所有可能的比赛名单。

#include<iostream>using namespace std;int main(){char st1[5]={'A','B','C','D','E'},st2[5]={'J','K','L','M','N'};int i=0,j,k,l,m,n;for(j=0;j<5;j++){//0号位if(j==0) continue;//A选手不与选手J比赛,即st1[0]不与st2[0]比赛for(k=0;k<5;k++){//1号位if(k==j) continue;//剔除乙队占据0号位的选手for(l=0;l<5;l++){//2号位if(l==j||l==k) continue;//剔除乙队占据0、1号位的选手for(m=0;m<5;m++){//3号位if(m==j||m==k||m==l) continue;//剔除乙队占据0、1、2号位的选手if(m==3) continue;//st1[3]不与st2[3]比赛,即D不与M比赛for(n=0;n<5;n++){//4号位if(n==j||n==k||n==l||n==m) continue;//剔除乙队占据0、1、2、3号位的选手if(n==3) continue;//st1[4]不与st2[3]比赛,即E不与M比赛cout<<st1[0]<<'-'<<st2[j]<<'\t'<<st1[1]<<'-'<<st2[k]<<'\t';cout<<st1[2]<<'-'<<st2[l]<<'\t'<<st1[3]<<'-'<<st2[m]<<'\t';cout<<st1[4]<<'-'<<st2[n]<<endl;i++;}}}}}cout<<i<<endl;return 0;}。

约瑟夫问题解决实验1:约瑟夫问题解决一、问题描述1。

实验主题:约瑟夫问题的一个描述是:n个人的数量是1，2，顺时针坐成一圈，每个人都有一个9(正整数)的密码。

首先，选择一个正整数作为上限值m，从第一个人开始按顺时针方向从1开始计数，当向m报告时停止计数，列出向m报告的人，使用他的密码作为新的值m，从下一个人开始按顺时针方向从1开始计数，并继续计数，直到所有的人都被列出。

试着设计一个程序，按照打印的顺序打印出每个人的号码。

2.基本要求:这个过程是通过使用单向循环链表来模拟的，每个人的号码是按照列表的顺序来打印的。

3.测试数据:N=7，7密码是3，1，7，2，4，8，4。

m的初始值是6(正确的出列顺序应该是6，1，4，7，2，3，5。

2.需求分析1。

通过程序实现的基本可能性:这个程序可以按照打印的顺序打印出每个人的号码。

程序运行后，将显示提示信息，提示用户输入人数n、初始报告值m和密码n。

如果程序需要自动重复，程序将在用户输入后自动输出计算结果。

2.输入形式和输入值范围:输入人数n、初始报告值m和n个人的密码，所有这些都是正整数int类型。

3.输出的形式:输出是按打印顺序打印每个人的号码，它是正整数。

4.测试数据要求:测试数据需要整型3.概要设计1。

为了实现上述功能，所使用的数据结构及其ADT 应在单向循环链表的有序链表中表示聚合数据的类型。

1.单向循环链表抽象数据类型的定义:typedef结构节点{ ElemType数据；元素类型号；结构节点*下一步；} SLNODE基本操作:结构节点* create _ sl(int n)；//创建单向循环链表2。

主要程序流程及其模块调用关系1)创建循环链表流程图2)约瑟夫问题解决流程图3)主要功能流程图4.详细设计1。

为每个操作实现伪代码，并在主程序上提供关键语句和注释:void main(){ SLNODE *头；int n，m；head=(SLNODE *)malloc(sizeof(SLNODE))；printf('/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */\ n ')；//初始界面printf('学生编号: 031350102 \ n ')；Printf('名称:王雅雯')；打印(约瑟夫问题解决)；printf('/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */\ n ')；打印(“输入总数n=\ n”)；scanf(“% d”，n)；打印(“输入初始值m=\ n”)；scanf(“% d”，m)；head=create _ sl(n)；约瑟夫斯(男，女，男)；}2。

约瑟夫生死游戏(C++)数据结构实现本文档涉及附件如下：1.\t代码附件：[约瑟夫生死游戏.cpp](代码附件地质)2.\t测试用例附件：[测试用例.txt](测试用例附件地质)约瑟夫生死游戏(C++)数据结构实现1.\t引言1.1\t背景1.2\t目的1.3\t范围2.\t概述2.1\t游戏规则2.2\t算法思路3.\t设计3.1\t数据结构设计3.1.1\t节点结构3.1.2\t链表结构3.2\t算法设计3.2.1\t初始化链表3.2.2\t删除节点3.2.3\t主循环4.\t实现4.1\t开发环境4.2\t实现细节4.2.1\t节点的创建与删除4.2.2\t链表的初始化与销毁4.2.3\t模拟游戏过程5.\t测试与验证5.1\t测试环境5.2\t测试用例5.2.1\t输入正常范围内的数据 5.2.2\t输入边界值5.2.3\t输入非法数据6.\t性能评估6.1\t时间复杂度分析6.2\t空间复杂度分析7.\t问题与讨论7.1\t问题7.2\t讨论8.\t结论8.1\t总结8.2\t改进方向本文所涉及的法律名词及注释：1.\t约瑟夫生死游戏：一个数学问题，又称约瑟夫环问题。

2.\t数据结构：计算机中用于组织和存储数据的方式。

3.\t链表：一种常见的数据结构，由一系列节点组成，节点间通过指针连接。

4.\t节点：链表中的元素，包含数据和指向下一个节点的指针。

5.\t初始化：为数据结构中的元素赋予初始值。

6.\t销毁：释放数据结构占用的资源，将其清空。

7.\t模拟：通过计算机程序对某个过程进行仿真。

8.\t测试用例：对程序进行测试的输入数据和期望输出结果。

9.\t性能评估：对程序的运行时间和内存占用等指标进行评估。

10.\t时间复杂度：衡量算法执行时间随数据规模增长的趋势。

11.\t空间复杂度：衡量算法执行时所需的额外空间随数据规模增长的趋势。