梁雪梅

摘? 要：中學(xué)是培養(yǎng)良好思維的關(guān)鍵時(shí)期，但是中學(xué)以基礎(chǔ)知識(shí)教育為主，忽略了學(xué)生的思維能力的培養(yǎng)，使得學(xué)生缺乏科學(xué)素養(yǎng)、工程素養(yǎng)和計(jì)算素養(yǎng)。而信息奧賽剛好彌補(bǔ)了這一短板，通過(guò)信息奧賽教學(xué)，尤其是算法教學(xué)來(lái)培養(yǎng)學(xué)生分析問(wèn)題和解決問(wèn)題的能力。因此，該文研究信息學(xué)奧林匹克競(jìng)賽對(duì)中學(xué)生計(jì)算思維的培養(yǎng)，并以貪心算法教學(xué)為例，通過(guò)兩個(gè)具體問(wèn)題，引導(dǎo)學(xué)生分析問(wèn)題、建立模型并評(píng)價(jià)算法。以此找出算法的規(guī)律和設(shè)計(jì)算法的步驟，培養(yǎng)學(xué)生分析問(wèn)題和解決問(wèn)題的能力，培養(yǎng)學(xué)生的計(jì)算素養(yǎng)。

關(guān)鍵詞：信息奧賽? 計(jì)算思維? 貪心算法? 建模

中圖分類號(hào)：G642;R-4 ? ?文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1672-3791（2019）09（c）-0118-02

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

中小學(xué)階段是培養(yǎng)學(xué)生良好思維的最佳時(shí)期，特別是計(jì)算思維的培養(yǎng)，但是我國(guó)中小學(xué)階段的教育以基礎(chǔ)知識(shí)教育為主，缺乏對(duì)計(jì)算思維的培養(yǎng)，使得學(xué)生對(duì)問(wèn)題的思考缺乏科學(xué)素養(yǎng)、工程素養(yǎng)和計(jì)算素養(yǎng)，從而導(dǎo)致學(xué)生在思考實(shí)際問(wèn)題的解決方法時(shí)不嚴(yán)謹(jǐn)、不科學(xué)[3]。

信息學(xué)奧林匹克競(jìng)賽即NOI競(jìng)賽（National Olympiad in Informatics），是全國(guó)中學(xué)五大競(jìng)賽之一。既然基礎(chǔ)知識(shí)教育缺乏計(jì)算思維的培養(yǎng)，那信息奧賽是如何提高學(xué)生的計(jì)算思維呢？

該文通過(guò)設(shè)計(jì)、實(shí)現(xiàn)和評(píng)價(jià)實(shí)際問(wèn)題的算法來(lái)闡明信息學(xué)奧林匹克競(jìng)賽對(duì)中學(xué)生計(jì)算思維的培養(yǎng)過(guò)程。同時(shí)還培養(yǎng)了學(xué)生分析問(wèn)題、解決問(wèn)題的能力，并通過(guò)不斷地解決問(wèn)題、開拓創(chuàng)新，提高學(xué)生的創(chuàng)新能力[4]。

1? 基于信息奧賽的計(jì)算思維培養(yǎng)——以貪心算法教學(xué)為例

在信息奧賽中包含大量算法方面的考核，尤其是算法在實(shí)際問(wèn)題中的應(yīng)用。因此，在信息奧賽教學(xué)中更加側(cè)重算法教學(xué)，主要教學(xué)過(guò)程分為問(wèn)題描述、問(wèn)題分析與建模、算法評(píng)價(jià)與優(yōu)化等[5]。通過(guò)該過(guò)程不斷提高學(xué)生素質(zhì)和分析問(wèn)題、解決問(wèn)題的能力，培養(yǎng)學(xué)生的計(jì)算思維。該文以貪心算法為例，探究信息奧賽對(duì)中學(xué)生計(jì)算思維的培養(yǎng)。

1.1 問(wèn)題描述

有n位同學(xué)參加學(xué)校文藝匯演，每位同學(xué)的表演時(shí)間已知。從0時(shí)刻開始陸續(xù)安排每位同學(xué)上場(chǎng)表演，每個(gè)表演的完成時(shí)間是從0時(shí)刻到個(gè)人表演結(jié)束的時(shí)間。請(qǐng)求出所有表演的總完成時(shí)間（所有表演完成時(shí)間之和）最短的上場(chǎng)順序。

例如：5位同學(xué)，表演時(shí)間分別為2min、6min、4min、9min、13min。

1.2 問(wèn)題分析與建模

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

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

【問(wèn)題分析】將表演時(shí)間按從小到大排序：2、4、6、9、13。則第一位同學(xué)的完成時(shí)間為2min，第二位同學(xué)的完成時(shí)間為（2+4）min，第三位同學(xué)的完成時(shí)間為（2+4+6）min，第四位同學(xué)的完成時(shí)間為（2+4+6+9）min，第五位同學(xué)的完成時(shí)間為（2+4+6+9+13）min?？偟耐瓿蓵r(shí)間計(jì)算如下：

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

通過(guò)分析得出，則最短的總完成時(shí)間為75min。表演時(shí)間短的先上場(chǎng)，根據(jù)表演時(shí)間按從小到大排序，然后依次上場(chǎng)。因此，抽象出其目標(biāo)函數(shù)和解。

