矩阵链相乘算法.docx

矩阵链相乘问题求解
一、说说递归与动态规划
a）递归
我们知道递归的思想是利用自己来调用自己本身来实现问题分解后层层深入求解直至到达定义的边界条件后层层返回将问题合并。最后得出解的一个过程。递归需要一个边界添加来终止递归。这是一个非常
7
8
9
10
11
12
13
14
retrunmands
注释
因为我们在表示矩阵相乘产生的计算量时是利用二维数组m[i][j]存储表示的。但是我
们知道在数组中i<=j所以如上图所示是一个上三角，且正对角线上的值为零。
现在我们来逐行分析算法
函数名参数p为一个整形的数组。在这里我说说这个数组。在这个数组里存放的是需要连乘的各个数组的维数信息。但是并不是想象中那样将所有数组的行和列都存储进去的。由于相乘矩阵的特殊性。也早就了特别的存储方式。设有四个矩阵的情况如下：
A(10,100),B(100,5),C(5,50),D(50,15)
从以上矩阵中我们可以看到中间各个矩阵的行列之间有相同项。为了节省空间我们只储存相同的一项也就是去重存储。而我们的存储策略是出来第一个矩阵的行列都存储以外其他的矩阵我们只存储其列项。而存储列信息的前一项便是其行信息则以上四个矩阵的存信息如下：
P[0]=10;p[1]=100;p[2]=5;p[3]=50;p[4]=15;
如果我们想知道第三个矩阵的信息是便可以提取(p[3-1],p[3])即为第三个矩阵的行和列。
获取需要相乘的矩阵的个数
3,4-将存储计算量的数组的正对角线上的值初始化为0•因为对角线上的矩阵相乘的数
为1也就是数组本身，当然相乘的计算量就是0了。
5-13行是一个大循环。第5行1是说明我们要计算的矩阵链的长度。。而1是我们要计算的矩阵链的长度，是从2开始的。也就是说我们将会在接下来的循环里分别计算所有长度为2,3,4,5・・・n的计算量。举例来说。如果n为6则1的取值可能为2,3,4,5,。理解这个很重要。第6行的i是长度为1的矩阵链的起始位置。
第7行的j便是结束位置了。
第8行是将初次使用的m[i][j]值初始化为无穷大
9-13行的for便是用来确定k值的。思想是在长度为1的矩阵链中从位置i开始往后以此试着计算其计算量。如有较小的值则存入到m[i][j]中并且保存当前的位置k。将其存入到数组s中。
e)备注
四、源码及分析
a)C语言描述示例

获取信息数组p
int*getMatrix(){
inti,j=0,dimension[n+1];
printf("Howmanymatrixdoyouwanttocaculate?\n:=");scanf("%d",&n);
for(i=0;i<n+1;i++){
讦(i==0)
printf("Pleaseinputtherownumberofthe1thmatrix:");
else
printf("Pleaseinputthecolumnnumberofthe%dthmatrix:",i);scanf("%d",&dimension[i]);
}
int*m=dimension;
returnm;
}
计算最有参数
voidma