贪心算法

周末晚上，岭童小子全家出动，去电影院看了一部正在热映的科幻电影。岭童小子坐在爸妈中间，手捧爆米花，看着期待已久的科幻片，心里别提有多开心了。

回到家后，岭童小子还沉浸在科幻电影中，直到睡觉前，他还在和星空讨论电影中的情节。不知过了多久，岭童小子进入了梦乡——

“哇！我成功了！”岭童小子躺在床上手舞足蹈，被自己的叫喊声吵醒了。岭童小子揉了揉眼睛，发现刚才的经历都是一场梦。他躺在床上，看着黑漆漆的房间，翻来覆去怎么也睡不着，脑海里不断浮现出梦里的场景……

“全体成员请注意！雷达系统已捕捉到敌国导弹来袭的信号。我们的导弹拦截系统发射的第一发炮弹能够达到任意高度，但是之后的每一发炮弹都不能高于前一发炮弹的高度。一套系统可能拦截不了所有的导弹，怎么办，最少需要准备多少套拦截系统呢？”

“兵来将挡，水来土掩。不怕，请告诉我飞来了几枚导弹！”

……

“请依次告诉我导弹飞来的高度。”

……

导弹拦截系统启动！

“敌国导弹被成功拦截！太棒了！”

“我要起床，把梦里的程序写出来，让星空瞧瞧我的厉害。”

说做就做，岭童小子翻身起床，开始敲击键盘……

晓敏老师：

岭童小子真是一个“程序迷”，在梦境里都在写程序。

关于导弹拦截的问题，因为我们不知道下一枚导弹的高度，所以无法从整体最优上来考虑，只能对当前出现的问题给出最优解。现在就让我们一起来分析一下吧。

已知现在有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，同学们可以在理解这个算法逻辑的前提下，自己研究具体代码。

如上所述，把一个复杂的问题分成若干个简单的子问题，在解决每一个子问题时，总是做出当前看来是最好的选择，即局部最优解，最后把所有的局部最优解合为一个解，这就是贪心算法的基本思路。

程序作品展示：

扫描下方的小程序码，看看长沙市芙蓉区马坡岭小学学生的优秀作品吧。

曹晓敏 ：湖南省特级教师、省优秀科技辅导员，长沙市首批卓越教师、市骨干教师。长沙市芙蓉区马坡岭小学信息技术教师。