某国为了防御敌国的导弹袭击，开发出一种导弹拦截系统，但是这种导弹拦截系统有一个缺陷：虽然他的第一发炮弹能够到达任意高度，但是以后每一发炮弹都不能高于前一发的高度，某天雷达捕捉到敌国的:8枚导弹来袭，雷达给出的导弹飞来的高度依次为389，207，155，300，299，170，158，65。
要求按照导弹袭击的时间顺序拦截全部导弹，不允许先拦截后面的导弹，再拦截前面的导弹，请你计算一下最少需要多少套拦截系统？
采用贪心策略求解该问题，首先把第1枚导弹的高度存入“拦截系统”列表中，即创建第一套拦截系统。然后把第2枚导弹的高度与“拦截系统”列表中的各个元素比较，如果它小于或等于某个元素，则将该元素的值替换为第2枚导弹的高度，即该元素代表的那套拦截系统能多次拦截高度更低的导弹，不需要增加新的拦截系统。
如果第2枚导弹的高度比“拦截系统”列表中的各个元素值都大，则说明没有能够拦截第2枚导弹的拦截系统，这时就创建一套新的拦截系统，将第2枚导弹的高度插入“拦截系统”列表中。其他各枚导弹按此过程进行处理，最后，“拦截系统”列表中包含的元素个数就是需要创建的拦截系统数量，到此求得该问题的解。
首先创建一个名为“导弹”的列表，并把8枚导弹的高度依次录入此列表中；再创建一个名为“拦截系统”的列表，用于存放各套拦截系统的最后拦截导弹的高度，每个元素代表一套拦截系统，两个列表如图所示
根据上面介绍的算法，编写求解“拦截导弹”问题的程序清单，如图所示，单击绿旗运行程序，得到答案，最少需要2套拦截系统。
假设由于导弹拦截系统造价太高，某国只部署了一套这种系统，那么面对来袭的8枚导弹，该系统最多能拦截多少枚导弹？
网友评论