现在的位置: 首页 > 综合 > 正文

矩阵连乘问题的一个具体实现

2013年11月18日 ⁄ 综合 ⁄ 共 745字 ⁄ 字号 评论关闭

输入: 连续相乘矩阵的总个数(不超过20),每个矩阵的维度(因为上一个矩阵的列是下一个矩阵的行,所以只需输入一个n+1维度的数组即可)

输出:最小计算量,以及加括号的方法

源代码:

#include <iostream>

using namespace std;
int arr[20][20]={0};//存储i到j之间的最小计算量
int split[20][20];//存储划分为二部分的矩阵位置
int dimension[21]={0};//输入矩阵的维度
int length=0;//矩阵连续乘的个数

void show1(int a,int b)
{
if(a==b)
{
cout<<"A"<<a;
return;
}
int t=split[a][b];
cout<<"(";
show1(a,t);
show1(t+1,b);
cout<<")";

}
void show()
{
cout<<"最小计算量:"<<arr[0][length-1]<<endl;
show1(0,length-1);
}
void main()
{
cin>>length;
for(int i=0;i<=length;++i)
cin>>dimension[i];
for(int i=1;i<length;++i)
for(int j=0;j<=length-1-i;++j)
{
arr[j][j+i]=999999999;
for(int k=j;k<j+i;k++)
{
int temp=arr[j][k]+arr[k+1][j+i]+dimension[j]*dimension[k+1]*dimension[k+i];
if(temp<arr[j][j+i])
{
arr[j][j+i]=temp;
split[j][j+i]=k;
}
}
}
show();
::system("pause");
}

抱歉!评论已关闭.