信息學奧林匹克競賽對中學生計算思維的培養

梁雪梅

摘? 要：中學是培養良好思維的關鍵時期，但是中學以基礎知識教育為主，忽略了學生的思維能力的培養，使得學生缺乏科學素養、工程素養和計算素養。而信息奧賽剛好彌補了這一短板，通過信息奧賽教學，尤其是算法教學來培養學生分析問題和解決問題的能力。因此，該文研究信息學奧林匹克競賽對中學生計算思維的培養，并以貪心算法教學為例，通過兩個具體問題，引導學生分析問題、建立模型并評價算法。以此找出算法的規律和設計算法的步驟，培養學生分析問題和解決問題的能力，培養學生的計算素養。

關鍵詞：信息奧賽? 計算思維? 貪心算法? 建模

中圖分類號：G642;R-4 ? ?文獻標識碼：A 文章編號：1672-3791（2019）09（c）-0118-02

美國卡內基·梅隆大學計算機科學系主任周以真（Jeannette M. Wing）教授在美國計算機權威期刊《Communications of the ACM》雜志上首次提出計算思維（Computational Thinking）。計算思維是運用計算機科學的基礎概念進行問題求解、系統設計、以及人類行為理解等涵蓋計算機科學之廣度的一系列思維活動[1，2]。即如何將看似困難的問題進行拆析、建模、抽象、轉換成計算機能進行信息處理或代碼執行的思維方法。這是解決實際問題的一種思維活動過程，也是一種有效解決問題的方法。

中小學階段是培養學生良好思維的最佳時期，特別是計算思維的培養，但是我國中小學階段的教育以基礎知識教育為主，缺乏對計算思維的培養，使得學生對問題的思考缺乏科學素養、工程素養和計算素養，從而導致學生在思考實際問題的解決方法時不嚴謹、不科學[3]。

信息學奧林匹克競賽即NOI競賽（National Olympiad in Informatics），是全國中學五大競賽之一。既然基礎知識教育缺乏計算思維的培養，那信息奧賽是如何提高學生的計算思維呢？

該文通過設計、實現和評價實際問題的算法來闡明信息學奧林匹克競賽對中學生計算思維的培養過程。同時還培養了學生分析問題、解決問題的能力，并通過不斷地解決問題、開拓創新，提高學生的創新能力[4]。

1? 基于信息奧賽的計算思維培養——以貪心算法教學為例

在信息奧賽中包含大量算法方面的考核，尤其是算法在實際問題中的應用。因此，在信息奧賽教學中更加側重算法教學，主要教學過程分為問題描述、問題分析與建模、算法評價與優化等[5]。通過該過程不斷提高學生素質和分析問題、解決問題的能力，培養學生的計算思維。該文以貪心算法為例，探究信息奧賽對中學生計算思維的培養。

1.1 問題描述

有n位同學參加學校文藝匯演，每位同學的表演時間已知。從0時刻開始陸續安排每位同學上場表演，每個表演的完成時間是從0時刻到個人表演結束的時間。請求出所有表演的總完成時間（所有表演完成時間之和）最短的上場順序。

例如：5位同學，表演時間分別為2min、6min、4min、9min、13min。

1.2 問題分析與建模

【輸入】同學集：S={1，2，3，4，5}，第i位同學的表演時間：tj∈Z+，j=1，2，…，n。

【輸出】最短總完成時間I，S的排列為i1，i2，…，in。

【問題分析】將表演時間按從小到大排序：2、4、6、9、13。則第一位同學的完成時間為2min，第二位同學的完成時間為（2+4）min，第三位同學的完成時間為（2+4+6）min，第四位同學的完成時間為（2+4+6+9）min，第五位同學的完成時間為（2+4+6+9+13）min。總的完成時間計算如下：

T=2+（2+4）+（2+4+6）+（2+4+6+9）+（2+4+6+9+13）

=2×5+4×4+6×3+9×2+13

=75

通過分析得出，則最短的總完成時間為75min。表演時間短的先上場，根據表演時間按從小到大排序，然后依次上場。因此，抽象出其目標函數和解。

【目標函數】I的總完成時間，。

需要注意的是，在一些更為復雜的問題求解中，目標函數還有一定的約束條件。

