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

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

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

1.課程定位

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.課程特色

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

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

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

（3）立體化教學(xué)。提供講義、程序、在線平臺(tái)、參考資料等多種學(xué)習(xí)資源，擴(kuò)展學(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著，劉宗田等譯，機(jī)械工業(yè)出版社2000年出版）。

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

（5）在線平臺(tái)：http：//hxsjjg.openjudge.cn/。

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

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

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