实验：矩阵相乘最小代价顺序.doc

实验：矩阵相乘最小代价顺序实验描述：多个矩阵相乘按照不同的结合相乘得到的相乘次数会有不同，求出一种顺序使得最后完成多个矩阵相乘相乘次数最少的相乘办法，把相乘的次数输出，相乘的顺序输出。输入时按顺序输入各个相乘矩阵的维数，如M1（10*20） * M2（20*50） * M3（50*1） *M4（1*100） 可表示为10 20 50 1 100。实验思路：本题可用典型的动态规划思想解决，用mij表示矩阵Mi *Mi+1 *Mj的最小代价。那么i=j时，mij=0即不用相乘，j!=i时，mij=MIN(mik+mk+1j+rirk+1rj+1),其中i=kj;r数组中储存着输入时对应的维数，如实验描述中r1=10/代表第一个矩阵的行数；r2=20/代表第二个矩阵的行数.r5=100/代表最后一个矩阵的列数。以上思路即可解决最小相乘次数的求出。还需求出相乘的顺序，以如下的形式表示出来：（A1*（A2*A3）*A4按照这种形式输出，那么只需建立一个数组a，大小比矩阵个数大一，分别对应Ai的”(“或”)”的个数。用sij表示Mi到Mj矩阵相乘的断点。实验复杂度分析：程序中需要三重循环，计算次数：0+(0+1)+(0+1+2)+(0+1+2+3)+(0+1+2+3+4)+.+（0+1+2+N）=N+（N-1）*2+（N-2）*3+.+N约为N(3)因为申请了两个N*N 的数组空间，空间复杂度：N(2).实验代码：#include#include#include#define MAX 100const int t=0;int N;int aMAX;int pMAX;int mMAXMAX;int sMAXMAX;void stop(int m,int n)int k;if(n=m+1|n=m)/*at+=n;*/return;k=smn;/printf(%dn,k);if(k!=m)ak-;am+;if(k+1!=n)ak+1+;an-;stop(m,k);stop(k+1,n);void main()int i,j,k,min,temp;printf(请输入总矩阵的个数：n);scanf(%d,&N);printf(请输入每个矩阵的维数：n);for(i=1;i=N+1;i+)scanf(%d,&pi);memset(a,0,sizeof(a);for(j=1;j0;i-)if(i=j)mij=0;sij=i;elsemin=32767;for(k=i;kj;k+)temp=mik+mk+1j+pi*pk+1*pj+1;if(tempmin)min=temp;sij=k;mij=min;printf(代价：%d次n顺序为：,m1N);stop(1,N);for(i=1;i=0)for(j=1;j=ai;j+)printf();if(i=N) printf(A%d,i);else printf(A%d*,i);else printf(A%d,i);for(j=1;j=fabs(ai);j+)printf();if(i!=N)printf(*);printf(n);实验结果： 求两个字符串的最大的公共子序列实验描述：给出两个字符串，如asdfg ，和 axdcfg ，那么他们的公共子序列为adfg，长度为4即找出两个字符串中相同的未打乱顺序的最长子序列。实验思路：本题可以用动态规划的思想解决。用lenij表示第一个字符串的前i个字符与第二个字符串前j个字符的最大公共序列长度。当ai=bj时，lenij=leni-1j-1+1;当ai!=bj时，lenij=MAX(lenij-1,leni-1j);用fatherij表示lenij是由leni-1j-1+1; lenij-1；还是leni-1j得来。用于找到最长公共子序列是哪些字符组成。实验复杂度分析：因为要遍历所有的len空间求出每个的值，所以时间复杂度近似为：O(m*n)因为建立了两个(m+1)*(n+1)的空间，所以空间复杂度为：O(m*n)实验代码：#include#include#define MAX 1000int lenMAXMAX;int fatherMAXMAX;void main()char aMAX,bMAX,cMAX;int i,j,m,n,t=0;printf(输入第一个字符串；n);scanf(%s,a);printf(输入第一个字符串；n);scanf(%s,b);m=strlen(a);n=strlen(b);for(i=0;i=m;i+)len0i=0;father0i=0;for(i=0;i=n;i+)leni0=0;fatheri0=0;for(i=1;i=n;i+)for(j=1;jlenij-1)lenij=leni-1j;fatherij=2;else lenij=lenij-1;fatherij=3;printf(最长公共序列为:%dn此序列为：,lennm);i=n;j=m;while(1)if(fatherij=1)ct+=bi-1;i-;j-;else