（C语言）约瑟夫斯（Josephus）问题进阶问题求解

（C语言）约瑟夫斯（Josephus）问题进阶问题求解

基础问题描述如下：

约瑟夫斯（Josephus）问题的一种描述是：编号为1，2，…，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向下一个人开始重新从1报数，如此下去，直至所有的人全部出列为止。试设计一个程序，按出列顺序印出各人编号。

为解决这个问题，采用循环链表进行储存，将每个人的编号、密码以数据结点的形式储存。

typedef struct node{
	int data;  //记录每个人手中的密码 
	int id;    //设置每个人人的最初位置 
	struct node *next;
}node,*linklist;

整体算法思路流程图十分简单：

其中有一点需要注意的是，在建立循环链表之时，要注意设置头结点，因为所写循环函数会根据当前结点的值进行下一步的循环，如果没有头结点，则会默认从第一个人开始循环，这与问题本身的意义是不一样的。

然后再用c语言将该流程描述出来：

#include
#include

int n;
typedef struct node{
	int data;  //记录每个人手中的密码 
	int id;    //设置每个人人的最初位置 
	struct node *next;
}node,*linklist;

linklist Creat_List(int n)  //创建总人数为n的约瑟夫斯环 
{
	linklist l,p,q;
	int i=1;
	int m;
	l=(node*)malloc(sizeof(node));
	printf("第1个人的密码是："); 
	scanf("%d",&m);
	l->data=m;
	l->id=1; 
	l->next=l;
	q=l;
	for(i=2;i<=n;i++)
	{
		p=(node*)malloc(sizeof(node));
		printf("第%d个人的密码是：",i); 
		scanf("%d",&m);
		p->data=m;
		p->id=i;
		p->next=l;
		q->next=p;
		q=p;
	}
	return l;
}
linklist kill_man(linklist l,int m)  //踢出第m个人 
{
	int i;
	linklist p,q;
	q = l; 
	for(i=0;inext;
	}
	printf("nkillman is :%dn",q->id);
	p->next = q->next;
	return q;
}
int main()
{
	int i,m;
	linklist l;
	printf("n的初值是：");
	scanf("%d",&n);
	printf("nm的初值是：");
	scanf("%d",&m);
	l=Creat_List(n);
	l= kill_man(l,m-1);
	for(i=1;idata;
		l= kill_man(l,m);
	}
	printf("-----------------------------------------n");
	return 0;
}