基于Josephus問題的C語言教學(xué)設(shè)計分析

劉東良

C語言教學(xué)案例較多，內(nèi)容涉及較多學(xué)科內(nèi)容，無疑增大了初學(xué)者的學(xué)習(xí)認(rèn)知負(fù)擔(dān)。為滿足C語言的教學(xué)需要，以一例"Josephus問題"貫通全部教學(xué)內(nèi)容的方式設(shè)計案例。通過Josephus問題的多種變形描述，使其內(nèi)容覆蓋標(biāo)準(zhǔn)C語言的全部知識單元，這樣設(shè)計能大大的減輕C語言學(xué)習(xí)者的學(xué)習(xí)難度，無需費時費力在求解問題本身的理解上，從而使學(xué)生能更好地理解、掌握C語言基礎(chǔ)知識，一例貫通，舉一反三。同時，增加無窮的樂趣和探索精神；加深學(xué)習(xí)者對C語言知識深度理解和靈活掌握；盡早盡快掌握C語言內(nèi)容和編程技能，能夠進行簡單的應(yīng)用程序設(shè)計。

1 Josephus問題和求解

據(jù)說古代羅馬軍隊中有一種懲罰習(xí)慣：如一個連隊因怯懦、反叛或其他理由受到懲罰時，采用"見十去一（decimatio）"的辦法進行處罰，即將隊伍中凡是站在10的倍數(shù)位置上的人處死。有關(guān)的事例可以追溯到公元前5世紀(jì)。類似的方法在古代的民事戰(zhàn)爭中被使用，但不一定是"見十去一"，也有其他的淘汰比率，如"見二十去一（vicesimatio）"、"見百去一（centesimatio）"等等。Josephus問題就是從此演變而來。

Josephus問題的基本形式是將k個子排成一圈，在這個圈中以某子為起點，m個m個數(shù)子，將每次數(shù)到的第m子去掉，直到去掉k－n子為止。問保留下來的n子在原來的圈中應(yīng)排在哪些位置上。

Josephus問題的求解是數(shù)學(xué)問題，用計算機語言設(shè)計程序求解各種約瑟夫及其變形問題具有現(xiàn)代意義和價值。蘇格蘭數(shù)學(xué)家Peter Guthrie Tait給出這個問題的通解后，Josephus＇Problem，又被稱為 Tait＇s Problem。

這就是泰特的算法。該算法是一種遞推的解法。n是總數(shù)，m是報數(shù)即間隔數(shù)，而i是循環(huán)變量，注意它是從2開始的初始條件，r＋1為結(jié)果又稱Josephus Number約瑟夫數(shù)。

至今可以檢索到許多種算法描述Josephus問題。在這些算法中，主要是利用一維數(shù)組或者循環(huán)鏈表進行求解。一般地，假設(shè)有一組數(shù)據(jù)構(gòu)成一個序列圈（序列的最后一個數(shù)據(jù)視為與第一個數(shù)據(jù)相鄰接）。要求從第s個數(shù)據(jù)開始計數(shù)，計數(shù)到m時彈出該數(shù)據(jù)，然后從它的下一個數(shù)據(jù)重新開始計數(shù)，計數(shù)到m時又彈出該數(shù)據(jù)，……，直到彈出序列中的所有數(shù)據(jù)（或只剩下一個或若干數(shù)據(jù)）為止。對于任意給定的自然數(shù)s和m，試求出這組數(shù)據(jù)的彈出次序。這種描述形式的Josephus問題隱藏了k值，而且對數(shù)據(jù)類型沒有具體要求，數(shù)據(jù)元素可以是整數(shù)、實數(shù)、字符或字符串?dāng)?shù)據(jù)，甚至還可以是結(jié)構(gòu)體，通用性好，實用性強。

2 C語言教學(xué)單元設(shè)計分析

用C語言實現(xiàn)不同Josephus問題的解法，以Josephus問題描述C語言的各知識點，進行一例貫通式教學(xué)設(shè)計。

2.1 變量和結(jié)構(gòu)化設(shè)計分析

以變量代表子，體現(xiàn)變量存儲數(shù)據(jù)的作用。Josephus問題有k個子，起點位置s，m個數(shù)子，保留的n子等4個變量。對Josephus問題變形可以擴展更多的變量，比如，在執(zhí)行程序前，猜哪幾個是獲勝者，能得到游戲者的成績，設(shè)定一個猜中數(shù)w變量；再如，最后必須相鄰的兩個子ki，ki＋1的編號或位置；以及報數(shù)時方向順時針或逆時針；或者將固定m改為不定密碼等更多變量。