【解】I*：使得T（I*）最小，即T（I*）=min{T（I）|I為S的排列}。

1.3 算法評價與優化

對于所有文藝匯演上場順序的實例，使用該算法都能得到最優解嗎？我們用數學思維來驗證該算法的正確性。

證：假設上場順序m第i，j項上場順序相鄰且有逆序，即ti>tj，交換任務i和j得到上場順序n，其他次序不變，如圖1所示。

根據目標函數可知T（n）-T（m）=ti-tj﹤0。所以該算法得到的結果為最優解。

通過學校文藝表演，我們發現每次先讓表演時間最短的同學上場便可以得到最短的總完成時間，這就是貪心算法的應用。通過具體的實例，我們可以發現貪心算法總是做出當前最好的選擇，即考慮在某種意義上的局部最優解，而不是整體上的最優。因此，貪心算法的關鍵是貪心策略的選擇，沒有固定的算法框架。使用貪心算法解決問題的基本步驟是[6]：（1）建立問題的數學模型;（2）將問題分解為若干子問題;（3）求解子問題的局部最優解;（4）合并子問題局部最優解得到原問題的一個解。

那么，所有問題都能通過貪心算法來解決并獲得最優解嗎？我們再來探討另一個問題。

圣誕老人給同學們派發新年禮物，但是每位同學的背包只能裝6kg禮物，現在有4類禮物，禮物的重量和價值如表1所示。

如何選擇禮物，使得不超過背包承重范圍且禮物價值達到最大呢？

依舊使用貪心法來解決這個問題，貪心策略是先裝單位重量價值大的禮物，總重量不超過6kg。因此，各類禮物按照排序為。按照貪心策略選擇了禮物1之后，再禮物2或禮物3均會超出6kg，所以最終的選擇結果為禮物1和禮物4，最終的價值為9。但是，很明顯，選擇禮物2和禮物4的總重量為6kg且價值為11，顯然比價值9更好。

通過這個例子我們可以知道，通過貪心算法得到的解不一定是正解。這就涉及到算法設計的問題。那么，設計算法的步驟為：（1）問題建模;（2）算法選擇與描述;（3）證明該方法是否對所有實例都能得到最優解;（4）如果得不到最優解，請給出反例證明。

根據文藝匯演案例，引導學生分析問題并建立模型，找到貪心算法的規律。然后分析具體的貪心算法，讓學生明白使用貪心算法解決問題的基本步驟。然后，根據新年禮物選擇案例，讓學生明白貪心算法得到的解不一定是最優解，引導學生明白設計算法的步驟。使用具體的問題引入，引導學生學會分析問題和解決問題，培養學生的計算思維。

2? 結語

該文根據計算思維的概念和信息奧賽培養目標，探究信息學奧林匹克競賽對中學生計算思維的培養。通過分析中學生基礎知識教育，發現中學基礎教育缺乏計算思維的培養。因此，以貪心算法教學為例，根據文藝匯演問題，引導學生分析問題、一步步解決問題，得到貪心算法的規律和使用貪心算法解決問題的步驟，然后根據新年禮物選擇問題，引導學生發現貪心法得到的解不一定是最優解，引出設計算法的步驟。通過分析和解決具體問題，培養學生分析問題和解決問題的能力，提高學生的數學思維、工程思維和計算思維。

參考文獻

[1] Jeannette M.Wing.Computational Thinking[J].Communications of the ACM，2006，3（49）：33-35.

[2] 周以真.計算思維[A].中國科學技術協會學會學術部.新觀點新學說學術沙龍文集7：教育創新與創新人才培養[C].中國科學技術協會學會學術部：中國科學技術協會學會學術部，2007：6.

[3] 劉向永，周以真，王榮良，等.計算思維改變信息技術課程[J].中國信息技術教育，2013（6）：5-12.

[4] 劉焱青.App Inventor2在中學生計算思維培養中的應用研究[D].湖南師范大學，2016.

[5] 屈婉玲，劉田，張立昂，等.算法設計與分析[M].北京：清華大學出版社，2011.

[6] 崔萌.遺傳算法解決多背包問題[J].計算機與網絡，2005（19）：52-54.