貪心算法

周末晚上，嶺童小子全家出動，去電影院看了一部正在熱映的科幻電影。嶺童小子坐在爸媽中間，手捧爆米花，看著期待已久的科幻片，心里別提有多開心了。

回到家后，嶺童小子還沉浸在科幻電影中，直到睡覺前，他還在和星空討論電影中的情節。不知過了多久，嶺童小子進入了夢鄉——

“哇！我成功了！”嶺童小子躺在床上手舞足蹈，被自己的叫喊聲吵醒了。嶺童小子揉了揉眼睛，發現剛才的經歷都是一場夢。他躺在床上，看著黑漆漆的房間，翻來覆去怎么也睡不著，腦海里不斷浮現出夢里的場景……

“全體成員請注意！雷達系統已捕捉到敵國導彈來襲的信號。我們的導彈攔截系統發射的第一發炮彈能夠達到任意高度，但是之后的每一發炮彈都不能高于前一發炮彈的高度。一套系統可能攔截不了所有的導彈，怎么辦，最少需要準備多少套攔截系統呢？”

“兵來將擋，水來土掩。不怕，請告訴我飛來了幾枚導彈！”

……

“請依次告訴我導彈飛來的高度。”

……

導彈攔截系統啟動！

“敵國導彈被成功攔截！太棒了！”

“我要起床，把夢里的程序寫出來，讓星空瞧瞧我的厲害。”

說做就做，嶺童小子翻身起床，開始敲擊鍵盤……

曉敏老師：

嶺童小子真是一個“程序迷”，在夢境里都在寫程序。

關于導彈攔截的問題，因為我們不知道下一枚導彈的高度，所以無法從整體最優上來考慮，只能對當前出現的問題給出最優解。現在就讓我們一起來分析一下吧。

已知現在有5枚導彈需要攔截，它們飛來的高度分別是：1200米、980米、1150米、800米、650米。導彈攔截系統發射的第一發炮彈能達到任意高度，但之后的每一發炮彈都不能高于前一發炮彈的高度。

第1枚導彈的高度為1200米，啟動第一套攔截系統，并將“最低高度”設置為1200米。

第2枚導彈的高度為980米，小于“最低高度”1200米，因此可以使用第一套攔截系統，并將“最低高度”更新為980米。

第3枚導彈的高度為1150米，大于“最低高度”980米，第一套攔截系統無法成功攔截，因此啟動第二套攔截系統，并將“最低高度”設置為1150米。

第4枚導彈的高度為800米，小于“最低高度”1150米，因此可以使用第二套攔截系統，并將“最低高度”更新為800米。

第5枚導彈的高度為650米，小于“最低高度”800米，因此繼續使用第二套攔截系統，并將“最低高度”更新為650米。

所以，在這次的導彈攔截任務中，只需2套攔截系統即可。

有了這個思路，編程就非常容易了。這里提供關鍵代碼段，如圖1、圖2，同學們可以在理解這個算法邏輯的前提下，自己研究具體代碼。

如上所述，把一個復雜的問題分成若干個簡單的子問題，在解決每一個子問題時，總是做出當前看來是最好的選擇，即局部最優解，最后把所有的局部最優解合為一個解，這就是貪心算法的基本思路。

程序作品展示：

掃描下方的小程序碼，看看長沙市芙蓉區馬坡嶺小學學生的優秀作品吧。

曹曉敏 ：湖南省特級教師、省優秀科技輔導員，長沙市首批卓越教師、市骨干教師。長沙市芙蓉區馬坡嶺小學信息技術教師。