josephus 问题

  
    问题描述：N个人从1到N编号，围成一圈，从1号开始传土豆，经过M次的人离席，又后面的人继续传递，最后的人获胜。



#include
#include
void main()
{
int *a;
int i,j,k;
int M,N;


printf("please input the M   and  N \n");
scanf("%d,%d",&M,&N);


printf("M= %d ,N = %d \n",M,N);


/* if(M ==0)      //简单优化，如果是依次离席，则最后一个胜出
{
printf("%d \n",N);
return ;
}*/


a = (int*)malloc((N)*sizeof(int));      //虽然题目是从1编号，但是如果在在数组中利用1到N 编号，处理回绕的时候需要判断，不如利用0 到N-1 省事，直接求余就可以办到。
for(i=0;i a[i]=0;


i= 0;j=0;k=0;
do{



for(k=0;k {
i=(i+1)%N;     //，第i 个人就是现在拿土豆的人。每次开始前，围城一圈人都是未曾离席的，所以i 先加往下传。如果k=0，即表示不用传，自己离席，而在for开始的时候就判断了，如果不用传，for结构就不会运行。
if(a[i]==0)    //遇到有效的人，才计数
k++;
}
a[i] = 1;    //这个人是传递了第M次土豆的人，离席。
printf("%d ",i+1);
while(a[++i]!=0);  //将土豆交给下一个有效的人（未曾离席的人，继续传递），则现在土豆在第i个人手上。
j++;      //已经离席的人数统计


}while(j+1 != N);   //是否已经离席了N-1 个人，则最后一个让你就是胜利者


     printf("\n");


     for(i=0 ;i printf("%d ",a[i]);
/* if(a[i] == 0)
{
printf("%d \n",i);
break;
}*/
}