josephus 问题

620阅读 0评论2013-04-10 hnylcxq
分类:C/C++

  
    问题描述: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;
}*/
}
上一篇:[转]DM9000 接收不到数据的原因
下一篇:uip IP包分片重组函数解析