c语言实现约瑟夫生者死者游戏（附有详细代码）

c语言实现约瑟夫生者死者游戏（附有详细代码）

 Reborn Terran Emperor

任务描述

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

问题建模分析

本游戏的数学建模如下：假设n个旅客排成一个环形，依次顺序编号1，2，…，n。从某个指定的编号开始，沿环计数，每数到第m个人就让其出列，且从下一个人开始重新计数，继续进行下去。这个过程一直进行到剩下k个旅客为止。 本游戏的要求用户输入的内容包括：

1. 旅客的个数，也就是n的值；
2. 离开旅客的间隔数，也就是m的值；
3. 所有旅客的序号作为一组数据要求存放在某种数据结构中。 本游戏要求输出的内容是包括
4. 离开旅客的序号；
5. 剩余旅客的序号； 所以，根据上面的模型分析及输入输出参数分析，可以定义一种数据结构后进行算法实现。

#include <stdlib.h>
#include <stdio.h> 
/*思路：1.建立循环链表
2.创建两个链表，一个用来存放死者（数组也行）（链表太麻烦了，先用数组吧，数组不好传递，主要是忘了，还的是链表），一个用来存放总人数以及剩下的人
3.需要的函数或者方法：建立新节点并赋值，尾插法，删除结点,输出两个链表，算了别搞函数了，传递太烦了，嗯，有时间再写封装函数的 *///建立结构体 
struct node{int num;//存放序号struct node *next; 
}; int main()
{int n,m,k;//依次对应总人数，隔几个死一个，剩下几个scanf("%d %d %d",&n,&m,&k);//创建链表 struct node *head, *tail,*p,*q;//头结点和尾结点 head = (struct node *)malloc(sizeof(struct node));head->next = NULL;//创建头结点 tail=head;for(int i=1;i<=n;i++)//尾插法建立循环表 {p = (struct node *)malloc(sizeof(struct node));p->num=i;tail->next=p;p->next=head->next;tail=p;}//删除结点 int i=1,j=0,l;int a[100];//存放死者 p = head->next;     //后结点q = tail;          //前结点while(n!=k){if(i!=m){q = p;p = p->next;i++;}else if(i==m){l=head->next->num;q->next = p->next;a[j]=p->num;j++;free(p);p = q->next;if(head->next->num!=l)//这一步是让p移动到循环表的开头，因为删除结点时极大可能会把头结点指向的第一个结点干了，那头结点就会变成野指针 {head->next=p;}i = 1;n--;}}//输出链表和数组printf("死者顺序：");for(int w=0;w<j;w++){printf("%d ",a[w]); }printf("n");printf("生者：");//遍历循环表,这里知道了循环表还剩下多少个元素，可以取巧遍历 
//	while(p->num>p->next->num)//这一步是让p移动到循环表的开头，因为删除结点时极大可能会把头结点指向的第一个结点干了，那头结点就会变成野指针 
//	{							//这一步真难，想了好久，垃圾小陈。单向链表这里还是有问题，唉，双向链表可以这么思考 
//		p=p->next;
//	}struct node *list;list=head->next;for(int w=0;w<k;w++){printf("%d ",list->num);list=list->next;} }