矩阵链乘法问题（给A1A2A3...An加括号，使之乘法次数最小）动态规划问题C++实现

曾经终败给现在 2022-06-18 11:11 37阅读 0赞

// 矩阵链乘法问题.cpp : Defines the entry point for the console application.  
//给A1A2A3...An加括号，使之乘法次数最小  
//动态规划问题

\#include "stdafx.h"  
\#include<iostream>  
\#define N 100  
\#define Infinity 65535  
using namespace std;

struct Matrix //矩阵  
\{  
int row; //矩阵行数  
int col; //矩阵列数  
\};

//矩阵  
Matrix matrix\[N\];  
//m\[i\]\[j\]存储Ai到Aj的最小乘法次数  
int m\[N\]\[N\];  
//s\[i\]\[j\]存储Ai到Aj之间加括号的位置  
int s\[N\]\[N\];

//打印加括号后的  
void print\_it(int i,int j)  
\{  
if(i==j)  
cout<<"A"<<i;  
else  
\{  
cout<<"(";  
print\_it(i,s\[i\]\[j\]);  
print\_it(s\[i\]\[j\]+1,j);  
cout<<")";  
\}  
\}

int \_tmain(int argc, \_TCHAR\* argv\[\])  
\{  
int cases;  
cout<<"请输入案例个数："<<endl;  
cin>>cases;  
while(cases--)  
\{  
//变量初始化  
memset(m,0,sizeof(m));  
memset(s,0,sizeof(s));  
cout<<"请输入矩阵的个数："<<endl;  
int n;  
cin>>n;  
//flag表示输入是否符合要求  
bool flag = true;  
int i =1;  
while(flag)  
\{  
cout<<"请输入每个矩阵行数与列数："<<endl;  
for(i=1;i<=n;i++)  
\{  
cout<<"A"<<i<<"行数：";  
cin>>matrix\[i\].row;  
cout<<"A"<<i<<"列数：";  
cin>>matrix\[i\].col;  
\}  
//检查Ai的列数是否等于Ai+1的行数  
for(i=1;i<n;i++)  
\{  
if(matrix\[i\].col != matrix\[i+1\].row)  
break;  
\}  
if(i>=n)  
flag = false;  
else  
\{  
flag = true;  
cout<<"输入不符合要求，存在矩阵的列数不等于后面一个矩阵的行数，请重新输入！"<<endl;  
\}  
\}  
int l,j,k;  
for(l=2;l<=n;l++)  
\{  
for(i=1;i<=n-l+1;i++)  
\{  
j = i+l-1;  
m\[i\]\[j\] = Infinity;  
int q =0;  
for(k=i;k<=j-1;k++)  
\{  
q = m\[i\]\[k\] + m\[k+1\]\[j\] + matrix\[i\].row\*matrix\[k\].col\*matrix\[j\].col;  
if(m\[i\]\[j\]>q)  
\{  
m\[i\]\[j\] = q;  
s\[i\]\[j\] = k;  
\}  
\}  
\}  
\}  
cout<<"加括号之后："<<endl;  
print\_it(1,n);  
cout<<endl;  
cout<<"最小乘法次数为："<<m\[1\]\[n\]<<endl;;  
\}  
system("pause");  
return 0;  
\}

\----------------------------------------------------程序测试-------------------------------------------------

请输入案例个数：  
1  
请输入矩阵的个数：  
6  
请输入每个矩阵行数与列数：  
A1行数：30  
A1列数：35  
A2行数：35  
A2列数：15  
A3行数：15  
A3列数：5  
A4行数：5  
A4列数：10  
A5行数：10  
A5列数：20  
A6行数：20  
A6列数：25  
加括号之后：  
((A1(A2A3))((A4A5)A6))  
最小乘法次数为：15125  
请按任意键继续. . .