使用整型數(shù)據(jù)類型的5個變量實現(xiàn)Josephus。學(xué)習(xí)while循環(huán)，switch、if條件，順序三種基本結(jié)構(gòu)的應(yīng)用；小孩使用5個整型變量描述，T是宏，大小不可改變；開始位置，報數(shù)，獲勝數(shù)三個變量；使用＃define定義5整型變量。使用C語言中的整型、字符型或者浮點類型僅僅是順序編號的標(biāo)示問題。

以變量代表子的解法能深刻揭示Josephus問題的本質(zhì)，需要C語言的知識也是最富技巧性。如switch和goto語句使得程序運行起來，無限和有限循環(huán)while、for語句則揭示計算機擅長的重復(fù)工作，變量的順序則明確C語言的語句順序執(zhí)行的重要性。

2.2 數(shù)組設(shè)計分析

以靜態(tài)數(shù)組定義固定k，限制程序的實用性。k個子用數(shù)組表示而且是靜態(tài)的數(shù)組。對于數(shù)學(xué)問題使用靜態(tài)數(shù)組就可很好解決Josephus問題，數(shù)組在理解和使用時都比較簡潔方便。利用一維數(shù)組求解Josephus問題時，數(shù)組的大?。磾?shù)組元素的個數(shù)）由k值確定。在定義數(shù)組之前，必須先給定k值。這個先決條件限制了這類算法的實用性，因為在許多應(yīng)用領(lǐng)域，事先不知道k的確切值。C／C＋＋語言定義數(shù)組的大小，要求使用常量或常變量，為了適應(yīng)k值，經(jīng)常需要"大開小用"（不可能使用修改源代碼的方法），浪費內(nèi)存資源。此外，如需要輸出字符型數(shù)據(jù)（如姓名或字符類型的編號等），則需使用二維數(shù)組進行描述。利用數(shù)組求解Josephus問題的算法比較簡練，易于描述。

數(shù)組是有序的、線性的、連續(xù)的結(jié)構(gòu)，要模擬Josephus問題的環(huán)或圈結(jié)構(gòu)，可以使用i＝（i＋1）%T；構(gòu)成"圈"，即當(dāng)循環(huán)變量i加1與總數(shù)相等時，i重新歸為0，實現(xiàn)了當(dāng)沿著數(shù)組"直線"向前數(shù)時，到最后一個元素后，跳回至第一個元素。注意C語言數(shù)組下標(biāo)從0開始，所以i要加1。另外，還可以使用下面三種表達方式達到同樣效果。

修改小孩數(shù)組總數(shù)可改變T的大小，一般小于50，便于整個程序在較短時間內(nèi)完成。N＋1，N－1，N＊m則分別實現(xiàn)數(shù)組元素后移，數(shù)組元素刪除和一次申請所有空間的算法，體現(xiàn)數(shù)組的不同應(yīng)用。

2.3 指針設(shè)計分析

動態(tài)數(shù)組描述不定K，效率高通用性好。k個子用數(shù)組表示，是動態(tài)的即k子數(shù)不定，程序根據(jù)輸入的不同值計算得到最后結(jié)果。在實際程序應(yīng)用中，或者考慮大數(shù)據(jù)量運算或者考慮效率，往往采用堆棧動態(tài)數(shù)組比較合適，既能高效率地執(zhí)行程序，又能保障結(jié)果準(zhǔn)確。

用整數(shù)i來代替p［i］，將初始序列看成一個整數(shù)序列存儲在向量p中，p［i］出列，將p［i＋1］，……，p［n］前移一個元素，將p［i］放入p［n］中，最后出列放在p［1］中。指向各編號的position指針形成動態(tài)數(shù)組，該程序可不限定k子個數(shù)，使程序的通用性更好。

2.4 函數(shù)設(shè)計分析

函數(shù)進行模塊化設(shè)計，理解C語言驅(qū)動機制。C語言又稱函數(shù)語言，其函數(shù)設(shè)計簡潔，沒有函數(shù)與過程區(qū)分。我們可以很容易地將各種設(shè)計封裝成函數(shù)，進行模塊化設(shè)計；學(xué)生也比較容易理解函數(shù)的復(fù)用意義和模塊化好處，難點是函數(shù)調(diào)用機制的理解。

