`
pleasetojava
  • 浏览: 698228 次
  • 性别: Icon_minigender_2
  • 来自: 上海
文章分类
社区版块
存档分类
最新评论

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

 
阅读更多

// 矩阵链乘法问题.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
请按任意键继续. . .

分享到:
评论

相关推荐

    动态规划解决矩阵链乘法问题

    关于运用动态规划解决矩阵链乘法问题的具体步骤

    JUZHEN.rar_矩阵链乘法

    矩阵链乘法问题就是如何对矩阵乘积加括号,使得它们的乘法次数达到最少。 Input 输入的第一行为一个正整数N(1&lt;=N&lt;=200)。表示矩阵的个数。 输入的第二行包含N+1个整数,分别表示pi(0&lt;=i&lt;=N),其中...

    矩阵连乘问题

    你的任务是要确定矩阵连乘的运算次序,使计算这n个矩阵的连乘积A1A2…An时总的元素乘法次数达到最少。 例如:3个矩阵A1,A2,A3,阶分别为10×100、100×5、5×50,计算连乘积A1A2A3时按(A1A2)A3所需的元素乘法...

    C++ 矩阵加减法

    矩阵(一) 编写C++程序完成以下功能: (1) 假定矩阵大小为4×5(整型数组表示); (2) 定义矩阵初始化函数,可以从cin中输入矩阵元素; (3) 定义矩阵输出函数,将矩阵格式化输出到cout; (4) 定义矩阵相加...

    矩阵连乘的重叠子问题

    例如要计算4个矩阵A1A2A3A4最小连乘次数,要分别计算A1(A2A3A4)、(A1A2)(A3A4)和(A1A2A3)A4三种情况下的最小连乘次数,而计算A1(A2A3A4)的最小连乘次数要计算其子问题A2A3A4的最小连乘次数,A2A3A4最小连乘次数的...

    专科管理学概论A1A2A3卷复习题集.doc

    专科管理学概论A1A2A3卷复习题集.doc

    大九九乘法口诀表(完整EXCEL打印版) A3.xls

    大九九乘法口诀表(完整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等CAD纸张模板(珍贵)包括A0A1A2A3等...

    JuZhenLianCheng.rar_juzhenliancheng_矩阵连乘

    你的任务是要确定矩阵连乘的运算次序,使计算这n个矩阵的连乘积A1A2…An时总的元素乘法次数达到最少。 例如:3个矩阵A1,A2,A3,阶分别为10×100、100×5、5×50,计算连乘积A1A2A3时按(A1A2)A3所需的元素乘法...

    动态规划之矩阵连乘问题Python实现方法

    本文实例讲述了动态规划之矩阵连乘问题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

    趣味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所需的元素乘法...

    城乡规划style(A1A2A3G1G2G3等)

    城乡规划ARCGIS匹配样式符号库

    c语言编程统计因数分解的种数

    给出一个正整数a,要求分解成若干个正整数的乘积,即a = a1 * a2 * a3 * ... * an,并且1 &lt; a1 &lt;= a2 &lt;= a3 &lt;= ... &lt;= an,问这样的分解的种数有多少。注意到a = a也是一种分解。 Input 第1行是测试数据的组数n,...

    PyPI 官网下载 | rkt_armutils-3.0.0.0a3.tar.gz

    资源来自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 ** 的相乘次数

    v1.0.0a3.tar.gz

    在编译目标目录下找到.\3rdparty\tinydnn\downloads\adb1c512e09ca2c7a6faef36f9c53e59\,其中adb1c512e09ca2c7a6faef36f9c53e59可能不一样,进入该目录,将该文件替换掉原来文件

Global site tag (gtag.js) - Google Analytics