約瑟夫環問題

約瑟夫環問題的原來描述為，設有編号為1，2，……，n的n(n>0)個人圍成一個圈，從第1個人開始報數，報到m時停止報數，報m的人出圈，再從他的下一個人起重新報數，報到m時停止報數，報m的出圈，……，如此下去，直到所有人全部出圈為止。當任意給定n和m後，設計算法求n個人出圈的次序。  稍微簡化一下。

      問題描述：n個人（編号0~(n-1))，從0開始報數，報到(m-1)的退出，剩下的人繼續從0開始報數。求勝利者的編号。 

  1. 利用數組或者list連結清單進行模拟操作過程，這裡就不再說了.....

  2. 利用數學推導，如果能得出一個通式，就可以利用遞歸、循環等手段解決。下面給出推導的過程：

        （1）第一個被删除的數為 (m - 1) % n。

        （2）假設第二輪的開始數字為k，那麼這n - 1個數構成的約瑟夫環為k, k + 1, k + 2, k +3, .....,k - 3, k - 2。做一個簡單的映射。

             k         ----->  0 

             k+1    ------> 1 

             k+2    ------> 2 

               ... 

             k-2    ------>  n-2 

        這是一個n -1個人的問題，如果能從n - 1個人問題的解推出 n 個人問題的解，進而得到一個遞推公式，那麼問題就解決了。假如我們已經知道了n -1個人時，最後勝利者的編号為x，利用映射關系逆推，就可以得出n個人時，勝利者的編号為 (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）第二個被删除的數為(m - 1) % (n - 1)。

        （4）假設第三輪的開始數字為o，那麼這n - 2個數構成的約瑟夫環為o, o + 1, o + 2,......o - 3, o - 2.。繼續做映射。

             o         ----->  0 

             o+1    ------> 1 

             o+2    ------> 2 

             o-2     ------>  n-3 

         這是一個n - 2個人的問題。假設最後的勝利者為y，那麼n -1個人時，勝利者為 (y + o) % (n -1 )，其中o等于m % (n -1 )。代入可得 (y+m) % (n-1)

         要得到n - 1個人問題的解，隻需得到n - 2個人問題的解，倒推下去。隻有一個人時，勝利者就是編号0。下面給出遞推式：

          f [1] = 0; 

          f [ i ] = ( f [i -1] + m) % i; (i>1) 

        有了遞推公式，實作就非常簡單了，給出循環的兩種實作方式。再次表明用标準庫的便捷性。