算法设计与分析/数据结构与算法实验3:矩阵连乘问题

简介: 算法设计与分析/数据结构与算法实验3:矩阵连乘问题

1.实验目的

(1)掌握动态规划法的处理思路与算法框架。

(2)掌握应用动态规划法解决具体问题的方法。

(3)掌握动态规划法的广泛应用。

2.实验内容

(1)问题描述

image.png

(2)输入

image.png


(3)输出

输出分为两行。

第一行输出一个整数,表示矩阵在以最优计算次序求解连乘积时,所需要计算的次数。

第二行输出求解矩阵连乘积的最优次序。

3.问题实例分析


image.png

0
0
0
0
0


image.png

0 1500
0 750
0 750
0 1500
0


image.png

0 1500 1750
0 750 1000
0 750 3000
0 1500
0

image.png

0 1500 1750 1500
0 750 1000 1750
0 750 3000
0 1500
0

image.png

0 1500 1750 1500 4500
0 750 1000 1750
0 750 3000
0 1500
0

image.png


0 1 1 1 4
0 2 3 4
0 3 4
0 4
0

image.png


4.算法描述及说明

正如第3节问题实例分析所述,算法的整体流程如下:

image.png


5.算法正确性分析

image.png


7.运行结果展示及其说明

测试样例使用了两组。对于每一组测试样例,都正确地输出了计算次数与次序,并在最后给出了最优的加括号的方案。

8.心得体会

9.程序源代码

#include<iostream>
const int N = 1005;
long long dp[N][N];
long long p[N];
int pos[N][N];
int posl[N];//记录左括号位置
int posr[N];//记录右括号位置
using namespace std;
void traceback(int i,int j) {
  if (i == j)
    return;
  traceback(i, pos[i][j]);
  traceback(pos[i][j] + 1, j);
  posl[i]++;
  posr[j]++;
  cout << "Multiply A" << i << "," << pos[i][j] << " and A" << pos[i][j] + 1 << "," << j<<endl;
}
int main() {
  int n;
  cin >> n;
  for (int i = 0; i <= n; i++)
    cin >> p[i];
  for (int i = 1; i <= n; i++)
    dp[i][i] = 0;
  for (int len = 2; len <= n; len++) {
    for (int i = 1; i <= n - len + 1; i++) {
      int j = i + len - 1;
      dp[i][j] = dp[i + 1][j] + p[i - 1] * p[i] * p[j];
      pos[i][j] = i;
      for (int k = i + 1; k < j; k++) {
        int t = dp[i][k] + dp[k + 1][j] + p[i - 1] * p[k] * p[j];
        if (t < dp[i][j]) {
          dp[i][j] = t;
          pos[i][j] = k;
        }
      }
    }
  }
  cout << "计算次数" << dp[1][n] << endl;
  traceback(1, n);
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j < posl[i]; j++)
      cout << '(';
    cout << 'A' << i ;
    for (int j = 0; j < posr[i]; j++)
      cout << ')';
  }
}


目录
相关文章
|
16天前
|
存储 人工智能 算法
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
这篇文章详细介绍了Dijkstra和Floyd算法,这两种算法分别用于解决单源和多源最短路径问题,并且提供了Java语言的实现代码。
49 3
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
|
19天前
|
机器学习/深度学习 存储 缓存
数据结构与算法学习十:排序算法介绍、时间频度、时间复杂度、常用时间复杂度介绍
文章主要介绍了排序算法的分类、时间复杂度的概念和计算方法,以及常见的时间复杂度级别,并简单提及了空间复杂度。
18 1
数据结构与算法学习十:排序算法介绍、时间频度、时间复杂度、常用时间复杂度介绍
|
12天前
|
存储 算法 Java
Set接口及其主要实现类(如HashSet、TreeSet)如何通过特定数据结构和算法确保元素唯一性
Java Set因其“无重复”特性在集合框架中独树一帜。本文解析了Set接口及其主要实现类(如HashSet、TreeSet)如何通过特定数据结构和算法确保元素唯一性,并提供了最佳实践建议,包括选择合适的Set实现类和正确实现自定义对象的hashCode()与equals()方法。
28 4
|
18天前
|
算法 搜索推荐 Java
java 后端 使用 Graphics2D 制作海报,画echarts图,带工具类,各种细节:如头像切割成圆形,文字换行算法(完美实验success),解决画上文字、图片后不清晰问题
这篇文章介绍了如何使用Java后端技术,结合Graphics2D和Echarts等工具,生成包含个性化信息和图表的海报,并提供了详细的代码实现和GitHub项目链接。
63 0
java 后端 使用 Graphics2D 制作海报,画echarts图,带工具类,各种细节:如头像切割成圆形,文字换行算法(完美实验success),解决画上文字、图片后不清晰问题
|
19天前
|
搜索推荐 算法
数据结构与算法学习十四:常用排序算法总结和对比
关于常用排序算法的总结和对比,包括稳定性、内排序、外排序、时间复杂度和空间复杂度等术语的解释。
13 0
数据结构与算法学习十四:常用排序算法总结和对比
|
19天前
|
存储 缓存 分布式计算
数据结构与算法学习一:学习前的准备,数据结构的分类,数据结构与算法的关系,实际编程中遇到的问题,几个经典算法问题
这篇文章是关于数据结构与算法的学习指南,涵盖了数据结构的分类、数据结构与算法的关系、实际编程中遇到的问题以及几个经典的算法面试题。
26 0
数据结构与算法学习一:学习前的准备,数据结构的分类,数据结构与算法的关系,实际编程中遇到的问题,几个经典算法问题
|
18天前
|
机器学习/深度学习 搜索推荐 算法
探索数据结构:初入算法之经典排序算法
探索数据结构:初入算法之经典排序算法
|
19天前
|
算法 Java 索引
数据结构与算法学习十五:常用查找算法介绍,线性排序、二分查找(折半查找)算法、差值查找算法、斐波那契(黄金分割法)查找算法
四种常用的查找算法:顺序查找、二分查找(折半查找)、插值查找和斐波那契查找,并提供了Java语言的实现代码和测试结果。
15 0
|
22天前
|
存储 算法 Java
数据结构和算法--分段树
数据结构和算法--分段树
11 0
|
25天前
|
算法
计科一二班算法数据结构实验9答案
计科一二班算法数据结构实验9答案
12 0

热门文章

最新文章