基本問(wèn)題描述：
已知n個(gè)人（以編號1，2，3...n分別表示）圍坐在一張圓桌周?chē)?。從編號?的人開(kāi)始報數，數到m的那個(gè)人出列；他的下一個(gè)人又從1開(kāi)始報數，數到m的那個(gè)人又出列；依此規律重復下去，直到圓桌周?chē)娜巳砍隽?。（也?lèi)似于變態(tài)殺人狂問(wèn)題）通常解決這類(lèi)問(wèn)題時(shí)我們把編號從0~n-1，最后結果 1即為原問(wèn)題的解。通常，我們會(huì )要求輸出最后一位出列的人的序號。那么這里主要研究的是最后一個(gè)出列的人的序號要怎么確定。
當n，m數據量很小的時(shí)候，我們可以用循環(huán)鏈表模擬約瑟夫環(huán)的過(guò)程。當模擬到人數等于1的時(shí)候，輸出剩下的人的序號即可。
具體解法這種方法往往實(shí)現起來(lái)比較簡(jiǎn)單，而且也很容易理解。但是時(shí)間復雜度卻是很糟糕的，達到了O（nm），這樣的話(huà)，其實(shí)在n，m比較大的時(shí)候（nm達到10^8或者更大），那么要得出結果往往需要耗費很長(cháng)的時(shí)間，但是我們可以運用一點(diǎn)數學(xué)上的技巧，將最后結果推導出來(lái)。
為了簡(jiǎn)化出列的過(guò)程：
首先我們把這n個(gè)人的序號編號從0~n-1（理由很簡(jiǎn)單，由于m是可能大于n的，而當m大于等于n時(shí)，那么第一個(gè)出列的人編號是m%n，而m%n是可能等于0的，這樣編號的話(huà)能夠簡(jiǎn)化后續出列的過(guò)程），當數到m-1的那個(gè)人出列，因此我們編號完成之后，開(kāi)始分析出列的過(guò)程：
第一次出列：
一開(kāi)始的時(shí)候，所有人的編號排成序列的模式即為：
0,1,2,3,4,5...n-2，n-1
那么第一次出列的人的編號則是(m-1)%n1，那么在第一個(gè)人出列之后，從他的下一個(gè)人又開(kāi)始從0開(kāi)始報數，為了方便我們設k1 = m%n1（n1為當前序列的總人數）那么在第一個(gè)人出列之后，k1則是下一次新的編號序列的首位元素，那么我們得到的新的編號序列為：
k1，k1 1，k1 2，k1 3...n-2，n-1，0，1，2...k1-3，k1-2 (k1-1第一次已出列)
那么在這個(gè)新的序列中，第一個(gè)人依舊是從0開(kāi)始報數，那么在這個(gè)新的序列中，每個(gè)人報的相應數字為：
0,1，2,3....n-2
那么第二次每個(gè)人報的相應數字與第一次時(shí)自己相應的編號對應起來(lái)的關(guān)系則為：
0 --> k1
1 --> k1 1
2 --> k1 2
...
n-2 ---> (k1 n-2)%n1(n1為當前序列的總人數，因為是循環(huán)的序列，k1 n-1可能大于總人數)
那么這時(shí)我們要解決的問(wèn)題就是n-1個(gè)人的報數問(wèn)題（即n-1階約瑟夫環(huán)的問(wèn)題）
可能以上過(guò)程你還是覺(jué)得不太清晰，那么我們重復以上過(guò)程，繼續推導剩余的n-1個(gè)人的約瑟夫環(huán)的問(wèn)題：
那么在這剩下的n-1個(gè)人中，我們也可以為了方便，將這n-1個(gè)人編號為：
0,1,2,3,4...n-2
那么此時(shí)出列的人的編號則是（m-1） % n2（n2為當前序列的總人數），同樣的我們設k2 = m % n2，那么在這個(gè)人出列了以后，序列重排，重排后新的編號序列為：
k2，k2 1，k2 2，k2 3...n-2，n-1，0，1，2...k2-3，k2-2 (k2-1第一次已出列)
那么在這個(gè)新的序列中，第一個(gè)人依舊是從1開(kāi)始報數，那么在這個(gè)新的序列中，每個(gè)人報的相應數字為：
1,2，3,4....n-2
那么這樣的話(huà)是不是又把問(wèn)題轉化成了n-2階約瑟夫環(huán)的問(wèn)題呢？
后面的過(guò)程與前兩次的過(guò)程一模一樣，那么遞歸處理下去，直到最后只剩下一個(gè)人的時(shí)候，便可以直接得出結果
當我們得到一個(gè)人的時(shí)候（即一階約瑟夫環(huán)問(wèn)題）的結果，那么我們是否能通過(guò)一階約瑟夫環(huán)問(wèn)題的結果，推導出二階約瑟夫環(huán)的結果呢？
借助上面的分析過(guò)程，我們知道，當在解決n階約瑟夫環(huán)問(wèn)題時(shí)，序號為k1的人出列后，剩下的n-1個(gè)人又重新組成了一個(gè)n-1階的約瑟夫環(huán)，那么
假如得到了這個(gè)n-1階約瑟夫環(huán)問(wèn)題的結果為ans（即最后一個(gè)出列的人編號為ans），那么我們通過(guò)上述分析過(guò)程，可以知道，n階約瑟夫環(huán)的結果
(ans k)%n(n為當前序列的總人數)，而k = m%n
則有：
n階約瑟夫環(huán)的結果
(ans m % n)%n，那么我們還可以將該式進(jìn)行一下簡(jiǎn)單的化簡(jiǎn)：
當m<n時(shí)，易得上式可化簡(jiǎn)為：（ans m）% n
而當m>=n時(shí)，那么上式則化簡(jiǎn)為：（ans % n m%n%n）% n
即為：（ans % n m%n）% n
而 （ans m）% n = （ans % n m%n）% n
因此得證
(ans m % n)%n = （ans m）% n
這樣的話(huà)，我們就得到了遞推公式，由于編號是從0開(kāi)始的，那么我們可以令
f[1] = 0； //當一個(gè)人的時(shí)候，出隊人員編號為0
f[n] = (f[n-1] m)%n //m表示每次數到該數的人出列，n表示當前序列的總人數
而我們只需要得到第n次出列的結果即可，那么不需要另外聲明數組保存數據，只需要直接一個(gè)for循環(huán)求得n階約瑟夫環(huán)問(wèn)題的結果即可
由于往往現實(shí)生活中編號是從1-n，那么我們把最后的結果加1即可。
代碼：
#include <stdio.h>int main(){ int n, m, i, s = 0; printf ('N M = '); scanf('%d%d', &n, &m); for (i = 2; i <= n; i ) { s = (s m) % i; printf('%d\n',s); } printf ('\nThe winner is %d\n', s 1);}聯(lián)系客服
