“應(yīng)用順序表模擬實現(xiàn)約瑟夫問題”教學(xué)設(shè)計

摘要：在大學(xué)計算機基礎(chǔ)課程“數(shù)據(jù)結(jié)構(gòu)與算法（B）”教學(xué)中，案例應(yīng)用有助于學(xué)生融會貫通數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和相關(guān)算法。文章通過“應(yīng)用順序表模擬實現(xiàn)約瑟夫問題”這一案例，講述在解決約瑟夫問題過程中，應(yīng)用順序表的原因、過程和關(guān)鍵算法，并對主要教學(xué)內(nèi)容的講授時間和注意事項等給出建議。

關(guān)鍵詞：數(shù)據(jù)結(jié)構(gòu)；微課；順序表；約瑟夫問題；教學(xué)設(shè)計

1.課程定位

“數(shù)據(jù)結(jié)構(gòu)與算法（B）”是北京大學(xué)面向非計算機專業(yè)學(xué)生、培養(yǎng)計算思維與編程能力的一門本科生主干基礎(chǔ)課，目前在北京大學(xué)的所有理科院系開設(shè)。課程要求掌握的常用數(shù)據(jù)結(jié)構(gòu)包括順序表、鏈表、字符串、棧、隊列、二叉樹、Huffmn樹、樹、堆以及圖。針對每一種常用數(shù)據(jù)結(jié)構(gòu)，我們要求學(xué)生：

（1）從邏輯結(jié)構(gòu)、一組基本運算和存儲（實現(xiàn)）3個方面去理解、掌握數(shù)據(jù)結(jié)構(gòu)；

（2）對算法的時間和空間復(fù)雜性有一定的分析能力；

（3）針對簡單的應(yīng)用問題，應(yīng)能選擇合適的數(shù)據(jù)結(jié)構(gòu)及設(shè)計有效的算法解決。

課程中第一個講授的數(shù)據(jù)結(jié)構(gòu)是順序表，見圖1，它也是在軟件開發(fā)中應(yīng)用最為廣泛的一種數(shù)據(jù)結(jié)構(gòu)。其講授難點是如何讓學(xué)生用學(xué)到的順序表基本知識（相關(guān)算法和存儲實現(xiàn)）編程解決與線性表有關(guān)的應(yīng)用問題。約瑟夫（Josephus）問題是一個非常經(jīng)典的計算問題。講授如何使用順序表編程實現(xiàn)約瑟夫問題，有助于學(xué)生進一步了解順序表的基本知識點和特點，了解如何應(yīng)用順序表進行有效的算法設(shè)計。

2.教學(xué)目標(biāo)

講授內(nèi)容圍繞一個編程案例，幫助學(xué)生：

（1）復(fù)習(xí)并掌握順序表的存儲實現(xiàn)方法以及順序表上的基本運算；

（2）了解約瑟夫問題的背景和由來，理解計算機編程實踐過程中需求分析的作用；

（3）能應(yīng)用順序表編程實現(xiàn)約瑟夫問題以及類似問題；

（4）遇到問題能有意識應(yīng)用數(shù)據(jù)結(jié)構(gòu)與算法中所學(xué)知識。

3.教學(xué)內(nèi)容與知識點

約瑟夫問題是以弗拉維奧·約瑟夫斯（FlaVius Josephus）命名的，他是一世紀(jì)的一名猶太歷史學(xué)家。在Josephus留下的日記中，描述了這樣一個故事：在羅馬人占領(lǐng)喬塔帕特后，39個猶太人與Josephus及他的朋友躲到一個洞中，39個猶太人決定寧死也不要被敵人抓到，于是決定了一個自殺方式：41個人排成一個圓圈，由第1個人開始報數(shù)，每報數(shù)到第3人該人就必須自殺，然后再由下一個重新報數(shù)，直到所有人都自殺身亡為止。Josephus要他的朋友先假裝遵從，他將朋友與自己安排在第16個與第31個位置，于是逃過了這場死亡游戲。

