测试数据：
XXXXXXXXXXXXXXXXXXXX .....XXXX......X.XXX X.........X.XX.....X
X.XXX.XX..X.XX.XXX.X X.........X.XX.....X
X.XXX.XX..X.XX.XXX.X .X.....XX.X.....X..X X....X..X...X.X....X
...XXXX.X.XXX...XXXX ...........X.......X
XXXXXX....XXXXXX..XX ...........X.......X .X.....XX.X.....X..X
XXXXXX....XXXXXXXX.X X....X..X...X.X....X
...XXXX.X.XXX...XXXX ...........X.......X
XXX.X.XXXXX.XXXX.X.X ....X.XX....XXX..... XXXX.....XX......... 1 1 1 1 4 8 1 5. 皇宫小偷
有一个小偷要到皇宫里偷取宝物，经过仔细的侦察，他发现皇宫实际上是一个20×20的迷宫，并且有一名卫兵巡逻，卫兵巡逻的路线是固定的，每单位时间移动一格，每4个单位时间循环一次。小偷每单位时间移动一格或在原地不动。任何时刻，小偷和卫兵在同一格，或卫兵能看到小偷，小偷将会被卫兵杀死。现在小偷已经得到了皇宫的地图，卫兵巡逻的起点，卫兵连续四次移动的方向和宝物的位置，请你设计一个程序判断小偷能否偷得宝物。
提示：参考第3题、第4题 6. 分酒问题
有一酒瓶装有8斤酒，没有量器，只有分别装5斤和3斤的空酒瓶。设计一程序将8斤酒分成两个4斤，并以最少的步骤给出答案。 7. *找倍数
对于每个输入的数字（如：2），则要求 给出一个由1，0构成的十进制整数，且该整数为输入数字的某个倍数（如2对应的10，6的倍数100100100100100100）。 8. *8数码难题
由左图变到右图最少需要几步，并演示移动过程。
2 5 1 8 6 7 4 3 1 4 7 2 5 8
3 6 实验四：动态规划
实验目的：理解动态规划的基本思想，理解动态规划算法的两个基本要素最优子结构性质和
子问题的重叠性质。熟练掌握典型的动态规划问题。掌握动态规划思想分析问题的一般方法，对较简单的问题能正确分析，设计出动态规划算法，并能快速编程实现。
实验内容：编程实现讲过的例题：最长公共子序列问题、矩阵连乘问题、凸多边形最优三角
剖分问题、电路布线问题等。本实验中的问题，设计出算法并编程实现。
习题
1． 最长公共子序列
一个给定序列的子序列是在该序列中删去若干元素后得到的序列。确切地说，若给定序列X=
解答如下：
a) 最长公共子序列的结构
若用穷举搜索法，耗时太长，算法需要指数时间。 易证最长公共子序列问题也有最优子结构性质
设序列X=
其中Xm-1=
由最长公共子序列问题的最优子结构性质可知，要找出X=
由此递归结构容易看到最长公共子序列问题具有子问题重叠性质。例如，在计算X和Y的最长公共子序列时，可能要计算出X和Yn-1及Xm-1和Y的最长公共子序列。而这两个子问题都包含一个公共子问题，即计算Xm-1和Yn-1的最长公共子序列。
我们来建立子问题的最优值的递归关系。用c[i,j]记录序列Xi和Yj的最长公共子序列的长度。其中Xi=
?0当i?0或j＝0时?c[i,j]??c[i?1,j?1]?1当i,j?0且xi?yj时?max?c[i,j?1],c[i?1,j]?当i,j?0且x?y时ij?
c) 计算最优值
由于在所考虑的子问题空间中，总共只有θ(m*n)个不同的子问题，因此，用动态规划算法自底向上地计算最优值能提高算法的效率。
计算最长公共子序列长度的动态规划算法LCS_LENGTH(X,Y)以序列X=
程序如下：
#include
int lcs_length(char x[], char y[]); int main() { char x[100],y[100]; int len; while(1) { scanf(\ if(x[0]=='0') //约定第一个字符串以‘0’开始表示结束 break; len=lcs_length(x,y); printf(\ } }
int lcs_length(char x[], char y[] ) { int m,n,i,j,l[100][100]; m=strlen(x); n=strlen(y); for(i=0;i
由于每个数组单元的计算耗费Ο(1)时间，算法lcs_length耗时Ο(mn)。 思考：空间能节约吗？ 2． 计算矩阵连乘积
在科学计算中经常要计算矩阵的乘积。矩阵A和B可乘的条件是矩阵A的列数等于矩阵B的行数。若A是一个p×q的矩阵，B是一个q×r的矩阵，则其乘积C=AB是一个p×r的矩阵。由该公式知计算C=AB总共需要pqr次的数乘。其标准计算公式为：
现在的问题是，给定n个矩阵{A1,A2,…,An}。其中Ai与Ai+1是可乘的，i=1,2,…,n-1。要求计算出这n个矩阵的连乘积A1A2…An。
0i?j??递归公式：m[i][j]??{m[i][k]?m[k?1][j]?pi?1pkpj}i?j min??i?k?j程序如下：
#include 3． 凸多边形的最优三角剖分 多边形是平面上一条分段线性的闭曲线。也就是说，多边形是由一系列首尾相接的直线段组成的。组成多边形的各直线段称为该多边形的边。多边形相接两条边的连接点称为多边形的顶点。若多边形的边之间除了连接顶点外没有别的公共点，则称该多边形为简单多边形。一个简单多边形将平面分为3个部分：被包围在多边形内的所有点构成了多边形的内部；多边形本身构成多边形的边界；而平面上其余的点构成了多边形的外部。当一个简单多边形及其内部构成一个闭凸集时，称该简单多边形为凸多边形。也就是说凸多边形边界上或内部的任意两点所连成的直线段上所有的点均在该凸多边形的内部或边界上。 通常，用多边形顶点的逆时针序列来表示一个凸多边形，即P= 若vi与vj是多边形上不相邻的两个顶点，则线段vivj称为多边形的一条弦。弦 将多边形分割成凸的两个子多边形 凸多边形最优三角剖分的问题是：给定一个凸多边形P= 可以定义三角形上各种各样的权函数W。例如：定义ω(△vivjvk)=|vivj|+|vivk|+|vkvj|，其中，|vivj|是点vi到vj的欧氏距离。相应于此权函数的最优三角剖分即为最小弦长三角剖分。(注意：解决此问题的算法必须适用于任意的权函数) 4． 防卫导弹 一种新型的防卫导弹可截击多个攻击导弹。它可以向前飞行，也可以用很快的速度向下飞行，可以毫无损伤地截击进攻导弹，但不可以向后或向上飞行。但有一个缺点，尽管它发射时可以达到任意高度，但它只能截击比它上次截击导弹时所处高度低或者高度相同的导弹。现对这种新型防卫导弹进行测试，在每一次测试中，发射一系列的测试导弹（这些导弹发射的间隔时间固定，飞行速度相同），该防卫导弹所能获得的信息包括各进攻导弹的高度，以及它们发射次序。现要求编一程序，求在每次测试中，该防卫导弹最多能截击的进攻导弹数量，一个导弹能被截击应满足下列两个条件之一： a)它是该次测试中第一个被防卫导弹截击的导弹； b)它是在上一次被截击导弹的发射后发射，且高度不大于上一次被截击导弹的高度的导弹。 输入数据：第一行是一个整数n，以后的n各有一个整数表示导弹的高度。 输出数据：截击导弹的最大数目。 分析：定义l[i]为选择截击第i个导弹，从这个导弹开始最多能截击的导弹数目。 由于选择了第i枚导弹，所以下一个要截击的导弹j的高度要小于等于它的高度，所以l[i]应该等于从i＋1到n的每一个j，满足h[j]<=h[i]的j中l[j]的最大值。