參考文章
約瑟夫環(huán)之二(用遞歸的思想解決Josephus問(wèn)題)
解釋
約瑟夫環(huán)是一個(gè)數(shù)學(xué)的應(yīng)用問(wèn)題：已知n個(gè)人（以編號(hào)1，2芦劣，3...n分別表示）圍坐在一張圓桌周圍迄汛。從編號(hào)為k的人開(kāi)始報(bào)數(shù)燃辖，數(shù)到m的那個(gè)人出列；他的下一個(gè)人又從1開(kāi)始報(bào)數(shù)剖踊，數(shù)到m的那個(gè)人又出列；依此規(guī)律重復(fù)下去，直到圓桌周圍的人全部出列以蕴。
解法
初始情況： 0, 1, 2 ......n-2, n-1 (共n個(gè)人)
第一個(gè)人,編號(hào)一定是(m-1)%n（或者寫(xiě)成m%n-1）出列之后，剩下的n-1個(gè)人組成了一個(gè)新的約瑟夫環(huán)（以編號(hào)為k==m%n的人開(kāi)始）:
k k+1 k+2 ... n-2, n-1, 0, 1, 2, ...,k-3, k-2
現(xiàn)在我們把他們的編號(hào)做一下轉(zhuǎn)換：
x' --> x的情況
k --> 0
k+1 --> 1
k+2 --> 2
...
...
k-2 --> n-2
變換后就完完全全成為了(n-1)個(gè)人報(bào)數(shù)的子問(wèn)題辛孵，假如我們知道這個(gè)子問(wèn)題的解：例如x是最終的勝利者丛肮，那么根據(jù)上面這個(gè)表把這個(gè)x變回去不剛好就是n個(gè)人情況的解嗎！
x ->ｘ＇魄缚？(這正是從n-1時(shí)的結(jié)果反過(guò)來(lái)推n個(gè)人時(shí)的編號(hào)宝与！)
0 -> k
1 -> k+1
2 -> k+2
...
...
n-2 -> k-2
變回去的公式 x'=(x+k)%n (注：k=m%n)
那么，如何知道(n-1)個(gè)人報(bào)數(shù)的問(wèn)題的解冶匹？只要知道(n-2)個(gè)人的解就行了习劫。(n-2)個(gè)人的解呢？只要知道(n-3)的情況就可以了 ---- 這顯然就是一個(gè)遞歸問(wèn)題：
令f[i]表示i個(gè)人玩游戲報(bào)m退出最后勝利者的編號(hào)徙硅，最后的結(jié)果就是f[n]
遞推公式
f[1]=0;
f[i]=(f[i-1]+k)%i = (f[i-1] +m%i) % i = (f[i-1] + m) % i ; (i>1)
代碼
#include <stdio.h>
int main() {
int n, m, i, result;
while (scanf("%d", &n) == 1) {
if (!n) {
break;
}
scanf("%d", &m);
result = 0;
for (i = 2; i <= n; i++) {
result = (result + m) % i;
}
printf("%d\n", result + 1);
}
return 0;
}
