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;
}