摘要：
这周的家庭作业很有趣约瑟夫的生死游戏。教师应抽签选择每组对应的数据结构。结果，婴儿画了一张单链表……1、约瑟夫的生者与死者游戏的主要思想是：30名乘客乘坐同一艘船，由于严重超载和高风浪，这是极其危险的；因此，船长告诉乘客，只有当船上一半的乘客被投入大海时，其余的乘客才能存活下来。然而，每个人都不得不同意这种方法，并同意组成一个30人的圈子。第一个人依次数了数，第九个人数了数。然后他们把他扔到海里
本周的作业还算挺好玩。。约瑟夫生死游戏嘛。
老师要抽签选择每个组对应的数据结构。结果宝宝抽到了单链表。。。。
一、项目简介
约瑟夫生者死者游戏的大意是：30个旅客同乘一条船，因为严重超载，加上风高浪大，危险万分；因此船长告诉乘客，只有将全船一半的旅客投入海中，其余人才能幸免遇难。无奈，大家只得同意这种办法，并议定30个人围成一圈，由第一个人开始，依次报数，数到第9人，便把他投入大海中，然后从他的下一个人数起，数到第9人，再将他投入大海，如此循环，直到剩下15个乘客为止。问哪些位置是将被扔下大海的位置。
二、设计思路
约瑟夫环问题是算法设计中的一个经典问题，是顺序编号的一组n个人围坐一圈，从第1个人按一定方向顺序报数，在报到m时该人出列，然后按相同方法继续报数，直到所有人出列。设计算法求约瑟夫环中人员的出列顺序。
线性表、队列是一种常用的数据结构，有顺序和链式两种存储结构，在实际中应用十分广泛，而链表又分为单链表和循环链表，队列又分为链式队列和循环队列。这些数据结构都可用来解决约瑟夫环问题。
三、 基本要求
1、选择合适的存储结构，建立线性表；
2、利用单链表求解约瑟夫环问题；
四、测试数据
约瑟夫环的开始位置、长度、报数可以从键盘输入合法数据，或者随机生成。
代码如下:
我的数据是随机生成滴。
#include <cstdio>
#include <ctime>
#include <cstdlib>
int kk=0;
int ll;
typedef struct people
{
int num;
}PEO;
typedef struct Node
{
PEO data;
struct Node * next;
}Node;
Node *InitList(Node *L)//初始化单链表
{
L=(Node *)malloc(sizeof(Node));
L->next=NULL;
return L;
}
void CreateFormTail(Node *L)//尾插法
{
Node *s,*r;
r=L;
int aa=30-ll+1+1;
for(int i=1;i<=30;i++){
s=(Node *)malloc(sizeof(Node));
s->data.num=aa;
r->next=s;
r=s;
if(i==30){
r->next=NULL;
}
if(aa==30)
aa=1;
else
aa++;
}
}
void Printf(Node *L)
{
int q=0;
Node *p=L->next;
while(p!=NULL)
{
q++;
printf("%d
",p->data.num);
p=p->next;
}
printf("单链表长度为%d
",q);
}
void sou(Node *L)
{
Node *s,*r,*pre;
r=L;
s=r->next;
for(int i=1;i<=30;i++){
if(s->data.num==1)
break;
else
r=r->next;
s=r->next;
}
printf("被丢下水的报数按顺序为
");
while(kk<15){
for(int j=1;j<9;j++){
r=r->next;
s=r->next;
if(s->next==NULL){
s->next=L->next;
}
if(r->next==NULL){
r->next=L->next;
}
}
printf("%d
",s->data.num);
s=s->next;
pre=r->next;
r->next=s;
free(pre);
kk++;
}
}
int main()
{
srand(time(NULL));//初始化随机化种子
ll=rand()%30+1;
printf("第%d个人从1开始报数
",ll);
printf("本题条件30个人从1开始数，数到第9个人就丢下水，要丢下去15个人
");
Node *L=NULL;
L=InitList(L);
CreateFormTail(L);
Printf(L);
sou(L);
return 0;
}