Josephus把他的存活歸因于運氣或天意，但實際上對于任意給定的n（n個人）、s（第s個人開始報數(shù)）和m（第m個人出列），可以通過一個計算模型推斷出所有人員自殺的序列。微課程講授了解決約瑟夫問題的計算模型，并給出基于順序表來實現(xiàn)約瑟夫問題的算法和相關(guān)程序代碼。其中，所有參與游戲的人員可以通過順序表進行存儲和表示。圖2給出了一個基于順序表的數(shù)據(jù)表示實例。

與約瑟夫問題類似的還有17世紀(jì)法國數(shù)學(xué)家加斯帕在《數(shù)目的游戲問題》一文中講述的一個故事：15個教徒和15個非教徒在深海上遇險，必須將一半的人投入海中，其余的人才能幸免于難。于是他們想了一個辦法：30個人圍成一圓圈，從第1個人開始依次報數(shù)，每數(shù)到第9個人就將他扔人大海，如此循環(huán)進行直到僅余l(xiāng) 5個人為止。問怎樣排法，才能使每次投入大海的都是非教徒？綜合這個問題，可以提示學(xué)生如何進行需求分析和問題建模，鍛煉學(xué)生的思維能力。

在講授中，教師應(yīng)注意將問題進行簡化和擴展以提供課堂練習(xí)和課后練習(xí)，并留下課堂思考問題。如Josephus問題基于順序表實現(xiàn)的算法復(fù)雜性較大：要模擬整個游戲過程，時間復(fù)雜度大概在O（n×m）。當(dāng)n、m非常大（如上百萬、千萬）的時候，幾乎沒有辦法在短時間內(nèi)出結(jié)果。如何改進這個算法？教師可以啟發(fā)學(xué)生打破常規(guī)，運用數(shù)學(xué)策略。

課程的主要教學(xué)內(nèi)容和知識點見表1，教師還應(yīng)注意到不同知識點上時間的劃分以增強學(xué)生的掌握能力。同時，基于課堂規(guī)模的大?。▽W(xué)生人數(shù)的不同），教師還需注意適當(dāng)調(diào)整教授內(nèi)容的時長?？傮w來說，課堂規(guī)模越大，內(nèi)容與知識點教授的時間應(yīng)適當(dāng)延長，課堂與課后練習(xí)的講解也要分類并進行針對性分析；反之，講授的時間則可以適當(dāng)縮短。

4.課程特色

課程要求學(xué)生在熟悉順序表存儲結(jié)構(gòu)以及基本運算的基礎(chǔ)上，能夠針對具體應(yīng)用問題的要求和性質(zhì)，設(shè)計出相應(yīng)的有效算法解決實際問題。其課程特色包括：

（1）重視清楚理解和深入掌握基本概念、基本原理和基本方法等三個基本內(nèi)容。

（2）多方位教學(xué)。從回顧、問題介紹、問題實踐、實例、類似問題、課堂練習(xí)、課后練習(xí)、思考與總結(jié)等多方面逐步進行知識點強化。

（3）立體化教學(xué)。提供講義、程序、在線平臺、參考資料等多種學(xué)習(xí)資源，擴展學(xué)習(xí)內(nèi)容。

5.課程學(xué)習(xí)資源

（1）《算法與數(shù)據(jù)結(jié)構(gòu)——C語言描述（第2版）》（張乃孝著，高等教育出版社2006年出版）。

（2）《數(shù)據(jù)結(jié)構(gòu)與算法》（張銘等著，高等教育出版社2008年出版）。

（3）《C++編程思想》（Bruce Eckel著，劉宗田等譯，機械工業(yè)出版社2000年出版）。

（4）Introduction to Algorithms（Thomas H.Cormen等著，MIT Press出版，高等教育出版社影印2002年）。

（5）在線平臺：http：//hxsjjg.openjudge.cn/。

（6）在線練習(xí)：http：//hxsijg.openjudge.cn/2013 hxtest02/E/。

（7）在線練習(xí)：http：//poj.grids.cn/practice/1012。

（編輯：彭遠(yuǎn)紅）