动态规划算法 章 试验报告.docVIP

实验报告 实验目的：理解动态规划的基本思想，理解动态规划算法的两个基本要素最优子结构性质和子问题的重叠性质。熟练掌握典型的动态规划问题。掌握动态规划思想分析问题的一般方法，对较简单的问题能正确分析，设计出动态规划算法，并能快速编程实现。 实验内容：编程实现讲过的例题：最长公共子序列问题、矩阵连乘问题、凸多边形最优三角剖分问题、电路布线问题等。本实验中的问题，设计出算法并编程实现。 实验过程： 1. 最长公共子序列问题 1.1问题描述 若给定序列X=x1, x2,…, xm，则另一序列Z=z1, z2,…, zk是X的子序列是指存在一个严格递增的下标序列 i1, i2,…, ik，使得对于所有j=1,2,…,k有 即求它们的公共子序列。 1.2算法分析 设序列X=x1, x2, …, xm和Y=y1, y2, …, yn的一个最长公共子序列Z=z1, z2, …, zk，则： 若xm=yn，则zk=xm=yn且Zk-1是Xm-1和Yn-1的最长公共子序列； 若xm≠yn且zk≠xm ，则Z是Xm-1和Y的最长公共子序列； 若xm≠yn且zk≠yn ，则Z是X和Yn-1的最长公共子序列。 其中Xm-1=x1, x2, …, xm-1，Yn-1=y1, y2, …, yn-1，Zk-1=z1, z2, …, zk-1。 最长公共子序列问题具有 HYPERLINK /algorithm/technique/dynamic_programming/chapter3.htm \l optimality 最优子结构性质。 用c[i,j]记录序列Xi和Yj的最长公共子序列的长度。其中Xi=x1, x2, …, xi，Yj=y1, y2, …, yj。当i=0或j=0时，空序列是Xi和Yj的最长公共子序列，故c[i,j]=0。建立递归关系如下： 1.3程序框图  1.4程序源代码 #includestdio.h #includestring.h int lcs_length(char x[], char y[]); int main() { char x[100],y[100]; int len,i,n; scanf(%d,n); for(i=0;in;i++) { scanf(%s%s,x,y); len=lcs_length(x,y); printf(%d\n,len); } } int lcs_length(char x[], char y[] ) { int m,n,i,j,l[100][100]; m=strlen(x); n=strlen(y); for(i=0;im+1;i++) l[i][0]=0; for(j=0;jn+1;j++) l[0][j]=0; for(i=1;i=m;i++) for(j=1;j=n;j++) if(x[i-1]==y[j-1]) //i,j从1开始，但字符串是从0开始 l[i][j]=l[i-1][j-1]+1; else if(l[i][j-1]l[i-1][j]) l[i][j]=l[i][j-1]; else l[i][j]=l[i-1][j]; return l[m][n]; } 2. 矩阵连乘积问题 2.1问题描述 矩阵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。使得数乘的次数最少。 2.2算法思想 应用动态规划，得到 递归公式： 2.3程序框图  2.4程序源代码 #includestdio.h int N; void main() { int p[101],i,j,k,r,t,v,n; int m[101][101]; //为了跟讲解时保持一致数组从1开始 int s[101][101]; //记录从第i到第j个矩阵连乘的断开位置 scanf(%d,N); for(v=0;vN;v++) { scanf(%d,n); for(i=0;i=n;i++) scanf(%d,p[i]);