趣味程式設計：約瑟夫環問題

問題來曆

據說著名猶太曆史學家 Josephus有過以下的故事：在羅馬人占領喬塔帕特後，39 個猶太人與Josephus及他的朋友躲到一個洞中，39個猶太人決定甯願死也不要被敵人抓到，于是決定了一個自殺方式，41個人排成一個圓圈，由第1個人開始報數，每報數到第3人該人就必須自殺，然後再由下一個重新報數，直到所有人都自殺身亡為止。然而Josephus 和他的朋友并不想遵從。首先從一個人開始，越過k-2個人（因為第一個人已經被越過），并殺掉第k個人。接着，再越過k-1個人，并殺掉第k個人。這個過程沿着圓圈一直進行，直到最終隻剩下一個人留下，這個人就可以繼續活着。問題是，給定了和，一開始要站在什麼地方才能避免被處決？Josephus要他的朋友先假裝遵從，他将朋友與自己安排在第16個與第31個位置，于是逃過了這場死亡遊戲。

數學模型

已知n個人（以編号1，2，3...n分别表示）圍坐在一張圓桌周圍。從編号為k的人開始報數，數到m的那個人出列；他的下一個人又從1開始報數，數到m的那個人又出列；依此規律重複下去，直到圓桌周圍的人全部出列。通常解決這類問題時我們把編号從0~n-1排列，最後結果+1即為原問題的解。對任意給定的n、k、m，

(1)假設最後一個人為勝利者，那麼勝利者是原來的第幾個人。

(2)求按出列次序得到的n個人員的順序表。

思路

連結清單方法

   這是約瑟夫環問題的實際場景，通過輸入n,m,k三個正整數，來求出列的序列。采用的是循環連結清單的資料結構

   解決問題的核心步驟：

       1.建立一個具有n個鍊結點，無頭結點的循環連結清單

       2.确定第1個報數人的位置

       3.不斷地從連結清單中删除鍊結點，直到連結清單為空