实验一:约瑟夫生死游戏

发布于 2020-03-29  96 次阅读


1.    实验内容简介

每30个乘客同乘一艘船,因为严重超载,加上风高浪大,危险万分,因此船长告诉乘客,只有将全船一半乘客投入海中,其余人才能幸免于难。无奈,大家只得同意这种办法,并议定30个人围成一圈,由第1个人数起,依次报数,数到第9人,便把他投入大海中,然后再从他的下一个人数起,数到第9人,再将他扔到大海中,如此循环地进行,直到剩下15个乘客为止。问哪些位置是将被扔下大海的位置。

2.    程序设计思路

使用链表结构,每一个节点代表一个人,每个节点包含2个属性,一个是编号number,一个是指向下一个节点的指针。经过一系列算法之后,剩下的节点即代表剩下的人。

3.    算法分析与设计

根据游戏规则每数到第九个人就抛弃,我们设计算法为每九个节点就抛弃这个节点,即第8个节点指向第10个节点,将次操作一直循环,直到剩下15个人为止。

4.    数据结构设计

设置链表,每个节点包含number,和next指针,算法中设计变量last,初始值为30,判断last为15使终止算法。

5.    系统实现(系统架构,操作系统运用,数据库运用等)

本实验中无这些应用。

6.    测试结果

最后剩下来的人为2       3       4       5       11      12      14      15      16      18      21        22      26      29      30

7.    源代码

#include <errno.h>
#include <string.h>
#include <stdint.h>
#include <iostream>
#include <fstream>
#include<string>
#include <stack>
#include <vector>
#include <deque>
#include<stdlib.h>
#pragma warning (disable: 4996)
using namespace std;
struct node {
	string data;
	int key;
	int number;
	node* next;
};
node* creat()
{
	node* head = NULL;
	node* end = head;
	node* S;
	string temp;
	int n;
	for (int i = 1; i <= 30; i++) {
		S = new node;
		S->number = i;
		S->next = NULL;
		if (head == NULL)head = S;
		else end->next = S;
		end = S;
	}
	end->next = head;
	return head;
}
void show(node* head) {
	node* read = head;
	cout << "——————愚蠢的分界符——————" << endl;
	cout << read->number << "	";
	read = read->next;
	while(read!=head)
	{
		cout << read->number << "	";
		read = read->next;
	}
	cout << endl;
	cout << "——————愚蠢的分界符——————" << endl;
}
node *game(node* head)
{
	node* X = head;
	for (int i = 0; i < 29; i++)X = X->next;
	int left = 30;
	do
	{
		for (int count = 0; count < 8; count++) {
			X = X->next;
		}
		cout << X->next->number << "	";
		X->next = X->next->next;
		left--;
	} while (left != 15);
	cout << "剩下人类的编号:" << endl;
	for (int i = 0; i < 15; i++) {
		cout << X->number << "	";
		X = X->next;
	}
	cout << endl;
	return head;
}
int main()
{
	node* head;
	head = creat();
	show(head);
	head = game(head);
	system("pause");
	return 0;
}

山下闲人漫步,山上泉水熙熙。 山外庸人自扰,山里野花灿灿。