end.
二、动态规划方法实现的灵活性与技巧性
这里需要说明的是，上述程序流程仅是提供了解题的一种思路或方法，并不是说所有解题的程序流程都应如此。例如：
● 若每一个阶段仅一个出发位置，则可通过一重循环枚举各个阶段的状态；
● 若状态非一个整数值所能描述(例如代表平面或空间上的一个坐标)，则枚举状态的第二重循环可由相应的多重循环替代；
● 如果可供选择的决策较少或者较难定义决策序号，则取消枚举决策的第三重循环，将决策过程直接放入状态转移方程或者在循环体内编写决策选择程序；
我们必须从问题本身和解题需求出发，具体问题具体分析，制定行之有效的策略。特别是作为信息学竞赛中的动态规划问题，考察的知识面是多方面的，应用的技巧也是多变的。
例 3-1-2 ：拦截导弹。某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭，由于该系统还在试用阶段。所以只有一套系统，因此有可能不能拦截所有的导弹。
输入导弹依次飞来的高度(雷达给出的高度不大于30000的正整数)。计算这套系统最多能拦截多少导弹。
输入：导弹数N和N颗依次飞来的导弹高度，（导弹个数<=1000）。 输出：一套系统最多拦截的导弹数，并依次打印输出被拦截导弹的高度。
在本题中不仅要求输出最优解，而且还要求输出最优解的形成过程。为此，我们设置了一张记忆表C[i]，在按从后往前方式求解的过程中，将每一个子问题的最佳决策保存起来，避免在输出方案时重复计算。 阶段i：由右而左计算导弹n‥导弹1中可拦截的最多导弹数（1≤i≤n）； 状态B[i]：由于每个阶段中仅一个状态，因此可通过一重循环
for i := n-1 downto 1 do 枚举每个阶段的状态B[i]；
决策k：在拦截导弹i之后应拦截哪一枚导弹可使得B[i]最大（i+1≤k≤n），
e.g.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 I 13
7 9 16 38 24 37 18 44 19 21 22 63 15 A[I] {高度}
2 1 1 2 4 3 3 2 3 2 2 2 2 1 B[I] {可拦截数} 2 0 0 14 6 8 8 14 10 14 14 14 14 0 C[I] {再拦截} var
a,b,c : array[1..1000] of word; n,i,j,k,max : word; begin
writeln('INPUT : '); {初始化，读入数据} n := 0;
while not eoln do begin {eoln ：end of line} inc(n); read(a[n]); b[n] := 1; c[n] := 0; end; readln;
for i := n-1 downto 1 do begin {枚举每一个阶段的状态，设导弹i被拦截} max := 0; j := 0;
26
for k := i+1 to n do {枚举决策，计算最佳方案中拦截的下一枚导弹} if (a[k] <= a[i]) and (b[k] > max) then begin max := b[k]; j := k; end;
b[i] := max+1; c[i] := j; {若导弹i之后拦截导弹j为最佳方案，则记下} end; max := 0;
for i := 1 to n do {枚举求出一套系统能拦截的最多导数} if b[i] > max then begin max := b[i]; j := i; end; writeln('OUTPUT'); {打印输出结果} writeln('Max = ',b[j]); while j > 0 do begin write(a[j]:5); j := c[j]; end; readln; end.
上面的两道例题都是倒推的，决策的选择也较多。下面我们来讲一题是正推的，而且决策的选择较少。 例 3-1-3 ：数塔问题。设有一个三角形的数塔，如下图所示。顶点结点称为根结点，每个结点有一个整数数值，其值不超过100。从顶点出发，可以向左走，也可以向右走。
从根13出发，向左走到达11，再向右走到达7，再向左走到达14，再向左到达7。由于7是最底层，无路可走。此时，我们找到一条从根结点开始到达底层的路径：13-11-7-14-7。路径上结点中数字的和，称为路径的值，如上面路径的值为13+11+7+14+7 = 52。
当三角形数塔给出之后，找出一条路径，使路径上的值为最大，打印输出最大路径的值。数塔的层数N最多可为100。
算法分析：
此题贪心法往往得不到最优解，例如13-11-12-14-13其路径的值为63，但这不是最优解。 穷举搜索往往是不可能的，当层数N = 100时，路径条数P = 299这是一个非常大的数，即使用世界上最快的电子计算机，也不能在短时间内计算出来。
对这道题唯一正确的方法是动态规划。如果得到一条由顶到底的某处的一条最佳路径，那么对于该路径上的每一个中间点来说，由顶至该中间点的路径所经过的数字和也为最大。因此本题是一个典型的多阶段决策最优化问题。在本题中仅要求输出最优解，为此我们设置了数组A[i,j]保存三角形数塔，B[i,j]保存状态值，按从上往下方式进行求解。
27
阶段i：以层数来划分阶段，由从上往下方式计算层数1‥层数N（1≤i≤n）；因此可通过第一重循
环
for i := 1 to n do begin 枚举每一阶段；
状态B[i,j]：由于每个阶段中有多个状态，因此可通过第二重循环
for j := 1 to i do begin 求出每个阶段的每个状态的最优解B[i,j]；
决策：每个状态最多由上一层的两个结点连接过来，因此不需要做循环。
var
a,b : array[1..100,0..100] of word; i,j,n : byte; max : word; begin repeat
write('N = '); readln(n); until n in [1..100]; fillchar(a,sizeof(a),0); b := a;
for i := 1 to n do begin
for j := 1 to i do read(a[i,j]); readln; end;
b[1,1] := a[1,1]; for i := 2 to n do for j := 1 to i do
if b[i-1,j-1] > b[i-1,j]
then b[i,j] := b[i-1,j-1]+a[i,j] else b[i,j] := b[i-1,j]+a[i,j]; max := 0;
for i := 1 to n do
if b[n,i] > max then max := b[n,i]; writeln('Max = ',max); readln; end.
对抗赛(COMPETE)
提交文件名：COMPETE.PAS 问题描述：
程序设计对抗赛设有N（0 编程要求：对给定N及N个奖品的价值，求出将这N个奖品分成价值相等的两组，共有多少种分法？ 例如：N = 5，S1，S2，S3??Sn分别为1，3，5，8，9 则可分为{1，3，9}与{5，8} 仅有1种分法； 28 例如：N = 7，S1，S2，S3??Sn分别为1，2，3，4，5，6，7 则可分为： {1,6,7}与{2,3,4,5} {2,5,7}与{1,3,4,6} {3,4,7}与{1,2,5,6} {1,2,4,7}与{3,5,6} 有4种分法。 输入文件（COMPETE.IN）： 输入文件中包含若干组数据，每组数据占一行，分别为N及S1，S2，S3??Sn。（每两个相邻的数据之间有一个空格隔开），最后一行为：0 (表示输入结束)。 输出文件（COMPETE.OUT）： 输出文件中包含若干行，每行一个整数，分别表示每组数据的答案，对于某组数据若无解，则输出0。 输入输出样例： COMPETE.IN 7 1 0 COMPETE.OUT 4 多边形的面积（AREA OF POLYGON） 提交文件名：AREA.PAS 问题描述： 现在我们定义一个简单的多边形，它是由终点相连的线段逐次连接环绕而成的，这样就可以保证没有线段相交。而平面多边形是所有的顶点都在一个平面上的多边形。 在这个问题中，你需要计算一个产生于三维空间的简单的平面多边形的面积，也就是说，虽然这个多边形的各顶点是在同一个平面上，但各顶点的坐标都是三维的。 输入文件（AREA.IN）： 每一行输入一个顶点的三维坐标（X，Y，Z），三个坐标之间用空格隔开，输入的数应为双精度浮点数，可正可负。最后一行输入的点应与第一行相同，表示首尾相边。多边形的顶点不能超过1024个。 输出文件（AREA.OUT）： 输出一个数，即多边形的面积，精确到小数点后三位。 输入输出样例： AREA.IN -1.401117996399998E+00 1.509291958378880E-01 1018695898555237E-01 1.918738650437130E-01 1.067473029433127E+00 9.07571353090345E-01 1.401117996399998E+00 –1.509291958378880E-01 –1.18695898588237E-01 -1.918738650437130E-01 -1.067473029433127E+00 -9.07571353090345E-01 -1.401117996399998E+00 1.509291958378880E-01 1018695898555237E-01 AREA.OUT 4.000 多项式乘法（MULTINOMIAL） 2 3 4 5 6 7 29 提交文件名：MULTI.PAS 问题描述： 请编程序把含有乘法运算的代数多项式表达式改写成不含乘法的代数多项式。为简化计算，特做以下约定： (1) 代数多项式表达式中只涉及一个代数符号 a ； (2) 含有乘法运算的代数多项式表达式都是两个不含乘法运算的代数多项式直接相乘的形式，而且这两个 参加乘法的代数多项式都用圆括号括起来了。乘法用符号表示，不得省略。 (3) 常数项以外的各项都是 xa^y 的形式，其中 x 为该项的系数，而 y 是该项的指数。x为 1 时，不得 简写成 a^y ，应写成 1a^y 。而y 为１时，不得简写成xa，应写成 xa^1 。 输入文件（MULTI.IN）： 文件中每行存放一个含有乘法的代数多项式表达式。 输出文件（MULTI.OUT）： 每行输出一个问题的解。要求指数大的项不能出现在指数小的项之后，指数相同的项必须合并同类项。不允许出现不必要的空白字符。 输入输出样例： MULTI.IN (5a^2+3a^1+2)*(4a^1+1) (5a^1+1)*(5a^1+1) MULTI.OUT 20a^3+17a^2+11a^1+2 25a^2+10a^1+1 反射（ECHO） 提交文件名：ECHO.PAS 问题描述： 下面是一个圆柱的截面图，当一束光线射向该柱时，该光线会以和入射角相同的反射角反射出去。 而下图是一束光线在若干各柱子之间连续反射的情况： 30 百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库题库(文件较多)(6)在线全文阅读。
相关推荐：