C語言函數(shù)調(diào)用遵循嵌套調(diào)用的原則。設(shè)計一個遞歸的Josephus問題演示函數(shù)調(diào)用機制。JosephusRecur遞歸函數(shù)，函數(shù)參數(shù)依次為k子總數(shù)，開始報數(shù)位置，間隔報數(shù)，猜數(shù)和離開時序數(shù)。

只有封裝成函數(shù)，才能直接或間接調(diào)用自己，從而形成遞歸調(diào)用。函數(shù)模塊化設(shè)計在許多Josephus問題解法中都有所使用。

2.5 結(jié)構(gòu)設(shè)計

結(jié)構(gòu)數(shù)組封裝K子多元信息。用結(jié)構(gòu)數(shù)組封裝k子的信息，比如設(shè)計小孩或八仙的名稱、年齡、生日等不同類型變量。這些成員可以靜態(tài)或動態(tài)設(shè)定，從而達到使用不同類型變量和自定義數(shù)據(jù)類型的目的。同時，理解數(shù)組與結(jié)構(gòu)重要區(qū)別之一是數(shù)組為同類型而結(jié)構(gòu)體可以是不同數(shù)據(jù)類型的成員。

結(jié)構(gòu)數(shù)組并沒有使用新的解法，只是比數(shù)組增加了必要的輔助信息，這是從簡單的樣例程序到實用商業(yè)程序發(fā)展的重要步驟。

2.6 鏈表設(shè)計分析

結(jié)構(gòu)鏈表模擬Josephus問題過程，直觀形象。因為Josephus問題本身是環(huán)型，即首尾相聯(lián)結(jié)，循環(huán)依次報數(shù)。所以利用循環(huán)鏈表進行Josephus問題求解，是一種比較理想的方法，主要體現(xiàn)在：一個循環(huán)鏈表可以被看成是一個圈，可以直接映射問題本身；一般采用動態(tài)分配內(nèi)存的方法建立循環(huán)鏈表（即"按需分配"），可節(jié)省存儲空間，而且不必事先給定n的值，實用性強；從循環(huán)鏈表中的任何一個結(jié)點出發(fā)，沿指針指向進行搜索，可以訪問到鏈表中的所有結(jié)點；刪除鏈表中相應(yīng)的結(jié)點元素值并釋放該結(jié)點。釋放結(jié)點可以縮短鏈表的長度（即可降低算法的時間復(fù)雜度），且有利于存儲資源的再利用。但利用循環(huán)鏈表求解Josephus問題的算法相對較復(fù)雜，需要一定的基礎(chǔ)和技巧。

結(jié)構(gòu)鏈表的設(shè)計主要意圖是學(xué)習(xí)鏈表的知識內(nèi)容，直觀展示指針的"指向"作用，通過指針的"拉鏈"、"斷鏈"、"脫鏈"等顯示鏈表操作過程。

在結(jié)構(gòu)鏈表的基礎(chǔ)上可進一步擴展單向和雙向以及循環(huán)鏈表的內(nèi)容。雙向循環(huán)鏈表豐富了Josephus問題多樣性。通過結(jié)構(gòu)體包含編號，密碼（報數(shù)）和方向?qū)崿F(xiàn)不定報數(shù)和不定方向，充分展示Josephus問題趣味性?？蓭ь^結(jié)點的單鏈表結(jié)構(gòu)定義和不帶頭結(jié)點的單環(huán)鏈表結(jié)構(gòu)定義設(shè)計。

通過指針，C語言可很容易地實現(xiàn)鏈表，從而更好地理解指針的作用及其重要性。

2.7 隊列設(shè)計分析

以隊列形式反映Josephus問題本質(zhì)。Josephus問題本質(zhì)上是一種環(huán)型隊列，故使用"先進先出"隊列結(jié)構(gòu)可更好地實現(xiàn)Josephus問題求解。隊列是一種常用的數(shù)據(jù)結(jié)構(gòu)，一般C語言教學(xué)中，沒有或很少涉及到。通過Josephus問題理解和掌握隊列結(jié)構(gòu)則是很容易達到的。

2.8 棧設(shè)計分析

