矩阵连乘问题
void MatrixChain(int* p, int n, int** m, int** s) {
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] + p[i - 1] * p[i] * p[j];
s[i][j] = i;
for (int k = i + 1; k < j; ++k) {
int 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;
}
}
}
}
}
void Traceback(int i, int j, int **s) {
if (i == j)
return;
Traceback(i, s[i][j], s);
Traceback(s[i][j] + 1, j, s);
cout << "Multiply A" << i << "," << s[i][j];
cout << "and A" << (s[i][j] + 1) << "," << j << endl;
}
最后更新:
2024年1月2日 21:37:12
创建日期: 2024年1月2日 16:56:10
创建日期: 2024年1月2日 16:56:10