matrixmult.cpp

用分治法解矩阵乘法(C++实现)

#include <iostream.h>

// Step 1: Initial matrix from A1 to An.
const int n = 6;
int p[n+1] = {50, 10, 3, 12, 5, 50, 6};

// Step 2: Calculate m[i][j] and s[i][j].
int m[n+1][n+1], s[n+1][n+1];

void MatrixChain(int * p, 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] + 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){
	if (i == j){
		cout << "A" << i;
		return;
	}
	cout << "(";
	Traceback(i, s[i][j]);
	Traceback(s[i][j]+1, j);
	cout << ")";
}

void main(){
	MatrixChain(p, n);
	// Step 3: Traceback.
	cout << "若已知 " << n << " 个矩阵如下所示：" << endl;
	for (int i = 1; i <= n; i++)
		cout << "　　A" << i << ": " << p[i-1] << " * " << p[i] << endl;
	cout << "则计算连乘积的添括号过程：" << endl << "　　";
	Traceback(1, n);
	cout << endl << "最少乘法数为：" << m[1][n] << endl;
}