今天看了一道算法問題：n個人（編号0~(n-1）），從0開始報數，報到m-1的退出，剩下的人繼續從0開始報數，求勝利者的編号。
其實這是一個約瑟夫（ Josephus problem）問題，原始的想法是采用數組或者連結清單結構模拟整個過程，總的時間複雜度為O（mn）。後來看到更好的解法，采用遞歸思想，它是這樣描述的（引用：http://baike.baidu.com/view/213217.htm）：
我們知道第一個人（編号一定是（m-1） mod n) 出列之後，剩下的n-1個人組成了一個新的約瑟夫環（以編号為k=m mod n的人開始）：
k k+1 k+2 ... n-2,n-1,0,1,2,... k-2
并且從k開始報0。
現在我們把他們的編号做一下轉換：
k --> 0
k+1 --> 1
k+2 --> 2
...
...
k-2 --> n-2
變換後就完完全全成為了（n-1）個人報數的子問題，假如我們知道這個子問題的解：例如x是最終的勝利者，那麼根據上面這個表把這個x變回去不剛好就是n個人情況的解嗎？！！變回去的公式很簡單，相信大家都可以推出來：x'=(x+k) mod n
如何知道（n-1）個人報數的問題的解？對，隻要知道（n-2）個人的解就行了。（n-2）個人的解呢？當然是先求（n-3）的情況 ---- 這顯然就是一個倒推問題！好了，思路出來了，下面寫遞推公式：
令f表示i個人玩遊戲報m退出最後勝利者的編号，最後的結果自然是f[n]
遞推公式
f[1]=0;
f=(f+m) mod i; (i>1）
但是對于這個解釋，一直沒搞明白，尤其是最初我的想法是下面這個過程（例如n=5，m=3）：
也許很多人看了會笑，本人确實在這卡了很長時間，總想不明白遞歸的過程，⊙﹏⊙b汗！！
後來，經過與同學的讨論，終于找到了問題所在，我沒有深刻了解遞歸的含義，正确的過程如下：
其實，遞歸關系式的描述的僅僅是相鄰兩個過程之間的關系，不能放到整個計算過程中。
寫下來對自己來說引以為戒，希望對有相同困惑的同學有所幫助，或者大家都沒我這麼笨，
為了加深了解，自己總結一下上面遞歸公式的推導思路：
1. 首先來說，想要從n的規模減少到n-1的規模，是一種很直接的想法，但是這兩個問題之間有什麼關系呢？
答案是：沒關系。
2. 那麼怎麼繼續呢？雖然f（n）和f（n-1）之間沒有直接的關系，但是下面的過程卻将它們聯系了起來：
第二行是f（n）執行的第二步（這裡m=k），那麼很顯然，第一行和第二行最終求得的結果是一樣的，因為它們是同一過程的第一步和第二步。
現在再看看第二行和第三行f（n-1），恰好滿足下面這個關系；
k = (0+k) % n
k+1 = (1+k) % n
...
k-2 = (n-2 + k) % n
假如第二行最終的結果為x，那麼f（n）的結果就是x（正如前面所說，這兩個步驟是一個過程），并且可以知道f（n-1）的最終結果為y，那麼有下面的關系：
x = (y + k) % n
也就是：
f(n) = [f(n-1) + k] % n
3. 上面得到了遞推關系式，那麼我們想求f(n)，隻要求出f(n-1)即可，這樣一直遞歸下去，f(1) = 0（因為這是隻包含一個元素0的情況）。
4. 到此為止，遞歸公式得到了：
f(1) = 0
f(i) = [f(i-1) + k] % i (i=2, 3, ... , n)
解釋完畢，再接再厲！