關于算法導論上面的矩陣鏈乘問題,雖然書上說的很清楚,但是關于填寫的規則,三重循環的下標的起點和終點
確實需要格外注意。

有三種填充方式,對角線,從下往上,從左往右,選擇一種能順利描述的就好
#include<fstream> #include<iostream> using namespace std; const int MAX_INT = 0x7fffffff; void print(int s[][7], int i, int j) { if (i == j) cout << "A" << i; else { cout << "("; print(s, i, s[i][j]); print(s, s[i][j] + 1, j); cout << ")"; } } int main() { int p[7] = {30,35,15,5,10,20,25 }; int m[8][8],s[7][7]; int x,i,j,l,k,q; for (x=1; x <7; x++) m[x][x] = 0; for ( l = 2; l <= 6; l++) { for ( i = 1; i <= 7-l; i++) { j=i+l-1; m[i][j] = MAX_INT; int q; // cout << m[i][j]; for ( k = i; k <j; k++) { q = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j]; if (q < m[i][j]) { m[i][j] = q; s[i][j] = k; } } } } print(s, 1, 6); system("pause"); return 0; }
浙公網安備 33010602011771號