【目標(biāo)函數(shù)】I的總完成時(shí)間，。

需要注意的是，在一些更為復(fù)雜的問(wèn)題求解中，目標(biāo)函數(shù)還有一定的約束條件。

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

1.3 算法評(píng)價(jià)與優(yōu)化

對(duì)于所有文藝匯演上場(chǎng)順序的實(shí)例，使用該算法都能得到最優(yōu)解嗎？我們用數(shù)學(xué)思維來(lái)驗(yàn)證該算法的正確性。

證：假設(shè)上場(chǎng)順序m第i，j項(xiàng)上場(chǎng)順序相鄰且有逆序，即ti>tj，交換任務(wù)i和j得到上場(chǎng)順序n，其他次序不變，如圖1所示。

根據(jù)目標(biāo)函數(shù)可知T（n）-T（m）=ti-tj﹤0。所以該算法得到的結(jié)果為最優(yōu)解。

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

那么，所有問(wèn)題都能通過(guò)貪心算法來(lái)解決并獲得最優(yōu)解嗎？我們?cè)賮?lái)探討另一個(gè)問(wèn)題。

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

如何選擇禮物，使得不超過(guò)背包承重范圍且禮物價(jià)值達(dá)到最大呢？

依舊使用貪心法來(lái)解決這個(gè)問(wèn)題，貪心策略是先裝單位重量?jī)r(jià)值大的禮物，總重量不超過(guò)6kg。因此，各類禮物按照排序?yàn)?。按照貪心策略選擇了禮物1之后，再禮物2或禮物3均會(huì)超出6kg，所以最終的選擇結(jié)果為禮物1和禮物4，最終的價(jià)值為9。但是，很明顯，選擇禮物2和禮物4的總重量為6kg且價(jià)值為11，顯然比價(jià)值9更好。

通過(guò)這個(gè)例子我們可以知道，通過(guò)貪心算法得到的解不一定是正解。這就涉及到算法設(shè)計(jì)的問(wèn)題。那么，設(shè)計(jì)算法的步驟為：（1）問(wèn)題建模;（2）算法選擇與描述;（3）證明該方法是否對(duì)所有實(shí)例都能得到最優(yōu)解;（4）如果得不到最優(yōu)解，請(qǐng)給出反例證明。

根據(jù)文藝匯演案例，引導(dǎo)學(xué)生分析問(wèn)題并建立模型，找到貪心算法的規(guī)律。然后分析具體的貪心算法，讓學(xué)生明白使用貪心算法解決問(wèn)題的基本步驟。然后，根據(jù)新年禮物選擇案例，讓學(xué)生明白貪心算法得到的解不一定是最優(yōu)解，引導(dǎo)學(xué)生明白設(shè)計(jì)算法的步驟。使用具體的問(wèn)題引入，引導(dǎo)學(xué)生學(xué)會(huì)分析問(wèn)題和解決問(wèn)題，培養(yǎng)學(xué)生的計(jì)算思維。

2? 結(jié)語(yǔ)

該文根據(jù)計(jì)算思維的概念和信息奧賽培養(yǎng)目標(biāo)，探究信息學(xué)奧林匹克競(jìng)賽對(duì)中學(xué)生計(jì)算思維的培養(yǎng)。通過(guò)分析中學(xué)生基礎(chǔ)知識(shí)教育，發(fā)現(xiàn)中學(xué)基礎(chǔ)教育缺乏計(jì)算思維的培養(yǎng)。因此，以貪心算法教學(xué)為例，根據(jù)文藝匯演問(wèn)題，引導(dǎo)學(xué)生分析問(wèn)題、一步步解決問(wèn)題，得到貪心算法的規(guī)律和使用貪心算法解決問(wèn)題的步驟，然后根據(jù)新年禮物選擇問(wèn)題，引導(dǎo)學(xué)生發(fā)現(xiàn)貪心法得到的解不一定是最優(yōu)解，引出設(shè)計(jì)算法的步驟。通過(guò)分析和解決具體問(wèn)題，培養(yǎng)學(xué)生分析問(wèn)題和解決問(wèn)題的能力，提高學(xué)生的數(shù)學(xué)思維、工程思維和計(jì)算思維。

參考文獻(xiàn)

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

[2] 周以真.計(jì)算思維[A].中國(guó)科學(xué)技術(shù)協(xié)會(huì)學(xué)會(huì)學(xué)術(shù)部.新觀點(diǎn)新學(xué)說(shuō)學(xué)術(shù)沙龍文集7：教育創(chuàng)新與創(chuàng)新人才培養(yǎng)[C].中國(guó)科學(xué)技術(shù)協(xié)會(huì)學(xué)會(huì)學(xué)術(shù)部：中國(guó)科學(xué)技術(shù)協(xié)會(huì)學(xué)會(huì)學(xué)術(shù)部，2007：6.

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

[4] 劉焱青.App Inventor2在中學(xué)生計(jì)算思維培養(yǎng)中的應(yīng)用研究[D].湖南師范大學(xué)，2016.

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

[6] 崔萌.遺傳算法解決多背包問(wèn)題[J].計(jì)算機(jī)與網(wǎng)絡(luò)，2005（19）：52-54.