我要评论动态规划法是解决问题的一种方法。它不规定为了得到结果需如何将问题划分为子问题的固定方法，而是按不同输入给出问题的具体实例的子问题划分方法，然后再进行运算、解答问题。
矩阵连乘问题的主要思想如下：
1）设置大小为连乘个数的方阵
2）主对角线上方各元素di,j(i<j)表示矩阵mi连乘到mj的最小工作量
3）下方元素di,j(i>j)记录获得该最小工作量矩阵分组的第一组的最后一个矩阵的序列号
最后通过下方元素可知最终结果的分组方式。
算法描述：
1）读入n, 即矩阵的个数;
2）读入n+1个数, 即n个矩阵的行数和列数, 将它们存入数组r中;
3）将d主对角线元素置为零;
4）求出d矩阵的其它元素的数值;
5）给出n个矩阵的结合方式.
code：
[html]
#define maxint 1000
int d[10][10],r[11];
void print(int i, int j)
{
int k;
if(i==j) printf("m%d",i);
else if (i+1==j) printf("m%d,m%d",i,j);
else
{
k =d[j][i];
printf(" (");
print(i,k);
print(k+1, j);
printf(")");
}
}
dm(int n)
{
int i,j,k,t;
for(i=1;i<n-1;i++)
for(j=1;j<n-1;j++)
{
d[j][j+1]=maxint;
for(k=0;k<i-1;k++)
{
t=d[j][j+k]+d[j+k+1][j+1]+r[j-1]*r[j+k]*r[j+1];
if(t<d[j][j+1])
{
d[j][j+1]=t;
d[j][j+1]=j+k;
}
}
}
}
main()
{
int flag=1,n,i;
char c;
printf("e------exit i--------continue\n");
while(flag==1)
{
scanf("%c",&c);
switch(c)
{
case 'i': flag=1;
printf("please input the data:\n");
printf("the value of matrix: n=");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("r[i]=",i);
scanf("%d",&r[i]);
}
for(i=1;i<n;i++) d[i][i]=0;
dm(n);
print(1,n+1);
break;
case 'e': flag=0;break;
}
}
}
作者：yyf573462811
您可能感兴趣的文章:
如您对本文有疑问或者有任何想说的，请点击进行留言回复，万千网友为您解惑！
网友评论