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