算法实验:矩阵连乘(动态规划)

2023-11-09 06:58

本文主要是介绍算法实验:矩阵连乘(动态规划),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Description
给你2个矩阵A、B,我们使用标准的矩阵相乘定义C=AB如下: A数组中栏(column)的数目一定要等于B数组中列(row)的数目才可以做此2数组的相乘。若我们以rows(A),columns(A)分 别代表A数组中列及栏的数目,要计算C数组共需要的乘法的数目为:rows(A)columns(B)columns(A)。例如:A数组是一个 10x20的矩阵,B数组是个20x15的矩阵,那么要算出C数组需要做101520,也就是3000次乘法。 要计算超过2个以上的矩阵相乘就得决定要用怎样的顺序来做。例如:X、Y、Z都是矩阵,要计算XYZ的话可以有2种选择:(XY)Z 或者 X(YZ)。假设X是5x10的数组,Y是10x20的数组,Z是20x35的数组,那个不同的运算顺序所需的乘法数会有不同: (XY)Z • 52010 = 1000次乘法完成(XY),并得到一5x20的数组。 • 53520 = 3500次乘法得到最后的结果。 • 总共需要的乘法的次数:1000+3500=4500。 X(YZ) • 103520 = 7000次乘法完成(YZ),并得到一10x35的数组。 • 53510 = 1750次乘法得到最后的结果。 • 总共需要的乘法的次数:7000+1750=8750。 很明显的,我们可以知道计算(XY)Z会使用较少次的乘法。 这个问题是:给你一些矩阵,你要写一个程序来决定该如何相乘的顺序,使得用到乘法的次数会最少。

Input
含有多组测试数据,每组测试数据的第一列,含有1个整数N(N <= 10)代表有多少个数组要相乘。接下来有N对整数,代表一数组的列数及栏数。这N个数组的顺序与要你相乘的数组顺序是一样的。N=0代表输入结束。请参考Sample Input。

Output
每组测试数据输出一列,内容为矩阵相乘的顺序(以刮号来表示)使得所用的乘法次数最小。如果有不只一组答案,输出任一组均可。请参考Sample Output。

Sample Input
3
1 5
5 20
20 1
3
5 10
10 20
20 35
6
30 35
35 15
15 5
5 10
10 20
20 25
0
Sample Output
Case 1: (A1 x (A2 x A3))
Case 2: ((A1 x A2) x A3)
Case 3: ((A1 x (A2 x A3)) x ((A4 x A5) x A6))

动态转移方程

在这里插入图片描述

利用备忘录方法记录下每次子问题计算出来的答案,最后如果再需要只要查一下子问题的答案即可
mm[i][j]用来表示[i, j]区间内所需的最小乘法次数, xx[i][j]表示对应于mm[i][j]的断开位置。
最后利用xx[i][j]递归输出答案即可

代码:

#include <cstdio>
#include <cstring>
const int M = 15;
int rows[M], columns[M];
int mm[M][M], xx[M][M];
int tot;
int n;
int find_(int l, int r) {if (l == r) return mm[l][r] = 0;if (mm[l][r] != -1) return mm[l][r];int ans = find_(l + 1, r) + rows[l] * columns[r] * columns[r];int x = l;for (int i = l + 1; i < r; ++i) {if (find_(l, i) + find_(i + 1, r) + rows[l] * columns[r] * columns[i] < ans) {x = i;ans = find_(l, i) + find_(i + 1, r) + rows[l] * columns[r] * columns[i];}}xx[l][r] = x;return mm[l][r] = ans;
}
void find__(int l, int r) {if (r - l == 0) {printf("A%d", l + 1);return;}int temp = xx[l][r];if (temp - l == 0)find__(l, temp);else {printf("(");find__(l, temp);printf(")");}printf(" x ");if (r - (temp + 1) == 0) {find__(temp + 1, r);}else {printf("(");find__(temp + 1, r);printf(")");}
}
int main() {int cnt = 1;while (scanf("%d", &n) != EOF) {tot = 0;if (n == 0) break;memset(mm, -1, sizeof(mm));memset(xx, -1, sizeof(xx));for (int i = 0; i < n; ++i) scanf("%d%d", &rows[i], &columns[i]);find_(0, n - 1);printf("Case %d: ", cnt++);printf("(");find__(0, n - 1);printf(")\n");}return 0;
}

这篇关于算法实验:矩阵连乘(动态规划)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/374584

相关文章

Java调用C++动态库超详细步骤讲解(附源码)

《Java调用C++动态库超详细步骤讲解(附源码)》C语言因其高效和接近硬件的特性,时常会被用在性能要求较高或者需要直接操作硬件的场合,:本文主要介绍Java调用C++动态库的相关资料,文中通过代... 目录一、直接调用C++库第一步:动态库生成(vs2017+qt5.12.10)第二步:Java调用C++

springboot+dubbo实现时间轮算法

《springboot+dubbo实现时间轮算法》时间轮是一种高效利用线程资源进行批量化调度的算法,本文主要介绍了springboot+dubbo实现时间轮算法,文中通过示例代码介绍的非常详细,对大家... 目录前言一、参数说明二、具体实现1、HashedwheelTimer2、createWheel3、n

C#如何动态创建Label,及动态label事件

《C#如何动态创建Label,及动态label事件》:本文主要介绍C#如何动态创建Label,及动态label事件,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C#如何动态创建Label,及动态label事件第一点:switch中的生成我们的label事件接着,

SpringCloud动态配置注解@RefreshScope与@Component的深度解析

《SpringCloud动态配置注解@RefreshScope与@Component的深度解析》在现代微服务架构中,动态配置管理是一个关键需求,本文将为大家介绍SpringCloud中相关的注解@Re... 目录引言1. @RefreshScope 的作用与原理1.1 什么是 @RefreshScope1.

MyBatis 动态 SQL 优化之标签的实战与技巧(常见用法)

《MyBatis动态SQL优化之标签的实战与技巧(常见用法)》本文通过详细的示例和实际应用场景,介绍了如何有效利用这些标签来优化MyBatis配置,提升开发效率,确保SQL的高效执行和安全性,感... 目录动态SQL详解一、动态SQL的核心概念1.1 什么是动态SQL?1.2 动态SQL的优点1.3 动态S

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

mybatis-plus 实现查询表名动态修改的示例代码

《mybatis-plus实现查询表名动态修改的示例代码》通过MyBatis-Plus实现表名的动态替换,根据配置或入参选择不同的表,本文主要介绍了mybatis-plus实现查询表名动态修改的示... 目录实现数据库初始化依赖包配置读取类设置 myBATis-plus 插件测试通过 mybatis-plu

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

基于Canvas的Html5多时区动态时钟实战代码

《基于Canvas的Html5多时区动态时钟实战代码》:本文主要介绍了如何使用Canvas在HTML5上实现一个多时区动态时钟的web展示,通过Canvas的API,可以绘制出6个不同城市的时钟,并且这些时钟可以动态转动,每个时钟上都会标注出对应的24小时制时间,详细内容请阅读本文,希望能对你有所帮助...