貪心算法

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

回到家后，嶺童小子還沉浸在科幻電影中，直到睡覺前，他還在和星空討論電影中的情節(jié)。不知過了多久，嶺童小子進(jìn)入了夢(mèng)鄉(xiāng)——

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

“全體成員請(qǐng)注意！雷達(dá)系統(tǒng)已捕捉到敵國(guó)導(dǎo)彈來襲的信號(hào)。我們的導(dǎo)彈攔截系統(tǒng)發(fā)射的第一發(fā)炮彈能夠達(dá)到任意高度，但是之后的每一發(fā)炮彈都不能高于前一發(fā)炮彈的高度。一套系統(tǒng)可能攔截不了所有的導(dǎo)彈，怎么辦，最少需要準(zhǔn)備多少套攔截系統(tǒng)呢？”

“兵來將擋，水來土掩。不怕，請(qǐng)告訴我飛來了幾枚導(dǎo)彈！”

……

“請(qǐng)依次告訴我導(dǎo)彈飛來的高度?！?/p>

……

導(dǎo)彈攔截系統(tǒng)啟動(dòng)！

“敵國(guó)導(dǎo)彈被成功攔截！太棒了！”

“我要起床，把夢(mèng)里的程序?qū)懗鰜恚屝强涨魄莆业膮柡?。?/p>

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

曉敏老師：

嶺童小子真是一個(gè)“程序迷”，在夢(mèng)境里都在寫程序。

關(guān)于導(dǎo)彈攔截的問題，因?yàn)槲覀儾恢老乱幻秾?dǎo)彈的高度，所以無(wú)法從整體最優(yōu)上來考慮，只能對(duì)當(dāng)前出現(xiàn)的問題給出最優(yōu)解?，F(xiàn)在就讓我們一起來分析一下吧。

已知現(xiàn)在有5枚導(dǎo)彈需要攔截，它們飛來的高度分別是：1200米、980米、1150米、800米、650米。導(dǎo)彈攔截系統(tǒng)發(fā)射的第一發(fā)炮彈能達(dá)到任意高度，但之后的每一發(fā)炮彈都不能高于前一發(fā)炮彈的高度。

第1枚導(dǎo)彈的高度為1200米，啟動(dòng)第一套攔截系統(tǒng)，并將“最低高度”設(shè)置為1200米。

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

第3枚導(dǎo)彈的高度為1150米，大于“最低高度”980米，第一套攔截系統(tǒng)無(wú)法成功攔截，因此啟動(dòng)第二套攔截系統(tǒng)，并將“最低高度”設(shè)置為1150米。

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

第5枚導(dǎo)彈的高度為650米，小于“最低高度”800米，因此繼續(xù)使用第二套攔截系統(tǒng)，并將“最低高度”更新為650米。

所以，在這次的導(dǎo)彈攔截任務(wù)中，只需2套攔截系統(tǒng)即可。

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

如上所述，把一個(gè)復(fù)雜的問題分成若干個(gè)簡(jiǎn)單的子問題，在解決每一個(gè)子問題時(shí)，總是做出當(dāng)前看來是最好的選擇，即局部最優(yōu)解，最后把所有的局部最優(yōu)解合為一個(gè)解，這就是貪心算法的基本思路。

程序作品展示：

掃描下方的小程序碼，看看長(zhǎng)沙市芙蓉區(qū)馬坡嶺小學(xué)學(xué)生的優(yōu)秀作品吧。

曹曉敏 ：湖南省特級(jí)教師、省優(yōu)秀科技輔導(dǎo)員，長(zhǎng)沙市首批卓越教師、市骨干教師。長(zhǎng)沙市芙蓉區(qū)馬坡嶺小學(xué)信息技術(shù)教師。