淺談《計算思維》課程的教學內容與教學方法

馬小虎

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

關鍵詞：計算思維；教學內容；典型實例；教學方法

1 教學內容

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

第一章主要介紹計算思維的基本概念，學習計算思維的目的和意義，國內外研究計算思維的基本情況，計算思維的學習方法。

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

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

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

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

第六章討論了程序設計中的特定思維。主要內容包括：數據的類型與本質、變量的特定含義、有窮與無窮、程序的基本控制結構、問題求解的本質過程、效率與可讀性、程序的構造特性等內容。

第七章主要介紹了計算思維在其他學科中的應用。比如：有限元分析與計算、數值天氣預報、蒙特卡洛方法等內容。

2 典型實例

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

例1：漢諾塔問題

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

算法分析：

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

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

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

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

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

例2：過河問題

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

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

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

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

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

3 教學方法

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

4 結束語

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

參考文獻

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