面向計算思維培養的算法教學案例

李 旭，趙秀巖，康 麗，沈 嵐，姚春龍

（大連工業大學 信息科學與工程學院，遼寧 大連 116034）

0 引 言

計算機基礎課程是高等院校非計算機專業學生的計算機入門課程，旨在培養學生利用計算機去獲取、分析、加工、處理、傳遞信息，解決實際問題的思路和能力，為將來使用計算機解決各自專業問題打下良好的基礎。然而，根據多年的授課情況看，學生在學完整門課程后雖然能夠了解和掌握大學計算機基礎課程的基本知識和技能，但是往往不能系統、全面地認識和應用這些知識，在后續的專業學習中遇到問題時，想不到用計算機知識去解決，或者想使用計算機卻不知道如何應用學過的知識。因此，為了更好發揮計算機基礎課程在高校人才培養課程體系中的基礎支撐作用，培養出適合時代需要的具有創新思維和綜合應用能力的各領域專業人才，開展從“基于知識的技能傳授”向“基于應用的思維能力培養”轉變的計算機基礎課程教學改革是必要且迫切的。

2006年3月，美國卡耐基·梅隆大學計算機科學系主任周以真首次提出并定義計算思維的概念，周教授認為計算思維是運用計算機科學的基礎概念進行問題求解、系統設計、人類行為理解等涵蓋計算機科學廣度的一系列思維活動[1]。計算思維代表著一種普遍的認識和一類普適的技能，在科學技術日新月異的信息時代，我們每一個人都應該熱心于它的學習和運用。然而目前對于計算思維能力培養的認識，一定程度上還停留在對國外思想的吸收和消化階段。如何讓計算思維能力培養在課程教學中真正落地是需要深入探討和解決的問題。

1 傳統算法教學中存在的問題

獨立思考和解決問題的能力是高校人才培養的目標之一。美國著名心理學和計算機專家西蒙指出：當一個人接受一項任務，但又不知道如何去完成它時，他面臨的就是一個問題。西蒙將問題解決看做人類認知的三類信息加工過程之一。為解決某一特定問題而設計的確定的有限的步驟稱為算法。算法設計與分析在培養學生獨立思考、分析問題和解決問題能力方面具有重要作用。

然而在傳統的算法教學中，教師往往將教學重點放在算法的解釋上，教學方法通常采用“介紹—舉例—演示”三部曲教學法。算法解釋生澀乏味、案例選取不接地氣沒有吸引力，學生感覺沒有實際應用價值。這種授課方式下往往是老師講、學生聽，留給學生主動思考的空間少，久而久之使學生思維退化，導致懶學甚至厭學。

在面向思維培養的計算機基礎教學改革實施以來，我們充分認識到算法教學對培養學生解決問題能力的重要性，認識到傳統的算法教學之所以效果不佳其根本原因在于沒有掌握算法的本質——問題的建模、分解、抽象和自動化，在問題求解過程中沒有充分調動學生的主觀能動性、激發學生的求知欲。

圖1 泥濘城市

2 面向思維培養的算法教學改革與實踐

在實際生活中，圖的最小花費生成樹問題在城市水管、天然氣管道規劃、最少通信線路鋪設以及物流公司的最小成本分析等領域有著廣泛的應用，它也是算法設計中貪婪法的一個典型問題。以最小花費問題為例說明面向思維培養的算法教學改革與實踐。

2.1 通俗易懂的案例選取

泥濘城市[2]案例描述如下：假設有一座城市還未鋪上道路，下雨之后要在這座城市中行走是一件非常困難的事情，地面被雨水浸濕，滿是泥濘，車輛紛紛陷入泥沼之中，人們的鞋子上沾滿了污泥。于是市長痛下決心，一定要在一些道路砌上石磚，但是錢必須用在刀刃上，他不想浪費經費，因此他下達了以下兩個要求：

（1）必須鋪設足夠的道路，讓每個人都能從家里沿著鋪好的道路到達別人的房子。

（2）所花費的經費越少越好。在兩棟房子之間的道路上鋪上的石磚數代表了鋪路所需要的費用。

2.2 以問題為驅動引導學生主動思考、自主解決問題

通過設計一連串問題，問題之間有層次漸進關系，逐步引導學生深入思考、歸納總結，進而找出并描述解決問題的步驟。對于泥濘城市案例，設計的問題如下：

（1）設想這座小城僅有5棟房子和7條路（圖1）。為了連接所有的房子，且要使用最少的石磚，房子之間的每個方塊代表需在此鋪上一塊石磚，哪些道路必須鋪上石磚？

