// 矩阵链乘法问题.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
请按任意键继续. . .
分享到:
相关推荐
关于运用动态规划解决矩阵链乘法问题的具体步骤
矩阵链乘法问题就是如何对矩阵乘积加括号,使得它们的乘法次数达到最少。 Input 输入的第一行为一个正整数N(1<=N<=200)。表示矩阵的个数。 输入的第二行包含N+1个整数,分别表示pi(0<=i<=N),其中...
你的任务是要确定矩阵连乘的运算次序,使计算这n个矩阵的连乘积A1A2…An时总的元素乘法次数达到最少。 例如:3个矩阵A1,A2,A3,阶分别为10×100、100×5、5×50,计算连乘积A1A2A3时按(A1A2)A3所需的元素乘法...
矩阵(一) 编写C++程序完成以下功能: (1) 假定矩阵大小为4×5(整型数组表示); (2) 定义矩阵初始化函数,可以从cin中输入矩阵元素; (3) 定义矩阵输出函数,将矩阵格式化输出到cout; (4) 定义矩阵相加...
例如要计算4个矩阵A1A2A3A4最小连乘次数,要分别计算A1(A2A3A4)、(A1A2)(A3A4)和(A1A2A3)A4三种情况下的最小连乘次数,而计算A1(A2A3A4)的最小连乘次数要计算其子问题A2A3A4的最小连乘次数,A2A3A4最小连乘次数的...
专科管理学概论A1A2A3卷复习题集.doc
大九九乘法口诀表(完整EXCEL打印版) A3.xls
给定n个矩阵{A1,…,An},其中Ai和Ai+1可乘,i=1,2,…,n-1。考察矩阵连乘积加括弧的方式数。 如四个矩阵连乘积A1A2A3A4,共有五种不同的加括弧方式: ( A1 ( A2 ( A3 A4 ) ) ) ( A1 ( ( A2 A3 ) A4 ) ) ( ( A1A2 )...
CAD纸张模板(珍贵)包括A0A1A2A3等CAD纸张模板(珍贵)包括A0A1A2A3等CAD纸张模板(珍贵)包括A0A1A2A3等CAD纸张模板(珍贵)包括A0A1A2A3等CAD纸张模板(珍贵)包括A0A1A2A3等CAD纸张模板(珍贵)包括A0A1A2A3等...
你的任务是要确定矩阵连乘的运算次序,使计算这n个矩阵的连乘积A1A2…An时总的元素乘法次数达到最少。 例如:3个矩阵A1,A2,A3,阶分别为10×100、100×5、5×50,计算连乘积A1A2A3时按(A1A2)A3所需的元素乘法...
本文实例讲述了动态规划之矩阵连乘问题Python实现方法。分享给大家供大家参考,具体如下: 给定n个矩阵{A1,A2,…,An},其中Ai与Ai+1是可乘的,i=1,2 ,…,n-1。如何确定计算矩阵连乘积的计算次序,使得依此次序计算...
矩阵(二) 编写C++程序完成以下功能: (1) 假定矩阵大小为4×5(整型);...(7) 动态申请三个矩阵:A1、A2、A3; (8) 初始化A1、A2; (9) 计算并输出A3 = A1加A2,A3 = A1减A2; (10) 释放矩阵空间
矩阵相加的函数,实现两个矩阵相加的功能,结果保存在另一个矩阵类,但必须矩阵大小相同; 矩阵相减的函数,实现两个矩阵相减的功能,结果保存在另一个矩阵类,但必须矩阵大小相同。 (3) 定义三个矩阵:A1、A2、A3...
趣味matlab编程学习向量矩阵-shiftM.m ...给定一个任意的1×n向量A=[a1 a2 a3...a_{n-1} a_n],请用MATLAB的有关命令构造如下的矩阵: Figure34.jpg 自己先做再看下面的
你的任务是要确定矩阵连乘的运算次序,使计算这n个矩阵的连乘积A1A2…An时总的元素乘法次数达到最少。 例如:3个矩阵A1,A2,A3,阶分别为10×100、100×5、5×50,计算连乘积A1A2A3时按(A1A2)A3所需的元素乘法...
城乡规划ARCGIS匹配样式符号库
给出一个正整数a,要求分解成若干个正整数的乘积,即a = a1 * a2 * a3 * ... * an,并且1 < a1 <= a2 <= a3 <= ... <= an,问这样的分解的种数有多少。注意到a = a也是一种分解。 Input 第1行是测试数据的组数n,...
资源来自pypi官网。 资源全名:rkt_armutils-3.0.0.0a3.tar.gz
给定n个矩阵{A1,A2,…,An},其中Ai与Ai+1是可乘的,i=1,2…,n-1。如何确定计算矩阵连乘积的计算次序,使得依此...有三个矩阵A1,A2,A3 大小分别为10* 100,100* 5,5*50,考虑**(A1(A2A3), (A1A2)A3 ** 的相乘次数
在编译目标目录下找到.\3rdparty\tinydnn\downloads\adb1c512e09ca2c7a6faef36f9c53e59\,其中adb1c512e09ca2c7a6faef36f9c53e59可能不一样,进入该目录,将该文件替换掉原来文件