matrix_mult.cpp

矩阵链的相乘的源代码

#pragma warning(disable:4786)
#include <vector> 
#include <algorithm>
#include <iostream.h>
using namespace std; 

#define N 5
//int x[N + 1] = {2,8,7,3,5,6};
int x[N + 1] = {3,2,4,5,6,1};
int m[N][N];
int flag[N][N];

int init (int m[N][N], int n);
int run ();
int show_x (int x[N + 1], int n)
{
	int i;
	for (i = 0; i < n + 1; i++)
	{
		printf ("%d ", x[i]);
	}
	printf ("\n");

	return 0;
}
int show_flag (int m[N][N], int n)
{
	printf ("\n");
	int i;
	int j;
	for (i = 0; i < n; i++)
	{
		for (j = 0; j < n; j++)
		{
			printf ("%3d ", m[i][j]);
		}
		printf ("\n");
	}
	
	return 0;
}

int main (void)
{
	show_x (x, N);
	init (m, N);
	run ();
	show_flag (m, N);
	show_flag (flag, N);

	return 0;
}
int run ()
{
	int i;
	int j;
	int k;
	int r;
	int chart;
	int min;
	int bound;
	for (k = 0; k < N; k++)
	{
		for (i = 1; i < N - k + 1; i++)
		{
			j = i + k;
			printf ("m[%d][%d] ", i, j);
			if (i == j)
			{
				m [i - 1][j - 1] = 0;
				continue;
			}
			chart = m[i - 1][i - 1] + m[i + 1 - 1][j - 1] \
				     + x[i - 1] * x[i + 1 - 1] * x[j];
			min = chart;
			bound = i;
			m[i - 1][ j - 1] = chart;
			for (r = i + 1; r < j; r++)
			{
				//printf ("m[%d][%d]", i, r);
				//printf ("m[%d][%d]  ", r + 1,j);
				chart = m[i - 1][r - 1] + m[r + 1 - 1][j - 1] \
					     + x[i - 1] * x[r + 1 - 1] * x[j];
				if (chart < min)
				{
					min = chart;
					bound = r;
					m[i - 1][ j - 1] = chart;
				}
			}
			flag[i - 1][j - 1] = bound;
			printf ("bound = %d \n", bound);
		}
		printf ("\n");
	}
	
	return 0;
}
int init (int m[N][N], int n)
{
	int i;
	int j;
	for (i = 0; i < n; i++)
	{
		m[i][i] = 0;
	}
	for (i = 0; i < n; i++)
	{
		for (j = 0; j < n; j++)
		{
			m[i][j] = 0;
		}
		printf ("\n");
	}
	
	return 0;
}