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)<k則此m不符合題意。
注意：
本題有幾點需要注意，否則很容易超時；
第一點、運用公式j=(j+m-1)%(n-i)，推導出下一個出現的元素在第幾號位置，如果j<k的話，不符合題意。
第二點、就是m,當只剩下k+1個數的時候，則上一個消失的數一定是在目前僅剩的bad左邊或者是右邊，所以m%(k+1)==0或者1
有了這兩個條件，可以加快程序的速度。。。
完整的實現代碼如下：
#include "stdio.h"
#include "stdlib.h"
int x[15];
/*
運用公式j=(j+m-1)%(len-i);推導出下一個出現的元素在第幾號位置，如果j<k的話，不符合題意。
若有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<k;i++)
{
j=(j+m-1)%(len-i); //約瑟夫環公式
if(j<k)
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<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");
}
