[数据结构与算法]约瑟夫环的三种解法（C语言），数组+链表+递归

问题描述：有n人围成一圈，顺序排号。从第1个人开始报数（从1到m报数），凡报到m的人退出圈子，问最后留下的是原来的第几号的那位。

只需要把出局的人的顺序全部算出来即可。

（一）数组实现：

#include<stdio.h>
#include<stdlib.h>
int main()
{
	int n,m;//共n个人，数到m出局
	int out=0,k=0,i;
	scanf("%d%d",&n,&m);
	int a[n];
	for(i=0;i<n;i++)//初始化为0，为1表示已出局 
	{
		a[i]=0;
	}
	i=-1;
	while(out<n)//当全部的人出局时循环停止 
	{
			
		i++;
		if(i==n)i=0;//因为围成一个环，如果i>n说明已经转完一圈 
		if(a[i]==0)k++;
		if(k==m)//报数为m的人出局 
		{
			out++; 
			a[i]=1;
		printf("%d ",i+1);
			k=0;
		}
		
	 } 
	return 0;
 } 

（二）链表实现：

#include<stdio.h>
#include<stdlib.h>
typedef struct node 
{
	int data;
	struct node*next;
}Node;
void Joseph(int n,int m)//有n个人，报到m出局
{
	int i;
	Node *head=NULL,*p=NULL,*r=NULL;
	head =(Node*) malloc(sizeof(Node));//为头节点分配内存空间 
	if(head==NULL)
	{
		printf("n内存分配失败"); 
		return ;
	}
	head->data=0;
	head->next=NULL;
	p=head;
	for(i=1;i<n;i++)//尾插法插入节点 
	{
		r=(Node*)malloc(sizeof(Node));//申请内存空间 
		r->data=i;//输入数据域 
		p->next=r;//尾插法 
		p=r;
	}
	p->next=head;//最后一个节点指向头节点，形成循环链表 
    r=head;
	while (p->next!=p)//当只剩下一个节点时退出循环 
	{
		for(i=1;i<m;i++)//i为计数器，数到三的出局 
		{
			p=r;
			r=r->next;
		}
		printf("%d ",r->data+1); //输出出局的号数，因为从0开始数所以号数+1 
		p->next=r->next;//
		free(r);//将出局的节点释放 
		r=p->next;
	}
	printf("%d",r->data+1);//输出最后一个节点 
 } 
int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	Joseph(n,m);
	return 0;
 } 

（三）递归实现：

#include<stdio.h>
int Joseph(int n,int m,int i)//共n个人，数到m出局，上一个出局的是k ,第i个出局 
{	
	if(i==1)return (n+m-1)%n;//第一次出局的人 
	else return (Joseph(n-1,m,i-1)+m)%n; 
 } 
 int main()
 {
 	int n,m,i;
 	scanf("%d%d",&n,&m);
 	for(i=1;i<=n;i++)
 	{
 		printf("%d ",Joseph(n,m,i)+1); 
	 }
	 
 }