main.cpp

《算法分析与设计》中的 “矩阵连乘程序”给定n个矩阵｛A1,A2,…,An｝

#include <iostream.h>
#include <iomanip.h>

void MatrixChain(int *p, int n, int *m, int *s)
{
	for(int i = 0; i < n; i++)
		*(m + i * n + i) = 0;
	
	for(int r = 1; r < n; r++)
		for(i = 0; i < n - r + 1; i++)
		{
			int j = i + r;
			*(m + i * n + j) = *(m + (i + 1) * n + j) + p[i] * p[i + 1] * p[j + 1];
			*(s + i * n + j) = i;
			for(int k = i + 1; k < j; k++)
			{
				int t = *(m + i * n + k) + *(m + (k + 1) * n +j) + p[i] * p[k + 1] * p[j + 1];
				if(t < *(m + i * n + j))
				{
					*(m + i * n + j) = t;
					*(s + i * n + j) = k;
				}
			}
		}
}

void Traceback(int i, int j, int *s, int n)
{
	if(i == j) return;
	Traceback(i, *(s + i * n + j),s, n);
	Traceback(*(s + i * n + j) + 1, j, s, n);
	cout << "Multiply A" << i + 1 << "," << *(s + i * n + j) + 1;
	cout << " and A" << *(s + i * n + j) + 2 << "," << j + 1 <<endl;
}

void main()
{
	cout << "********************************************************" << endl;
	cout << "               the Solution of Matrix Chain             " << endl;
	cout << "********************************************************" << endl;
	cout << endl << "You should make sure the numbers of matrix at first." << endl;
	cout << "Please input the numbers of matrix:";
	int n = 0;
	int i = 0, j = 0;
	cin >> n;
	int *m = new int[n * n];
	int *p = new int[n + 1];
	int *s = new int[n * n];
	for(i = 0; i < n * n; i++)
	{
		m[i] = 0;
		s[i] = 0;
	}

	cout << endl << "Then,you should make sure the demensions of each matrix." <<endl;

	for(i = 0; i <=  n; i++)
		cin >> p[i];
	
	MatrixChain(p, n, m, s);
	cout << endl << "the results of matrix combination is: " << endl;
	if(0 == n - 1)
		cout << "Only one matrix don't need to combine." << endl;
	else
		Traceback(0, n - 1, s, n);
	cout << "the optimization frequency of calculation is:" << setw(8) 
		<< *(m + 0 * n + n - 1) << endl;
}