約瑟夫環

題目大意：

有k個好人跟k個壞人按順序坐著，然後按第m個殺人，求出把壞人全部先殺光的m的最小值。 0<k<14。典型的約瑟環問題。

解題思路：

一開始看見數據量那麼小，還以為暴力一定可以出來，結果，好吧，當k為0以上時，時間大得驚人，自己暴力的方法還是有很大問題啊。

比較標準的做法是：在這麼多個人中，始終用start跟end來確定好人那個序列的位置。

比如一開始是1 2 3 4 5 6，那麼start = 0,end = 3(從0開始計數)當m等於5的時候，kill後就剩下1 2 3 4 6 ，重新拍下序列變成 6 1 2 3 4 ，這時候

start = ((start-m)%n+n)%n;

end = ((end-m)%n+n)%n;

n是當前剩下的人數。定完位置之後，kill的位置為kill = (m-1)%n;

這樣就可以做了。

代碼：

#include
using namespace std;

bool joseph(int k, int m)
{
int start = 0, end = k - 1; //定位，定好人的位置
int kill;//殺人的序號
for(int n = 2 * k; n > k; n--) //n代表人數
{
kill = (m - 1) % n;
if(kill >= start && kill <= end)
{
return false;
}
start = ((start - m) % n + n) % n;//定位，加n模n是為了防止負數
end = ((end - m) % n + n) % n;
}
return true;
}

int main(void)
{
int f[14];
for(int i = 1; i < 14; i++)
for(int j = 1; ; j++)
{
if(joseph(i, j))
{
f[i] = j;
break;
}
}
int k;
while(scanf("%d", &k), k)
{
printf("%d\n", f[k]);
}
return 0;
}