（2）將這5棟房子連接起來，至少需要鋪幾條路？

（3）如果已經選擇在房子A、B和B、C之間分別鋪設石磚，直接從房子A到房子C的道路還要不要鋪設？

（4）如果添加一條道路，使設計方案中產生了一個“循環路線”，即從一條路離開一棟房子后還能走另外一條路回到這棟房子，這條道路還要不要添加？

（5）鋪設方法是唯一的么？你能想到的使用最少石磚數的鋪法有幾種？

（6）請用自然語言把你鋪設最少石磚的方法描述出來。

（7）如果用圓圈表示地圖中的房子，用線條和數字表示地圖中的道路，計算機科學家們稱這種結構為圖。在圖中，圓圈代表的房子稱為節點，節點之間的線條代表泥濘的道路，每條道路的長度用線條旁的數字標明。請畫出與上述地圖相對應的圖結構。這種將房子縮寫成節點、道路表示為線條和數字的過程稱為問題建模。

（8）在圖中，如果從一個頂點到另一個頂點有路徑相連，我們稱這兩個頂點是連通的。如果圖中任意兩點都是連通的，該圖被稱為連通圖。那么上述求地圖中連接所有房子的最少石磚數是不是已經轉化為求連通圖的總長最短的路徑問題？在計算機科學中該類問題被定義為最小生成樹問題。該問題之所以被稱為“最小”是因為它要求擁有最小的石磚總數，“生成”代表了每一棟房子都和另外一棟連接起來，最終得到的正確方案的形狀看起來則像一棵“樹”——如果你從任一棟房子出發，都會有一條或多條道路從這里“分叉”出去，而這每一條分支稍后又會有其他的分支，但是兩條分支永遠無法回指或相交，如果你讓他們相交了，說明將有兩條道路能通往同一棟房子，則其中的一條必是浪費石磚的選擇。

（9）如圖2所示的大一點城市的布局圖，請畫出與布局圖相對應的圖結構。

圖2 大一點的泥濘城市

（10）是否能應用剛才設計出的最少石磚數算法，找出大一點城市的石磚鋪設方法？這個算法對于更大規模的相同問題是否依然有效？

（11）請用流程圖描述鋪設最少石磚數的算法，即用流程圖描述最小生成樹算法。

（12）你是否還能找出其他方法解決該問題？請用流程圖把解決步驟描述出來。

（13）解決最小花費問題，上述算法的執行步驟一樣嗎？哪種方法更優，請說明原因。

對于問題（1）這樣小規模的最小花費問題，學生通常很快就能得出最少需鋪設7塊石磚的最優方案，也會回答出連接5棟房子，至少需要鋪設4條路。問題（3）和問題（4）能夠讓學生充分思考并明確設計方案中一定不能存在循環線路。通過問題（5）和（6）的引導和提問，學生通常能自主歸納總結出以下兩種鋪設最少石磚的方法：①從一張空白地圖開始，按照路徑長度從小到大添加道路，逐步增加石磚直到全部房子都被連接起來，注意增加路徑時不能將兩個已經連接的房子再用其他道路連接起來，產生“循環”線路。當路徑長度相同時，改變添加路徑的順序，會產生不同的最終布局，但是最后的結果依然能保持需要石磚的總數最少。②從一個房子開始，遍歷與該房子或已連接房子相連接的其他房子，使用連接路徑中的最小長度添加道路，逐步增加石磚直到全部房子都被連接起來，注意增加路徑時不能產生循環線路。

問題（7）引導學生通過抽象、簡化建立能刻畫該類實際問題的一般模型，如圖3所示，使學生水到渠成地得出問題（8）的結論：該問題即為求解連通圖的總長最短的路徑問題。

圖3 問題建模

問題（9）和（10）引導學生驗證算法的正確性和有效性，歸納總結出求解該類問題的普適算法。問題（11）和（12）要求學生用流程圖準確、規范地描述出算法的步驟，自主“實現”計算機中經典的Kruskal算法或Prim算法。問題（13）引導學生通過比較執行步數判定算法的性能。

3 結 語

上述實例展示了面向計算思維培養的算法教學改革，在不改變教學大綱和內容的基礎上，通過改進教學方法，有意識地將與思維培養相關的問題分解、抽象和自動化的方法自然地融入到教學中，培養了學生獨立思考、主動參與、實際探究的能力。

精心設計的教學案例，以及學生與老師“風云際會”的互動過程大大增加了學生對知識的興趣，開啟他們探索知識的航程。通過對我校非計算機專業開展面向思維的算法教學改革實踐，學生的課堂活躍度大大提升，學習積極性、主動性高漲。