問題描述：n個(gè)人（編號(hào)0~(n-1))，從0開始報(bào)數(shù)锹雏，報(bào)到(m-1)的退出巴比，剩下的人繼續(xù)從0開始報(bào)數(shù)。求勝利者的編號(hào)逼侦。
http://blog.csdn.net/haoni123321/article/details/7178748
利用數(shù)學(xué)推導(dǎo)匿辩，下面是推導(dǎo)的過程：
（1）第一個(gè)被刪除的數(shù)為 (m - 1) % n。
（2）假設(shè)第二輪的開始數(shù)字為k榛丢，那么這n - 1個(gè)數(shù)構(gòu)成的約瑟夫環(huán)為k, k + 1, k + 2, k +3, .....,k - 3, k - 2铲球。做一個(gè)簡(jiǎn)單的映射。
k ? ? ? ? -----> ?0
k+1 ? ?------> 1
k+2 ? ?------> 2
...
k-2? ? ------> ?n-2
這是一個(gè)n -1個(gè)人的問題晰赞，如果能從n - 1個(gè)人問題的解推出 n 個(gè)人問題的解稼病，從而得到一個(gè)遞推公式，那么問題就解決了掖鱼。假如我們已經(jīng)知道了n -1個(gè)人時(shí)然走，最后勝利者的編號(hào)為x，利用映射關(guān)系逆推戏挡，就可以得出n個(gè)人時(shí)芍瑞，勝利者的編號(hào)為 (x + k) % n。其中k等于m % n褐墅。代入(x + k) % n ?<=> ?(x + (m % n))%n <=> (x%n + (m%n)%n)%n <=> (x%n+m%n)%n <=> (x+m)%n
（3）第二個(gè)被刪除的數(shù)為(m - 1) % (n - 1)拆檬。
（4）假設(shè)第三輪的開始數(shù)字為o洪己，那么這n - 2個(gè)數(shù)構(gòu)成的約瑟夫環(huán)為o, o + 1, o + 2,......o - 3, o - 2.。繼續(xù)做映射竟贯。
o ? ? ? ? -----> ?0
o+1 ? ?------> 1
o+2 ? ?------> 2
...
o-2 ? ? ------> ?n-3
這是一個(gè)n - 2個(gè)人的問題答捕。假設(shè)最后的勝利者為y，那么n -1個(gè)人時(shí)屑那，勝利者為 (y + o) % (n -1 )拱镐，其中o等于m % (n -1 )。代入可得 (y+m) % (n-1)
要得到n - 1個(gè)人問題的解持际，只需得到n - 2個(gè)人問題的解沃琅，倒推下去。只有一個(gè)人時(shí)选酗，勝利者就是編號(hào)0阵难。下面給出遞推式：
f [1] = 0;
f [ i ] = ( f [i -1] + m) % i; (i>1)
有了遞推公式，實(shí)現(xiàn)就非常簡(jiǎn)單了:
這個(gè)算法的時(shí)間復(fù)雜度為O(n)芒填，空間復(fù)雜度為常數(shù)。相對(duì)于模擬算法已經(jīng)有了很大的提高空繁。算n殿衰，m等于一百萬，一千萬的情況不是問題了盛泡∶葡椋可見，適當(dāng)?shù)剡\(yùn)用數(shù)學(xué)策略傲诵，不僅可以讓編程變得簡(jiǎn)單凯砍，而且往往會(huì)成倍地提高算法執(zhí)行效率。
