快捷導(dǎo)航

HDOJ 1443 約瑟夫環(huán)的最新應(yīng)用分析詳解

更新時(shí)間：2013年05月24日 11:23:40 作者：

本篇文章是對(duì)HDOJ 1443 約瑟夫環(huán)的最新應(yīng)用進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下

k個(gè)男生和k個(gè)女生站成一列，前面k個(gè)是男生，后面k個(gè)是女生，從第一個(gè)男生開(kāi)始報(bào)數(shù)，報(bào)到隊(duì)列最后一個(gè)同學(xué)，循環(huán)到隊(duì)首繼續(xù)報(bào)，并且如果一個(gè)同學(xué)報(bào)到的數(shù)是m，這個(gè)同學(xué)就出列，然后后面的同學(xué)繼續(xù)從1開(kāi)始報(bào)數(shù)，現(xiàn)在求一個(gè)數(shù)m，使k個(gè)女生全部出列，而男生沒(méi)有出列。

輸入：男生女生的個(gè)數(shù)k(男生女生人數(shù)相等都為k，輸出：m值
例：輸入：2，輸出：7
輸入：4，輸出：30

本題是約瑟夫環(huán)變形先引入Joseph遞推公式，設(shè)有n個(gè)人（0,...,n-1），數(shù)m，則第i輪出局的人為f(i)=(f(i-1)+m-1)%(n-i+1),f(0)=0; f(i) 表示當(dāng)前子序列中要退出的那個(gè)人（當(dāng)前序列編號(hào)為0~(n-i));
拿個(gè)例子說(shuō)：K=4,M=30;

復(fù)制代碼代碼如下:

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
      ........

依據(jù)題意，前K個(gè)退出的人必定是后K個(gè)人，所以只要前k輪中只要有一次f(i)<k則此m不符合題意。
注意：
本題有幾點(diǎn)需要注意，否則很容易超時(shí)；
第一點(diǎn)、運(yùn)用公式j(luò)=(j+m-1)%(n-i)，推導(dǎo)出下一個(gè)出現(xiàn)的元素在第幾號(hào)位置，如果j<k的話，不符合題意。
第二點(diǎn)、就是m,當(dāng)只剩下k+1個(gè)數(shù)的時(shí)候，則上一個(gè)消失的數(shù)一定是在目前僅剩的bad左邊或者是右邊，所以m%(k+1)==0或者1
有了這兩個(gè)條件，可以加快程序的速度。。。
完整的實(shí)現(xiàn)代碼如下：

復(fù)制代碼代碼如下:

#include "stdio.h"
#include "stdlib.h"
int x[15];
/*
運(yùn)用公式j(luò)=(j+m-1)%(len-i);推導(dǎo)出下一個(gè)出現(xiàn)的元素在第幾號(hào)位置，如果j<k的話，不符合題意。
若有7個(gè)人，報(bào)到3的人依次出列
第一次 j=(j+m-1)%(len-i)=(0+3-1)%(7-0)=2   下標(biāo)為2的3出列   新序列為  1 2 4 5 6 7
第二次 j=(j+m-1)%(len-i)=(2+3-1)%(7-1)=4   下標(biāo)為4的6出列   新序列為  1 2 4 5 7
第三次 j=(j+m-1)%(len-i)=(4+3-1)%(7-2)=1   下標(biāo)為1的2出列   新序列為  1 4 5 7
第四次 j=(j+m-1)%(len-i)=(1+3-1)%(7-3)=3   下標(biāo)為3的7出列   新序列為  1 4 5
第五次 j=(j+m-1)%(len-i)=(3+3-1)%(7-4)=2   下標(biāo)為2的5出列   新序列為  1 4
第六次 j=(j+m-1)%(len-i)=(2+3-1)%(7-5)=0   下標(biāo)為0的1出列   新序列為  4
第七次 j=(j+m-1)%(len-i)=(0+3-1)%(7-6)=0   下標(biāo)為0的4出列   新序列為空，至此，所有人已經(jīng)全部出列，出列的順序?yàn)椋? 6 2 7 5 1 4
*/
int test(int k,int m)
{
 int i,j=0,len=k*2;
 for(i=0;i<k;i++)
 {
  j=(j+m-1)%(len-i);    //約瑟夫環(huán)公式
  if(j<k)
   return 0;     //遇到前k輪中有小于k的直接返回0 
 }
 return 1;
}
/*
接下來(lái)說(shuō)說(shuō)m的取值范圍：我們考察一下只剩下k+1個(gè)人時(shí)候情況，即壞人還有一個(gè)未被處決，
那么在這一輪中結(jié)束位置必定在最后一個(gè)壞人，那么開(kāi)始位置在哪呢？這就需要找K+2個(gè)人的結(jié)束位置，
然而K+2個(gè)人的結(jié)束位置必定是第K+2個(gè)人或者第K+1個(gè)人，這樣就出現(xiàn)兩種順序情況：GGGG.....GGGXB 或  GGGG......GGGBX (X表示有K+2個(gè)人的那一輪退出的人）所以有K+1個(gè)人的那一輪的開(kāi)始位置有兩種可能即最后一個(gè)位置或K+1的那個(gè)位置，限定m有兩種可能：
GGGG......GGGBX 若K+2個(gè)人的結(jié)束位置在最后一個(gè)(第K+2個(gè))，則m%(k+1)==0
GGGG......GGGXB 若K+2個(gè)人的結(jié)束位置在倒數(shù)第二個(gè)(第K+1個(gè))，則m%(k+1)==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("%d\n",x[k]);
 system("pause");
}