约瑟夫环.cpp

约瑟夫环.CPP

/*设有N个人围成一圈，每个人的编号依次1，2，。。。N。现从编号为S克人开始报数，数到M的人便出列，接着从出列得下一个人开始重新报数，数到M的人又出列，以此类推，直到所有的人都出列为止。现要求该N个人的出列顺序，这个问题称为约瑟夫问题。试编写求解约瑟夫问题的方法。  
百合清韵 22:00:56
约瑟夫环？ */


#include <stdio.h>
#define N 1000		//总人数
#define M 25		//一轮人数
#define S 2			//起始点

int p[N],s;		//p[N]中储存输出顺序
 
void YSF()		//约瑟夫环函数
{
	int cnt=0,i=1,k,s,t; 
	//i为计数，s为该数位置，k保存输出数的位置，t为中间变量保存输出数的值
	s=S-1;
	while(cnt<N-1)
	{
		//未全部输出时
		
		i++;s++;
		if(s>N-cnt-1)s=0;
		if(i%M==0)
		{		
			//输出条件			
			t=p[s];
			i=1;k=s;			//重新从1开始计数
			while(k<N-cnt)p[k++]=p[k+1];	//将其他的数前移
			p[N-cnt-1]=t;		//将要输出的位置移至末尾
			if(s==N-cnt-1)s=0;		//最后一个输出
			cnt++;				//cnt为已输出的个数
		}
	}

	for(i=N-1;i>=0;i--)
	{
		if(i%10==0) printf("\n");	
		printf("%4d",p[i]);
	}
}

void main()
{
	int i;
	for(i=0;i<N;i++)p[i]=i+1;
	YSF();
}