資料結構實踐——猴子選大王

【項目 - 猴子選大王】

　　一群猴子，編号是1，2，3 …m，這群猴子（m個）按照1-m的順序圍坐一圈。從第1隻開始數，每數到第n個，該猴子就要離開此圈，這樣依次下來，直到圈中隻剩下最後一隻猴子，則該猴子為大王。輸入m和n，輸出為大王的猴子是幾号。

提示： （1）連結清單解法：可以用一個循環單連結清單來表示這一群猴子。表示結點的結構體中有兩個成員：一個儲存猴子的編号，一個為指向下一個人的指針，編号為m的結點再指向編号為1的結點，以此構成環形的鍊。當數到第n個時，該結點被删除，繼續數，直到隻有一個結點。 （2）使用結構數組來表示循環鍊：結構體中設一個成員表示對應的猴子是否已經被淘汰。從第一個人未被淘汰的數起，每數到n時，将結構中的标記改為0，表示這隻猴子已被淘汰。當數到數組中第m個元素後，重新從第一個數起，這樣循環計數直到有m-1被淘汰。 （3）該問題為計算機科學中的經典問題，很多實際的問題可以抽象到這種模型上來。感興趣的同學請搜尋“約瑟夫問題”。

［參考解答（c++實作）］