王　勝

（犍為外國語實驗學校，四川　犍為　614400）

?

模擬淘汰程序的設計方法研究
——以“猴子選大王”程序為例

王勝

（犍為外國語實驗學校，四川犍為614400）

摘要：猴子選大王是一道經(jīng)典的程序設計題，文章指出，可以通過不同的設計方法來實現(xiàn)：（1）模擬數(shù)組法。（2）模擬鏈表法。（3）stl l ist實現(xiàn)。（4）數(shù)學推導法。

關(guān)鍵詞：猴子選大王；模擬；鏈表；stl l ist；數(shù)學推導

問題：n只猴子圍成一個圈。從第一只猴子開始，從1開始依次報數(shù)，報到m的猴子離開。從這只離開猴子的下一只開始再從1開始報數(shù)，報到m的再離開。以此類推，直到最后剩下一只猴子為止。這只剩下的猴子就是大王?，F(xiàn)在編寫程序，輸入n和m，輸出大王的號碼。

1　模擬靜態(tài)數(shù)組法

學習了靜態(tài)數(shù)組后，可以直接用靜態(tài)數(shù)組來模擬淘汰的過程。

原理：設置n+1數(shù)組，初值為0，表示n只猴子都在圈子里，淘汰的猴子賦值為1。從數(shù)組1開始掃描，查看對應的值是否為0并計數(shù)，掃描到m個0后，把對應數(shù)組的值修改為1，表示淘汰。繼續(xù)執(zhí)行下一步的操作，直到里面只剩下一只猴子結(jié)束。最后從1開始掃描數(shù)組，找到一個為0的結(jié)束，該下標對應的猴子為大王。關(guān)鍵：0，1表示猴子是否在圈中，掃描的時候忽略不在的猴子，設置結(jié)束標記，能正常結(jié)束。

優(yōu)點：理解容易，代碼較易實現(xiàn)。

缺點：效率差，每次都要掃描全部的數(shù)據(jù)，還要判斷該位置上是否有猴子。對于大一些的數(shù)據(jù)運行時間長。

2　模擬鏈表法

數(shù)組法在淘汰過程中要不斷判斷對應的值是否為0，即猴子是否在圈內(nèi)，掃描判斷效率低。學習鏈表后，我們可以用環(huán)形鏈表實現(xiàn)，每個節(jié)點代表一個猴子，掃描淘汰過程中直接刪除該結(jié)點，避免了判斷及重復掃描浪費時間。

優(yōu)點：執(zhí)行效率比數(shù)組高，只掃描不判斷，提高了運行時間，臨時開辟存儲空間，不用預先定義避免了內(nèi)存浪費。

缺點：鏈表理解編寫有一定的難度。

3　stl list實現(xiàn)

自從有了stl后，可借助里面的容器list（鏈表）快速實現(xiàn)鏈表功從而進行程序設計及代碼的編寫。解題思路：生成一圈猴子，邊掃描邊刪除，快速模擬淘汰過程。

優(yōu)點：代碼簡潔，很好的實現(xiàn)了模擬淘汰的操作。

缺點：學習新的程序知識。

4　數(shù)學推導法

模擬法效率很低，其時間復雜度為O（mn）。當n和m很大時，很難在短時間內(nèi)得出結(jié)果。如果能得出一個通式，就可以利用遞推來快速解決。下面給出推導的過程（假設從0到N-1）：

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

（2）假設第二輪的開始數(shù)字為k，那么這n-1個數(shù)構(gòu)成的約瑟夫環(huán)為k，k+1，k+2，k+3，.....，k-3，k-2。做一個簡單的映射。

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

（4）假設第三輪的開始數(shù)字為o，那么這n - 2個數(shù)構(gòu)成的約瑟夫環(huán)為o，o+1，o+2，......o-3，o-2.。繼續(xù)做映射。

這是一個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）

有了這個公式，我們要做的就是從1-n順序算出f的數(shù)值，最后結(jié)果是f［n］。因為實際生活中編號總是從1開始，我們輸出f［n］+1，由于是逐級遞推，甚至不需要保存每個f，程序也是異常簡單：

Intans［10000］=｛0｝，i，n，m； //ans數(shù)組保存結(jié)果，還可用stl 中vector容器，甚至用一個變量代替。式進行計算

優(yōu)點：運行速度快，代碼簡練。

缺點：數(shù)學推導過程要仔細推敲，慢慢消化理解。

對于猴子選大王這類環(huán)形問題，我們可以用不同的方法、不同的技術(shù)來解決，如何選擇最優(yōu)的設計方案呢，這就要我們在平時的學習中不斷的積累知識，多思善想。適當?shù)剡\用數(shù)學策略，不僅可以讓編程變得簡單，而且往往會成倍地提高算法執(zhí)行效率。在此拋磚引玉，希望大家能提出更優(yōu)、更易解決問題的方法。

Research on Simulation Program Design Method：Taking Choose Monkey King Program as an Example

Wang Sheng
（Qianwei Foreign Language Experimental School， Qianwei614400， China）

Abstract：Choose Monkey King is a classic programming problem, the article points out that can be done by different design methods: (1) the simulation method of array. (2) simulation list. (3) the stl list implementation. (4) mathematical deduction.

Key words：choose monkey king; simulation; list; stl list; mathematical deduction

作者簡介：王勝（1975-），男，四川犍為。