首页 > 代码库 > 约瑟夫生死游戏(单链表实现)

约瑟夫生死游戏(单链表实现)

2024-08-18 05:15:48   222人阅读

本周的作业还算挺好玩。。约瑟夫生死游戏嘛。

老师要抽签选择每个组对应的数据结构。结果宝宝抽到了单链表。。。。

一、项目简介

      约瑟夫生者死者游戏的大意是：30个旅客同乘一条船，因为严重超载，加上风高浪大，危险万分；因此船长告诉乘客，只有将全船一半的旅客投入海中，其余人才能幸免遇难。无奈，大家只得同意这种办法，并议定30个人围成一圈，由第一个人开始，依次报数，数到第9人，便把他投入大海中，然后从他的下一个人数起，数到第9人，再将他投入大海，如此循环，直到剩下15个乘客为止。问哪些位置是将被扔下大海的位置。

二、设计思路

      约瑟夫环问题是算法设计中的一个经典问题，是顺序编号的一组n个人围坐一圈，从第1个人按一定方向顺序报数，在报到m时该人出列，然后按相同方法继续报数，直到所有人出列。设计算法求约瑟夫环中人员的出列顺序。

线性表、队列是一种常用的数据结构，有顺序和链式两种存储结构，在实际中应用十分广泛，而链表又分为单链表和循环链表，队列又分为链式队列和循环队列。这些数据结构都可用来解决约瑟夫环问题。

三、 基本要求

1、选择合适的存储结构，建立线性表；

2、利用单链表求解约瑟夫环问题；

四、测试数据

约瑟夫环的开始位置、长度、报数可以从键盘输入合法数据，或者随机生成。

代码如下:

      我的数据是随机生成滴。

  1 #include <cstdio>
  2 #include <ctime>
  3 #include <cstdlib>
  4 
  5 int kk=0;
  6 int ll;
  7 
  8 typedef struct people
  9 {
 10     int num;
 11 }PEO;
 12 typedef struct Node
 13 {
 14     PEO data;
 15     struct Node * next;
 16 }Node;
 17 
 18 Node *InitList(Node *L)//初始化单链表
 19 {
 20     L=(Node *)malloc(sizeof(Node));
 21     L->next=NULL;
 22     return L;
 23 }
 24 
 25 void CreateFormTail(Node *L)//尾插法
 26 {
 27     Node *s,*r;
 28     r=L;
 29     int aa=30-ll+1+1;
 30     for(int i=1;i<=30;i++){
 31         s=(Node *)malloc(sizeof(Node));   
 32         s->data.num=aa; 
 33         r->next=s;
 34         r=s;
 35         if(i==30){
 36             r->next=NULL;
 37         }
 38         if(aa==30)
 39             aa=1;
 40         else
 41             aa++;
 42         
 43     }
 44 }
 45 void Printf(Node *L)
 46 {
 47     int q=0;
 48     Node *p=L->next;
 49     while(p!=NULL)
 50     {
 51         q++;
 52         printf("%d\n",p->data.num);
 53         p=p->next;
 54     }
 55     printf("单链表长度为%d\n",q);
 56 }
 57 
 58 void sou(Node *L)
 59 {
 60     Node *s,*r,*pre;
 61     r=L;
 62     s=r->next;
 63     for(int i=1;i<=30;i++){
 64         if(s->data.num==1)
 65             break;
 66         else
 67             r=r->next;
 68             s=r->next;
 69             
 70     }
 71     printf("被丢下水的报数按顺序为\n");
 72     while(kk<15){
 73         for(int j=1;j<9;j++){
 74             r=r->next;
 75             s=r->next;
 76             if(s->next==NULL){
 77                 s->next=L->next;
 78             }
 79             if(r->next==NULL){
 80                 r->next=L->next;
 81             }
 82         }
 83         printf("%d\n",s->data.num);
 84         s=s->next;
 85         pre=r->next;
 86         r->next=s;
 87         free(pre);
 88         kk++;
 89     }
 90 }
 91 
 92 int main()
 93 {
 94     srand(time(NULL));//初始化随机化种子          
 95     ll=rand()%30+1;
 96     printf("第%d个人从1开始报数\n",ll);
 97     printf("本题条件30个人从1开始数，数到第9个人就丢下水，要丢下去15个人\n");
 98     Node *L=NULL;
 99     L=InitList(L);
100     CreateFormTail(L);
101     Printf(L);
102     sou(L);
103     
104     return 0;
105 }

 

约瑟夫生死游戏(单链表实现)


联系
我们