以棧體現(xiàn)函數(shù)調(diào)用機制。為了展現(xiàn)程序執(zhí)行時，函數(shù)調(diào)用機制與"先進后出"的棧特性，設(shè)計雙棧完成Josephus問題解法，程序運行效果特別形象直觀。函數(shù)調(diào)用機制是現(xiàn)代程序語言特性，掌握堆棧就是掌握程序的驅(qū)動原理。

2.9 樹設(shè)計分析

結(jié)構(gòu)決定效率。以樹結(jié)構(gòu)可以提高Josephus程序運行效率。使用Range Tree實現(xiàn)Josephus數(shù)的計算是效率比較高的，時間復(fù)雜度為O（nlogn），而一般鏈表為O（n＊m），數(shù)組為 O（n2）。其中n為總數(shù)，m為報數(shù)。范圍樹Range Tree以樹狀層次結(jié)構(gòu)代替線性結(jié)構(gòu)，提高查找效率，從而提高程序整體效率。

2.10 文件設(shè)計分析

文件記錄Josephus問題的元數(shù)據(jù)和過程。C語言的標(biāo)準(zhǔn)輸入輸出包含了文件操作，是在初學(xué)階段就應(yīng)該掌握的基礎(chǔ)內(nèi)容。從文件讀取Josephus問題的元數(shù)據(jù)，執(zhí)行后，將解法過程和結(jié)果都保存到文件中去，便于理解。在結(jié)果文件中：

第一行5是總數(shù)，1是開始位置，3是間隔報數(shù)，1是最后一個獲勝；第二行至第六行是每次在圈里的號碼，豎線后是出圈的號碼。

2.11 位運算設(shè)計分析

位運算展示Josephus問題特性。通常位運算沒有比較好的教學(xué)案例，而Josephus問題的一個特例，當(dāng)m為2即每次向后移動即間隔一個子時，使用位運算則能非常高效地求出約瑟夫數(shù)。

從二進制的角度理解為：將n左移1位（即乘2），然后將最右端設(shè)置為1（即加1），最后將左端的1置為0（即減去2＊n的向下取的2的冪）。更簡單的描述是將n的二進制表示循環(huán)左移動一位！如：n為1011001－＞0110011－＞1100110。對應(yīng)代碼：

該語句是每次把N二進制最右邊的1修改為0，直到最左邊的1為止.這種方法也可以用來計算N二進制中1的數(shù)目，當(dāng)N二進制中1的數(shù)目比較小的時候算法的效率很高。

2.12 程序測試設(shè)計分析

測試是學(xué)習(xí)計算機語言必須學(xué)習(xí)的內(nèi)容之一。測試是檢驗程序正確性并完善程序。它不同于程序編寫、調(diào)試，而是對既成的程序，運行特定測試數(shù)據(jù)（稱為測試用例）驗證其結(jié)果正確性。調(diào)試程序階段主要活動在程序本身的編寫過程，執(zhí)行或簡單得到結(jié)果后即告結(jié)束，而測試剛剛開始。

窮舉法測試八仙定座。呂洞賓在2號位不變，其它仙人隨機，使用兩粒骰子產(chǎn)生點數(shù)進行報數(shù)，所以有11種可能，呂洞賓是不可能坐上首席的，窮舉法測試八仙定座程序正確性。

3 Josephus問題的C語言設(shè)計教學(xué)效果

實際教學(xué)中，整理、設(shè)計52個Josephus問題解法，并利用圖形函數(shù)設(shè)計了22個動畫演示程序。學(xué)生對Josephus問題比較感興趣，還能主動思考求解Josephus問題的新方法，達到了良好的教學(xué)效果。

以Josephus問題典型案例，設(shè)計C語言教學(xué)內(nèi)容無疑是一次教學(xué)改革和探索，希望能不斷改進和完善，使得該研究取得更理想效果。

［1］沈康身.東方約瑟夫問題研究選析［J］.自然科學(xué)史研究，2003：22（1）：60－68.

［2］［美］格雷厄姆.具體數(shù)學(xué)［M］.西安：西安電子科技大學(xué)出版社，1992：116.

［3］郭世榮.方中通《數(shù)度衍》中所見的約瑟夫斯問題［J］.自然科學(xué)史研究，2002：21（1）：49－55.

［4］陳海山.Josephus問題的算法設(shè)計與應(yīng)用研究［J］.計算機工程與應(yīng)用，2007：43（1）：61－64.