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