一、【实验目的】
(1)进一步理解动态规划算法的设计要素
(2)熟悉动态规划算法中备忘录和标记函数的设计
(3)能够应用备忘录和标记函数实现结果的跟踪。
二、【实验内容】
输入:矩阵链Ai…j的输入为向量P=<Pi-1,Pi,…,Pj>,其中:1<=i<=j<=n.
输出:矩阵链Ai…j乘法的**运算次序。
要求采用迭代方法进行程序设计,并设计备忘录和标记函数表。
三、【实验源代码】
👨🏫 参考:动态规划(详解矩阵连乘 案例+Java代码实现)
👨🏫 Cpp版
#include <bits/stdc++.h> using namespace std; //输入:矩阵链Ai…j的输入为向量P=<Pi-1,Pi,…,Pj>,其中:1<=i<=j<=n. //输出:计算Ai…j的所需最小乘法运算次数m[i,j]和最后一次运算位置s[i,j]。 const int N = 101; int m[N][N], s[N][N]; int a[] = {
30, 35, 15, 5, 10, 20}; void MatrixChain(int a[N], int n) {
for(int i=1; i<=n; i++) m[i][i] = 0; for(int r=2; r<=n; r++) {
for(int i=1; i<= n-r+1; i++) {
int j = i+r-1; m[i][j] = m[i+1][j] + a[i-1]*a[i]*a[j]; s[i][j] = i; for(int k=i; k<=j-1; k++) {
int t = m[i][k] + m[k+1][j] + a[i-1]*a[k]*a[j]; if(t < m[i][j]) {
m[i][j] = t; s[i][j] = k; } } } } } int main() {
MatrixChain(a, 6); cout << "The number of least multiplication operations:" << endl; cout << m[1][5] << endl; cout << "Position of the last operation:" << endl; cout << s[1][5] << endl; cout << "array s:" << endl; for(int i=1; i<=5; i++) {
for(int j=1; j<=5; j++) {
cout << s[i][j] << ' '; } cout << endl; } return 0; } /* 5 30 35 15 5 10 20 */
讯享网
💛 输出样例
讯享网The number of least multiplication operations: 11875 Position of the last operation: 3 array s: 0 1 1 3 3 0 0 2 3 3 0 0 0 3 3 0 0 0 0 4 0 0 0 0 0
💖 Java版:Main.java
import java.util.Scanner; public class Main {
static int n;// 矩阵数组的长度看,矩阵个数为 n-1 static int[] p;// 矩阵数组,第 i个矩阵的行列数为(p[i-1],p[i])(i>0) static int[][] m;// m[i][j] 表示 矩阵 i ~j 链乘的最优解(乘法次数) static int[][] s;// 存放最优解的分割位置,用于回溯最优解 public static void matrixChain() {
for (int len = 2; len < n; len++)// 区间的长度 len {
for (int l = 1; l < n - len + 1; l++)// 当前闭区间左端点 l {
int r = l + len - 1;// 闭区间右端点 r // 先以 l 进行划分 // m[l][r] = m[l + 1][r] + p[l - 1] * p[l] * p[r]; // 求出矩阵 l到j的连乘 m[l][r] = Integer.MAX_VALUE;// 初始化为无穷大 s[l][r] = l; // 记录划分位置 for (int k = l; k < r; k++)// 区间分割点 {
// 计算当前分割点的乘法次数 // m[l][k]:表示矩阵链从第l个矩阵到第k个矩阵的最小乘法次数。 // m[k + 1][r]:表示矩阵链从第k+1个矩阵到第r个矩阵的最小乘法次数。 int t = m[l][k] + m[k + 1][r] + p[l - 1] * p[k] * p[r]; if (t < m[l][r])// 如果找到更小的乘法次数,则更新最优解 {
m[l][r] = t; s[l][r] = k; } } } } } / * 输出 A[i:j] 的最优计算次序 * * @param i、j: 连乘矩阵下标 * @param s: 存放分割位置下标的数组 / public static void traceback(int i, int j, int[][] s) {
// 输出A[i:j] 的最优计算次序 if (i == j) {
// 递归出口 System.out.print("A" + i); return; } else {
System.out.print("("); // 递归输出左边 traceback(i, s[i][j], s); // 递归输出右边 traceback(s[i][j] + 1, j, s); System.out.print(")"); } } public static void main(String[] args) {
Scanner sc = new Scanner(System.in); n = sc.nextInt();// 输入 n 个矩阵 n++;// 数组要开大一位 p = new int[n]; for (int i = 0; i < n; i++) p[i] = sc.nextInt(); m = new int[n][n]; s = new int[n][n]; matrixChain(); System.out.println("最优值为: " + m[1][n - 1]); System.out.println("最后一次的运算位置:" + s[1][n - 1]); traceback(1, n - 1, s); } }
💛 输入样例
讯享网5 30 35 15 5 10 20
💛 输出样例
最优值为: 11875 最后一次的运算位置:3 ((A1(A2A3))(A4A5))

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容,请联系我们,一经查实,本站将立刻删除。
如需转载请保留出处:https://51itzy.com/kjqy/77222.html