馬小虎

摘 要：介紹了新生研討課《計算思維》的主要教學(xué)內(nèi)容，給出了一些典型實例，探討了如何講授好該課程的一些教學(xué)方法。

關(guān)鍵詞：計算思維；教學(xué)內(nèi)容；典型實例；教學(xué)方法

1 教學(xué)內(nèi)容

《計算思維》課程是我們近年來給一年級新生開設(shè)的一門新生研討課，在實際講授該課程時我們采用了由唐培和、徐奕奕和王日鳳編著的《計算思維導(dǎo)論》作為參考教材。該參考教材主要教學(xué)內(nèi)容包括七章，這七章內(nèi)容可概括如下[1]：

第一章主要介紹計算思維的基本概念，學(xué)習(xí)計算思維的目的和意義，國內(nèi)外研究計算思維的基本情況，計算思維的學(xué)習(xí)方法。

第二章主要討論狹義計算思維的理論與技術(shù)基礎(chǔ)。其主要內(nèi)容包括：數(shù)據(jù)與符號在機器內(nèi)部是如何表示的，圖靈機及其計算思想，馮諾依曼機及其工作原理，非傳統(tǒng)計算方法與技術(shù)，還介紹了可計算性問題與計算復(fù)雜性問題。

第三章專門討論計算思維的邏輯基礎(chǔ)，主要介紹了布爾代數(shù)、命題邏輯、謂詞邏輯以及邏輯演算。

第四章重點介紹了計算思維的方法學(xué)。其主要內(nèi)容包括：問題求解過程、數(shù)學(xué)模型、數(shù)據(jù)存儲結(jié)構(gòu)、程序設(shè)計方法論，分析與討論了時空概念、抽象、局部化與信息隱藏、精確、近似與模糊、折中與中庸之道以及問題描述方法。

第五章重點介紹了計算思維的算法基礎(chǔ)。這一章首先介紹算法的基本概念、算法的性質(zhì)、算法的描述、算法的簡單分析方法等，然后介紹算法設(shè)計的基本思想與方法，最后介紹了幾個常用的經(jīng)典算法。

第六章討論了程序設(shè)計中的特定思維。主要內(nèi)容包括：數(shù)據(jù)的類型與本質(zhì)、變量的特定含義、有窮與無窮、程序的基本控制結(jié)構(gòu)、問題求解的本質(zhì)過程、效率與可讀性、程序的構(gòu)造特性等內(nèi)容。

第七章主要介紹了計算思維在其他學(xué)科中的應(yīng)用。比如：有限元分析與計算、數(shù)值天氣預(yù)報、蒙特卡洛方法等內(nèi)容。

2 典型實例

計算思維課程中具有大量的經(jīng)典案例。下面以經(jīng)典的遞歸算法和圖論方法給出兩個實例進行說明如下：

例1：漢諾塔問題

題目：把A桿上的全部64個金盤借助B桿全部移到C桿上，并仍保持原有順序疊好。操作規(guī)則：每次只能移動一個盤子，并且在移動過程中三根桿上都始終保持大盤在下，小盤在上，操作過程中盤子可以置于A、B、C任一桿上。

算法分析：

1）以C桿作為中介桿，將A桿n-1個金盤移動到B桿

2）將A桿中唯一剩下的一個金盤移動到C桿（此時A桿為空桿，取代C桿地位）

3）以A桿為中介，將B桿n-1個金盤移動到C桿

從以上分析可以看出漢諾塔問題是一個典型的遞歸問題。

當(dāng)n=1時，需要移動2^1-1=1次盤子，當(dāng)n=2時，需要移動2^2-1=3次盤子，當(dāng)n=3時，需要移動2^3-1=7次盤子，當(dāng)n=64時，則需要移動2^64-1=18446744073709551615次盤子，假設(shè)計算機每秒可移動1000萬個盤子，那么也需要花費大約58490年的時間。

例2：過河問題

題目：農(nóng)夫需要把狼、羊、菜和自己運到河對岸去，只有農(nóng)夫能夠劃船，除農(nóng)夫之外每次只能運一種東西，如果沒有農(nóng)夫看著，羊會偷吃菜，狼會吃羊。請考慮一種方法，讓農(nóng)夫能夠安全地安排這些東西和他自己過河。

算法分析：設(shè)一個四維向量（a，b，c，d）。令1表示在河的這邊，0表示在河的另一邊。a代表人，b代表狼，c代表羊，d代表菜。則人狼羊菜在河這一邊的狀態(tài)可用分量為1和0的四維向量表示。排除不可能的狀況，比如狼和羊在一邊（0，1，1，0），羊和菜在一邊（0，0，1，1）。則由窮舉法可知，最后可得到十個不同的四維向量。（1，1，1，1）為初始狀態(tài)，（0，0，0，0）為結(jié)果狀態(tài)。人為變化的主體，所以相鄰兩個向量第一個分量不同。

由圖可知，一共有兩種方案，兩種方案都需要七次才能把所有東西運過河。

方法一（紅線）：步驟1將羊帶到對岸；步驟2人獨自回去；步驟3將菜帶到對岸；步驟4人將羊帶回；步驟5將狼帶到對岸；步驟6人獨自回去；步驟7將羊帶到對岸

方法二（黑線）：步驟1將羊帶到對岸；步驟2人獨自回去；步驟3將狼帶到對岸；步驟4人將羊帶回；步驟5將菜帶到對岸；步驟6人獨自回去；步驟7將羊帶到對岸可以推廣到更加復(fù)雜的情況。這就是經(jīng)典算法中的圖論方法。

3 教學(xué)方法

《計算思維》課程是我們?yōu)橐荒昙壭律_設(shè)的研討課，選該課程的同學(xué)來自各個學(xué)院的不同專業(yè)，學(xué)生們一般沒有什么計算機基礎(chǔ)知識，更沒有編程基礎(chǔ)，所以在講授該課程時，講的是解決實際問題的思想和方法，而不是程序設(shè)計。該課程應(yīng)該注重培養(yǎng)學(xué)生的思想、方法、意識、興趣和能力，二不是灌輸一大堆概念與知識。通常由主講老師先講授第一章與第五章內(nèi)容，然后，由學(xué)生分組完成其他章節(jié)的演講，該新生研討課學(xué)校規(guī)定學(xué)生總?cè)藬?shù)限定在30人之內(nèi)，以便每個學(xué)生都至少有一次機會上臺演講一個主題，事先認真做好PPT，講完以后，由主講老師負責(zé)點評。通過這種師生互動、學(xué)生為主角的方式，同學(xué)們的積極性得到了充分的調(diào)動，有些同學(xué)還查閱了大量的教材之外的內(nèi)容，做出了非常漂亮的PPT，演講得也非常熟練、非常成功。

4 結(jié)束語

《計算思維》課程是一門新開設(shè)的新生研討課，我們還在不斷探索、實踐中，其教學(xué)內(nèi)容與教學(xué)方式還在不斷完善之中。在這里僅對我們已經(jīng)開展的一些實踐工作做一些初步總結(jié)，以便能跟同行們一起交流、一起提高。

參考文獻

[1]唐培和，徐奕奕，王日鳳編著.計算思維導(dǎo)論[M].桂林：廣西師范大學(xué)出版社，2012.