使用Scratch进行战略部署——导弹拦截系统

2020-04-10  本文已影响0人  酷叮猫少儿编程

  某国为了防御敌国的导弹袭击,开发出一种导弹拦截系统,但是这种导弹拦截系统有一个缺陷:虽然他的第一发炮弹能够到达任意高度,但是以后每一发炮弹都不能高于前一发的高度,某天雷达捕捉到敌国的:8枚导弹来袭,雷达给出的导弹飞来的高度依次为389,207,155,300,299,170,158,65。

  要求按照导弹袭击的时间顺序拦截全部导弹,不允许先拦截后面的导弹,再拦截前面的导弹,请你计算一下最少需要多少套拦截系统?

  采用贪心策略求解该问题,首先把第1枚导弹的高度存入“拦截系统”列表中,即创建第一套拦截系统。然后把第2枚导弹的高度与“拦截系统”列表中的各个元素比较,如果它小于或等于某个元素,则将该元素的值替换为第2枚导弹的高度,即该元素代表的那套拦截系统能多次拦截高度更低的导弹,不需要增加新的拦截系统。

  如果第2枚导弹的高度比“拦截系统”列表中的各个元素值都大,则说明没有能够拦截第2枚导弹的拦截系统,这时就创建一套新的拦截系统,将第2枚导弹的高度插入“拦截系统”列表中。其他各枚导弹按此过程进行处理,最后,“拦截系统”列表中包含的元素个数就是需要创建的拦截系统数量,到此求得该问题的解。

  首先创建一个名为“导弹”的列表,并把8枚导弹的高度依次录入此列表中;再创建一个名为“拦截系统”的列表,用于存放各套拦截系统的最后拦截导弹的高度,每个元素代表一套拦截系统,两个列表如图所示

  根据上面介绍的算法,编写求解“拦截导弹”问题的程序清单,如图所示,单击绿旗运行程序,得到答案,最少需要2套拦截系统。

  假设由于导弹拦截系统造价太高,某国只部署了一套这种系统,那么面对来袭的8枚导弹,该系统最多能拦截多少枚导弹?

上一篇 下一篇

猜你喜欢

热点阅读