Algorithm 版 (精华区)

发信人: sino (一层秋雨一层凉), 信区: Algorithm
标  题: 一个题解
发信站: 哈工大紫丁香 (2001年09月20日18:44:29 星期四), 站内信件

发信人: Wednesday (柯南), 信区: Visual
标  题: 编程求解
发信站: 日月光华站 (Sun Dec  5 18:58:50 1999) , 转信
某国为加强国防而研制出一种导弹防御系统,但是这种防御系统有一缺陷:虽然第一发炮
弹
可以击中任意高度,但后面的炮弹却无法再打倒前一次的高度.且由于是试运行阶段,
只有一套系统可用.
现在雷达捕捉到敌方飞来的一批导弹的高度(均小于3000),问单靠一套系统可以最多击落

敌方几发导弹;若打算全部击落需用几套系统.
例:
输入:
n=7  N为导弹总数
300 250 275 252 200 138 245
输出
5  (最多击落5枚导弹)
2  (全部击落需2套系统)
注: 300 250 275 252 200 138 245
    ~~~     ~~~ ~~~ ~~~ ~~~
   加下划线部分为一套系统应击落的
--
※ 修改:·Wednesday 於 Dec  5 19:08:52 修改本文·[FROM:   202.113.28.48]
※ 来源:·日月光华站 bbs.fudan.edu.cn·[FROM: 202.113.28.48]
发信人: ttomcat (Delphi? Delphi!), 信区: Visual
标  题: Re: 编程求解
发信站: 日月光华站 (Sat Dec 11 21:54:18 1999) , 站内信件
这两个问题不一定能同时最优化，即不一定第一套系统打得越多用的系统越少。
如将例子中最后一个数字改为251则最少需用两套系统，但第一套系统应打300 250 200

 138（另一套系统打275 252 251），不能照最多的方案打。
此问题可分为两个问题，即一套系统最多打落几发及全部击落最少要几套系统。
第一问题的解法如下：
我们来考虑每一个数向后连接的最优路径（即最多可连接的数），即数组中的每一个数

都有一个它可连接的数。例如在298,300,250,275,198,200,138中，138的可连接数为1
（它自身），200的为2（它与138），198的为2（它与138）。
倒过来做，即从后往前一个个考虑数组中的数字，每考虑一数，寻后方比之小的数中可

连接的数最多的一个数，它的可连接的数+1赋给本数。则上例中275的可连接数为198的

可连接数+1成为3。以此做下去。
理由如下：为使击落数最多所取的这些数我们称之为最优路径，对一个数来说，如果最

优路径经过它，则必然经过它后方连接的那条最优路径。而每一数字可连接的数莫非是

它后面的且比它小的数中的一个，所以上面决定的路径是最优的。
程序：
#define TOTAL 10
void main()
{
   int source[TOTAL]={298,300,250,252,200,138,245,244,247,241};
   int optimize[TOTAL];//存放每一数可在其后连接的个数（最多）
   int i,j,maxlink,max,t;//max为所求的最大数，maxlink为后方元素中可连接的最
多数
   max=1;
   for (i=TOTAL-1;i>=0;i--)
   {
     maxlink=0;
     for (j=i+1;j<TOTAL;j++)
     {
       if (optimize[j]>maxlink&&source[j]<source[i]) maxlink=optimize[j];
                //寻后方比当前数小的数中可连接的数最多的一个数，
                //它的可连接的数+1赋给本数可连接的数。
                //如果要记下最优解中包含哪些元素，要在此记下j。
     }
        optimize[i]=maxlink+1;
        if (optimize[i]>max) {max=optimize[i];t=i;}
   }//此时已求得max
}
关于计算最少需用系统数的算法，由于时间仓促，我还没想出来，希望大家能一起参与

讨论。
程序虽短，可是我费了不少劲。（我花了1个多小时）希望以后BBS上能多有这样的算法

