HDOJ 1443 约瑟夫环的最新应用分析详解

k个男生和k个女生站成一列，前面k个是男生，后面k个是女生，从第一个男生开始报数，报到队列最后一个同学，循环到队首继续报，并且如果一个同学报到的数是m，这个同学就出列，然后后面的同学继续从1开始报数，现在求一个数m，使k个女生全部出列，而男生没有出列。

输入：男生女生的个数k(男生女生人数相等都为k，输出：m值
例： 输入：2，输出：7
输入：4，输出：30

本题是约瑟夫环变形 先引入Joseph递推公式，设有n个人（0,...,n-1），数m，则第i轮出局的人为f(i)=(f(i-1)+m-1)%(n-i+1),f(0)=0; f(i) 表示当前子序列中要退出的那个人（当前序列编号为0~(n-i));
拿个例子说：K=4,M=30;
复制代码 代码如下:
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
      ........

依据题意，前K个退出的人必定是后K个人，所以只要前k轮中只要有一次f(i)注意：
本题有几点需要注意，否则很容易超时；
第一点、运用公式j=(j+m-1)%(n-i)，推导出下一个出现的元素在第几号位置，如果j第二点、就是m,当只剩下k+1个数的时候，则上一个消失的数一定是在目前仅剩的bad左边或者是右边，所以m%(k+1)==0或者1
有了这两个条件，可以加快程序的速度。。。
完整的实现代码如下：
复制代码 代码如下:
#include "stdio.h"
#include "stdlib.h"
int x[15];

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;
}

void Joseph(void)
{
 int m,k;
 for(k=1;k<15;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("%dn",x[k]);
 system("pause");
}