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

《实验：矩阵相乘最小代价顺序》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验：矩阵相乘最小代价顺序实验描述：多个矩阵相乘按照不同的结合相乘得到的相乘次数会有不同，求出一种顺序使得最后完成多个矩阵相乘相乘次数最少的相乘办法，把相乘的次数输出，相乘的顺序输出。输入时按顺序输入各个相乘矩阵的维数，如M1（10*20）*M2（20*50）*M3（50*1）*M4（1*100）可表示为1020501100。实验思路：本题可用典型的动态规划思想解决，用m[i][j]表示矩阵M[i]*M[i+1]*……*M[j]的最小代价。那么i==j时，m[i][j]=0即不用相乘，j!=i时，m[i][j]=MIN(m[i][k]+m[k

2、+1][j]+r[i]r[k+1]r[j+1]),其中i<=k

3、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#defineMAX100constintt=0;intN;inta[MAX];intp[MAX];intm[MAX][MAX];ints[MAX][MAX];voidstop(intm,intn){intk;if(n

4、==m+1

5、

6、n==m){/*a[t++]=n;*/return;}k=s[m][n];//printf("%d",k);if(k!=m){a[k]--;a[m]++;}if(k+1!=n){a[k+1]++;a[n]--;}stop(m,k);stop(k+1,n);}voidmain(){inti,j,k,min,temp;printf("请输入总矩阵的个数：");scanf("%d",&N);printf("请输入每个矩阵的维数：");for(i=1;i<=N+1;i++)scanf("%d",&p[i]);memset(a

7、,0,sizeof(a));for(j=1;j<=N;j++)for(i=j;i>0;i--){if(i==j){m[i][j]=0;s[i][j]=i;}else{min=32767;for(k=i;k=0){for

8、(j=1;j<=a[i];j++)printf("(");if(i==N)printf("A%d",i);elseprintf("A%d*",i);}else{printf("A%d",i);for(j=1;j<=fabs(a[i]);j++)printf(")");if(i!=N)printf("*");}}printf("");}实验结果：求两个字符串的最大的公共子序列实验描述：给出两个字符串，如asdfg，和axdcfg，那么他们的公共子序列为adfg，长度为4即找出两个字符串中相同的未打乱顺序的最长子序列。实验思路：本题可以用动态

9、规划的思想解决。用len[i][j]表示第一个字符串的前i个字符与第二个字符串前j个字符的最大公共序列长度。当a[i]=b[j]时，len[i][j]=len[i-1][j-1]+1;当a[i]!=b[j]时，len[i][j]=MAX(len[i][j-1],len[i-1][j]);用father[i][j]表示len[i][j]是由len[i-1][j-1]+1;len[i][j-1]；还是len[i-1][j]得来。用于找到最长公共子序列是哪些字符组成。实验复杂度分析：因为要遍历所有的len[][]空间求出每个的值，所以时间复杂度近似

10、为：O(m*n)因为建立了两个(m+1)*(n+1)的空间，所以空间复杂度为：O(m*n)实验代码：#include#include