求解，对提高编程水平非常有好处。非常感谢Wednesday.
【 在 Wednesday (柯南) 的大作中提到: 】
: 某国为加强国防而研制出一种导弹防御系统,但是这种防御系统有一缺陷:虽然第一发
炮弹
: 可以击中任意高度,但后面的炮弹却无法再打倒前一次的高度.且由于是试运行阶段,
: 只有一套系统可用.
: 现在雷达捕捉到敌方飞来的一批导弹的高度(均小于3000),问单靠一套系统可以最多击
落
: 敌方几发导弹;若打算全部击落需用几套系统.
: 例:
: 输入:
: n=7  N为导弹总数
: 300 250 275 252 200 138 245
: 输出
: 5  (最多击落5枚导弹)
: 2  (全部击落需2套系统)
: 注: 300 250 275 252 200 138 245
:     ~~~     ~~~ ~~~ ~~~ ~~~
:    加下划线部分为一套系统应击落的
--
※ 来源:·日月光华站 bbs.fudan.edu.cn·[FROM: 10.51.32.9]
发信人: ttomcat (Delphi? Delphi!), 信区: Visual
标  题: Re: 编程求解
发信站: 日月光华站 (Tue Dec 21 09:42:34 1999) , 站内信件
#define NUM 7
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
void main()
{
   int links[NUM];
   int linknumber;
   int i,j,k,max;
   int source[NUM]={300,250,275,252,200,138,251};
   int sourcenumber=NUM;
   links[0]=source[0];
   linknumber=1;
   for (i=1;i<sourcenumber;i++)
   {
      k=-1;
      max=3001;
      for (j=0;j<linknumber;j++)
         if (links[j]>source[i]&&links[j]<max)
            {
               k=j;
               max=links[j];
            }//寻找比它大的最小的链头。
      if (k==-1) //找不到
      {
         links[linknumber]=source[i];
         linknumber++;
      }
      else //找到
      {  links[k]=source[i];
      }
   }
}
基本思路是从头开始随着一个个元素的加入，可以组成一些从大到小的链
（记录在links数组中，只记录最后一个，即最小一个元素），每一加入的
元素可以自成一链头或加入其他链（链尾数字比它大）。
当所有链尾都比它小时，它自成一链头。否则寻找比它大的最小的一个链
尾连接。
linknumber记录链数.
【 在 ttomcat (Delphi? Delphi!) 的大作中提到: 】
: 这两个问题不一定能同时最优化，即不一定第一套系统打得越多用的系统越少。
: 如将例子中最后一个数字改为251则最少需用两套系统，但第一套系统应打300 250 2
00
:  138（另一套系统打275 252 251），不能照最多的方案打。
: 此问题可分为两个问题，即一套系统最多打落几发及全部击落最少要几套系统。
                                                    ~~~~~~~~~~~~~~~~~~
: 第一问题的解法如下：
: 我们来考虑每一个数向后连接的最优路径（即最多可连接的数），即数组中的每一个
数
: 都有一个它可连接的数。例如在298,300,250,275,198,200,138中，138的可连接数为
1
: （它自身），200的为2（它与138），198的为2（它与138）。
: 倒过来做，即从后往前一个个考虑数组中的数字，每考虑一数，寻后方比之小的数中
可
: 连接的数最多的一个数，它的可连接的数+1赋给本数。则上例中275的可连接数为198
的
: 可连接数+1成为3。以此做下去。
: 理由如下：为使击落数最多所取的这些数我们称之为最优路径，对一个数来说，如果
最
: 优路径经过它，则必然经过它后方连接的那条最优路径。而每一数字可连接的数莫非
是
: 它后面的且比它小的数中的一个，所以上面决定的路径是最优的。
: 程序：
: #define TOTAL 10
: void main()
: {
:    int source[TOTAL]={298,300,250,252,200,138,245,244,247,241};
:    int optimize[TOTAL];//存放每一数可在其后连接的个数（最多）
:    int i,j,maxlink,max,t;//max为所求的最大数，maxlink为后方元素中可连接的最

: 多数
:    max=1;
:    for (i=TOTAL-1;i>=0;i--)
:    {
:      maxlink=0;
:      for (j=i+1;j<TOTAL;j++)
:      {
:        if (optimize[j]>maxlink&&source[j]<source[i]) maxlink=optimize[j];
:                 //寻后方比当前数小的数中可连接的数最多的一个数，
:                 //它的可连接的数+1赋给本数可连接的数。
:                 //如果要记下最优解中包含哪些元素，要在此记下j。
:      }
:         optimize[i]=maxlink+1;
:         if (optimize[i]>max) {max=optimize[i];t=i;}
:    }//此时已求得max
: }
:
--

--
撷取生活中每一朵清新的浪花,智慧的浪花 ..汇成音乐的海洋.

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: mtlab4.hit.edu.cn]