文档介绍：合肥学院计算机科学与技术系课程设计报告2013~2014学年第二学期课程数据结构与算法课程设计名称拦截导弹问题学生姓名学号专业班级指导教师2014年6月题目:拦截导弹问题【问题描述】某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度。某天,雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹。输入导弹依次飞来的高度(雷达给出的高度数据是不大于30000的正整数),计算这套系统最多能拦截多少导弹,如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。【基本要求】输入格式一行,为导弹依次飞来的高度输出格式两行,分别是最多能拦截的导弹数与要拦截所有导弹最少要配备的系统数样例输入38920715530029917015865样例输出62问题分析和任务定义经过分析会发现,每一个导弹最终的结果都是要被打的,如果它后面有一个比它高的导弹,那打它的这个装置无论如何也不能打那个导弹了,经过这么一分析,这个问题便抽象成在已知序列里找最长上升序列的问题。即此问题一是寻求一组数据的最长非递增子序列的长度;二是找出包含所有数据的所需最少的子序列的树目2、数据结构的选择和概要设计根据分析可知此算法需要运用动态规划,我选择用数组h[21]来存储数据并将程序分成两个部分:inth[21],opt[21],count,i,j,p[21],lis,pos,bul=0,flis,e; count=0; printf("请输入要拦截的导弹数:"); scanf("%d",&e);//e来表示飞来的导弹数 printf("样例输入:\n"); for(i=0;i<e;i++){ scanf("%d",&h[count++]);//h[count]用来存储飞来的导弹的高度 }设X={x1,x2,…,xn}为依次飞来的导弹序列,Y={y1,y2,…,yk}为问题的最优解(即X的最长非递增子序列),s为问题的状态(表示导弹拦截系统当前发送炮弹能够到达的最大高度,初值为s=∞——第一发炮弹能够到达任意的高度)。如果y1=x1,即飞来的第一枚导弹被成功拦截。那么,根据题意“每一发炮弹都不能高于前一发的高度”,问题的状态将由s=∞变成s≤x1(x1为第一枚导弹的高度);在当前状态下,序列Y1={y2,…,yk}也应该是序列X1={x2,…,xn}的最长非递增子序列(大家用反证法很容易证明)。也就是说,在当前状态s≤x1下,问题的最优解Y所包含的子问题(序列X1)的解(序列Y1)也是最优的。这就是拦截导弹问题的最优子结构性质。运用动态规划的思想解决系统最多能拦截多少导弹的问题;假设系统最多能拦截的导弹数为dmax(即问题的最优值),则dmax=max(opt(i))所以,要计算问题的最优值dmax,需要分别计算出opt(1)、opt(2)、……opt(n)的值,然后将它们进行比较,找出其中的最大值。根据上面分析出来的递归方程,我们完全可以设计一个递归函数,采用自顶向下的方法计算opt(i)的值。然后,对i从1到n分别调用这个递归函数,就可以计算出opt(1)、opt(2)、……opt(n)。但这样将会有大量的子问题被重复计算。比如在调用递归函数计算opt(1)的时候,可能需要先计算opt(5)的值;之后在分别调用递归函数计算opt(2)、opt(3)、opt(4)的时候,都有可能需要先计算opt(5)的值。如此一来,在整个问题的求解过程中,opt(5)可能会被重复计算很多次,从而造成了冗余,降低了程序的效率。其实,通过以上分析,我们已经知道:opt(n)=1。如果将n作为阶段对问题进行划分,根据问题的动态规划递归方程,我们可以采用自底向上的方法依次计算出opt(n-1)、opt(n-2)、……opt(1)的值。for(i=e-1;i>=0;i--)//动态规划:从下层考虑问题,推出上层的答案,减少程序的执行次数,提高程序的效率for(j=i+1;j<e;j++) {if(h[i]!=-1&&h[j]!=-1&&h[i]>=h[j]&&opt[j]+1>opt[i]) {opt[i]=opt[j]+1;p[i]=j;} }这样,每个opt(i)的值只计算一次,并在计算的同时把计算结果保存下来,从而避免了有些子问题被重复计算的情况发生,提高了程序的效率。理解,运用递归思想解决要拦截所有导弹最少需要配备多少套这种导弹拦截系统问题3、详细设计和编码、(1)定义头文件#include<>(2)定义数据类型inth[21],opt[21],count,i,j,p[21],lis,pos,bul=0,flis,e//h[21]用来