0%

矩阵连乘

问题描述

实现矩阵连乘算法。输入n个矩阵的维度(n+1个数, n>2),输出矩阵连乘的最小数乘次数以及连乘次序,即矩阵加括号的方式,如: (A1((A2A3)A4))。

提交格式:
实现void solve(int n,int p[],int out[])函数。

参数n为矩阵个数,p为关于矩阵维数的n+1个数,矩阵Ai的维数为(p[i-1],p[i]),out[0]为最小数乘次数MOD1000000007,out[i]为输出的连乘次序(i>0)。2<n<=500,2<p[i]<=500。

输出连乘次序时,请将(替换为-1、)替换为-2,矩阵Ai替换为i,输出到out数组中。
请不要printf输出任何内容。

输入样例:

1
n=5,p={10,5,2,8,6,3}

输出样例:

1
out={292,-1,-1,1,2,-2,-1,-1,3,4,-2,5,-2,-2}
核心思路
  1. 最优子结构分析,建立递归关系,得到递归表达式;
  2. 依据其递归式以自底向上的方式进行迭代,得到m矩阵和s矩阵;
  3. 通过s矩阵加括号;
  4. 构造主函数进行调试。
实现要点
  1. 关键在于构造递推表达式,这也是动态规划的难点所在;
  2. 由于数据可能比较大,数据类型选择long long;
  3. 虽然题目是加数字,但和加括号一样,借助通过递归实现。
code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include<stdio.h>
#include <stdlib.h>

long long m[500][500], s[500][500];
long long number;
void traceback(long long i, long long j, int* out);
void solve(int n, int p[], int out[])
{
for (long long i = 1; i <= n; i++) m[i][i] = 0;
for (long long r = 1; r <= n - 1; r++) //r是i和j的间隔宽度
for (long long i = 1; i <= n - r; i++) //随着间隔宽度r的增长,i递减,直到i为1
{
long long j = i + r;
m[i][j] = m[i + 1][j] + p[i - 1] * p[i] * p[j]; // 在i的位置断链,分解为m[i][i]和m[i+1][j]。
s[i][j] = i;
for (long long k = i + 1; k < j; k++) // 计算最小的m[i][j]
{
long long t = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];
if (t < m[i][j])
{
m[i][j] = t;
s[i][j] = k;
} //k是i和j之间的最佳断链位置
}
}
out[0] = m[1][n]% 1000000007;
for (long long i = 1; i <= n; i++)
{
out[i] = i;
}
number = n;
traceback(1,n,out);
}

void traceback(long long i, long long j, int* out)
{
long long k;
if (i == j) return ;
else {
for (k = number; out[k + 1] != i; k--)
{
out[k + 1] = out[k];
}
out[k+1] = -1;
number++;
for (k = number; out[k] != j; k--)
{
out[k + 1] = out[k];
}
out[k + 1] = -2;
number++;
traceback(i, s[i][j], out);
traceback(s[i][j] + 1, j, out);
}
}

int main()
{
int n=5;
int p[6] = { 10,5,2,8,6,3 };
int out[1500] = {0};
solve(n, p, out);
printf("out=");
for (int i = 0; i <= number; i++)
{
printf("%d,", out[i]);
}
system("pause");
return 0;
}
-------------本文结束感谢您的阅读-------------

欢迎关注我的其它发布渠道