深入详解关于HDOJ 1443 约瑟夫环的应用

f(0)=0;
      f(1)=(f(0)+30-1)%8=5; 序列（0,1,2,3,4,5,6,7）中的5
      f(2)=(f(1)+30-1)%7=6; 序列（0,1,2,3,4,6,7）中的7
      f(3)=(f(2)+30-1)%6=5; 序列（0,1,2,3,4,6）中的6
      f(4)=(f(3)+30-1)%5=4; 序列（0,1,2,3,4）中的4
      ........

#include "stdio.h"
#include "stdlib.h"
int x[15];
/*
运用公式j=(j+m-1)%(len-i);推导出下一个出现的元素在第几号位置，如果j 若有7个人，报到3的人依次出列
第一次 j=(j+m-1)%(len-i)=(0+3-1)%(7-0)=2   下标为2的3出列   新序列为  1 2 4 5 6 7
第二次 j=(j+m-1)%(len-i)=(2+3-1)%(7-1)=4   下标为4的6出列   新序列为  1 2 4 5 7
第三次 j=(j+m-1)%(len-i)=(4+3-1)%(7-2)=1   下标为1的2出列   新序列为  1 4 5 7
第四次 j=(j+m-1)%(len-i)=(1+3-1)%(7-3)=3   下标为3的7出列   新序列为  1 4 5
第五次 j=(j+m-1)%(len-i)=(3+3-1)%(7-4)=2   下标为2的5出列   新序列为  1 4
第六次 j=(j+m-1)%(len-i)=(2+3-1)%(7-5)=0   下标为0的1出列   新序列为  4
第七次 j=(j+m-1)%(len-i)=(0+3-1)%(7-6)=0   下标为0的4出列   新序列为空，至此，所有人已经全部出列，出列的顺序为：3 6 2 7 5 1 4
*/
int test(int k,int m)
{
 int i,j=0,len=k*2;
 for(i=0;i  {
  j=(j+m-1)%(len-i);    //约瑟夫环公式
  if(j    return 0;     //遇到前k轮中有小于k的直接返回0
 }
 return 1;
}
/*
接下来说说m的取值范围：我们考察一下只剩下k+1个人时候情况，即坏人还有一个未被处决，
那么在这一轮中结束位置必定在最后一个坏人，那么开始位置在哪呢？这就需要找K+2个人的结束位置，
然而K+2个人的结束位置必定是第K+2个人或者第K+1个人，这样就出现两种顺序情况：GGGG.....GGGXB 或  GGGG......GGGBX (X表示有K+2个人的那一轮退出的人）所以有K+1个人的那一轮的开始位置有两种可能即最后一个位置或K+1的那个位置，限定m有两种可能：
GGGG......GGGBX 若K+2个人的结束位置在最后一个(第K+2个)，则m%(k+1)==0
GGGG......GGGXB 若K+2个人的结束位置在倒数第二个(第K+1个)，则m%(k+1)==1
*/
void Joseph(void)
{
 int m,k;
 for(k=1;k  {
  m=k+1;
  while(1)
  {
   if(test(k,m))     // m%(k+1)==0的情况
   {
    x[k]=m;
    break;
   }
   if(test(k,m+1))     // m%(k+1)==1的情况
   {
    x[k]=m+1;
    break;
   }
   m+=k+1;
  }
 }
}
int main(void)
{
    int k;
 Joseph();
 while(scanf("%d",&k),k)
  printf("%d\n",x[k]);
 system("pause");
}