搜索
习题1．最长公共子序列一个给定序列的子序列是在该序列中删去若干元素后得到的序列。确切地说，若给定序列X=x1,x2,…,xm，则另一序列Z=z1,z2,…,zk是X的子序列是指存在一个严格递增的下标序列i1,i2,…,ik，使得对于所有j=1,2,…,k有解答如下：a)最长公共子序列的结构若用穷举搜索法，耗时太长，算法需要指数时间。易证最长公共子序列问题也有最优子结构性质设序列X=x1,x2,…,xm和Y=y1,y2,…,yn的一个最长公共子序列Z=z1,z2,…,zk，则：i.若xm=yn，则zk=xm=yn且Zk-1是Xm-1和Yn-1的最长公共子序列；ii.若xm≠yn且zk≠xm，则Z是Xm-1和Y的最长公共子序列；iii.若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。最长公共子序列问题具有最优子结构性质。b)子问题的递归结构由最长公共子序列问题的最优子结构性质可知，要找出X=x1,x2,…,xm和Y=y1,y2,…,yn的最长公共子序列，可按以下方式递归地进行：当xm=yn时，找出Xm-1和Yn-1的最长公共子序列，然后在其尾部加上xm(=yn)即可得X和Y的一个最长公共子序列。当xm≠yn时，必须解两个子问题，即找出Xm-1和Y的一个最长公共子序列及X和Yn-1的一个最长公共子序列。这两个公共子序列中较长者即为X和Y的一个最长公共子序列。由此递归结构容易看到最长公共子序列问题具有子问题重叠性质。例如，在计算X和Y的最长公共子序列时，可能要计算出X和Yn-1及Xm-1和Y的最长公共子序列。而这两个子问题都包含一个公共子问题，即计算Xm-1和Yn-1的最长公共子序列。我们来建立子问题的最优值的递归关系。用c[i,j]记录序列Xi和Yj的最长公共子序列的长度。其中Xi=x1,x2,…,xi，Yj=y1,y2,…,yj。当i=0或j=0时，空序列是Xi和Yj的最长公共子序列，故c[i,j]=0。建立递归关系如下：c)计算最优值由于在所考虑的子问题空间中，总共只有θ(m*n)个不同的子问题，因此，用动态规划算法自底向上地计算最优值能提高算法的效率。计算最长公共子序列长度的动态规划算法LCS_LENGTH(X,Y)以序列X=x1,x2,…,xm和Y=y1,y2,…,yn作为输入。输出两个数组c[0..m,0..n]和b[1..m,1..n]。其中c[i,j]存储Xi与Yj的最长公共子序列的长度，b[i,j]记录指示c[i,j]的值是由哪一个子问题的解达到的，这在构造最长公共子序列时要用到。最后，X和Y的最长公共子序列的长度记录于c[m,n]中。程序如下：#includestdio.h#includestring.hintlcs_length(charx[],chary[]);intmain(){charx[100],y[100];intlen;while(1){scanf(%s%s,x,y);if(x[0]=='0')//约定第一个字符串以‘0’开始表示结束break;len=lcs_length(x,y);printf(%d\n,len);}}intlcs_length(charx[],chary[]){intm,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;elseif(l[i][j-1]l[i-1][j])l[i][j]=l[i][j-1];elsel[i][j]=l[i-1][j];returnl[m][n];}由于每个数组单元的计算耗费Ο(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。递归公式：程序如下：#includestdio.hintmain(){intp[101],i,j,k,r,t,n;intm[101][101];//为了跟讲解时保持一致数组从1开始ints[101][101];//记录从第i到第j个矩阵连乘的断开位置scanf(%d,&n);for(i=0;i=n;i++)scanf(%d,&p[i]);//读入p[i]的值(注意：p[0]到p[n]共n+1项)for(i=1;i=n;i++)//初始化m[i][i]=0m[i][i]=0;for(r=1;rn;r++)//r为i、j相差的值for(i=1;in;i++)//i为行{j=i+r;//j为列m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];//给m[i][j]赋初值s[i][j]=i;for(k=i+1;kj;k++){t=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];if(tm[i][j]){m[i][j]=t;//m[i][j]取最小值s[i][j]=k;}}}printf(%d,m[1][n]);}3．凸多边形的最优三角剖分多边形是平面上一条分段线性的闭曲线。也就是说，多边形是由一系列首尾相接的直线段组成的。组成多边形的各直线段称为该多边形的边。多边形相接两条边的连接点称为多边形的顶点。若多边形的边之间除了连接顶点外没有别的公共点，则称该多边形为简单多边形。一个简单多边形将平面分为3个部分：被包围在多边形内的所有点构成了多边形的内部；多边形本身构成多边形的边界；而平面上其余的点构成了多边形的外部。当一个简单多边形及其内部构成一个闭凸集时，称该简单多边形为凸多边形。也就是说凸多边形边界上或内部的任意两点所连成的直线段上所有的点均在该凸多边形的内部或边界上。通常，用多边形顶点的逆时针序列来表示一个凸多边形，即P=v0,v1,…,vn-1表示具有n条边v0v1，v1v2，…,vn-1vn的一个凸多边形，其中，约定v0=vn。若vi与vj是多边形上不相邻的两个顶点，则线段vivj称为多边形的一条弦。弦将多边形分割成凸的两个子多边形vi,vi+1,…,vj和vj,vj+1,…,vi。多边形的三角剖分是一个将多边形分割成互不重迭的三角形的弦的集合T。如图是一个凸多边形的两个不同的三角剖分。凸多边形最优三角剖分的问题是：给定一个凸多边形P=v0,v1,…,vn-1以及定义在由多边形的边和弦组成的三角形上的权函数ω。要求确定该凸多边形的一个三角剖分，使得该三角剖分对应的权即剖分中诸三角形上的权之和为最小。可以定义三角形上各种各样的权函数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]的最大值。程序如下：#includestdio.hintmain(){inti,j,n,max,h[100],l[100];scanf(%d,&n);for(i=0;in;i++)scanf(%d,&h[i]);l[n-1]=1;for(i=n-2;i=0;i--){max=0;for(j=i+1;jn;j++)if(h[i]h[j]&&maxl[j])max=l[j];l[i]=max+1;}printf(%d,l[0]);}5．石子合并在一个圆形操场的四周摆放着n堆石子(n=100)，现要将石子有次序地合并成一堆。规定每次只能选取相邻的两堆合并成新的一堆,并将新的一堆的石子数,记为该次合并的得分。编一程序，由文件读入堆栈数n及每堆栈的石子数(=20)。选择一种合并石子的方案,使得做n－1次合并,得分的总和最小；输入数据：第一行为石子堆数n；第二行为每堆的石子数,每两个数之间用一个空格分隔。输出数据：从第一至第n行为得分最小的合并方案。第n+1行是空行.从第n+2行到第2n+1行是得分最大合并方案。每种合并方案用n行表示，其中第i行(1=i=n)表示第i次合并前各堆的石子数(依顺时针次序输出，哪一堆先输出均可)。要求将待合并的两堆石子数以相应的负数表示。SampleInput44594SampleOutput－459－4－8－59－13－9224－5－944－14－4－4－18226．最小代价子母树设有一排数，共n个，例如：2214713261511。任意2个相邻的数可以进行归并，归并的代价为该两个数的和,经过不断的归并，最后归为一堆，而全部归并代价的和称为总代价，给出一种归并算法，使总代价为最小。输入、输出数据格式与“石子合并”相同。SampleInput4125164SampleOutput－12－516417－16－4－17－20377．商店购物某商店中每种商品都有一个价格。例如，一朵花的价格是2ICU(ICU是信息学竞赛的货币的单位）；一个花瓶的价格是5ICU。为了吸引更多的顾客，商店提供了特殊优惠价。特殊优惠商品是把一种或几种商品分成一组。并降价销售。例如：3朵花的价格不是6而是5ICU；2个花瓶加1朵花是10ICU不是12ICU。编一个程序，计算某个顾客所购商品应付的费用。要充分利用优惠价以使顾客付款最小。请注意，你不能变更顾客所购商品的种类及数量，即使增加某些商品会使付款总数减小也不允许你作出任何变更。假定各种商品价格用优惠价如上所述，并且某顾客购买物品为：3朵花和2个花瓶。那么顾客应付款为14ICU因为：1朵花加2个花瓶优惠价：10ICU2朵花正常价：4ICU输入数据：第一个文件INPUT．TXT描述顾客所购物品（放在购物筐中）;第二个文件描述商店提供的优惠商品及价格（文件名为OFFER．TXT）。两个文件中都只用整数。第一个文件INPUT．TXT的格式为:第一行是一个数字B（0≤B≤5），表示所购商品种类数。下面共B行，每行中含3个数C，K，P。C代表商品的编码（每种商品有一个唯一的编码），1≤C≤999。K代表该种商品购买总数，1≤K≤5。P是该种商品的正常单价