matrix.cpp

距阵链乘问题: 找出矩阵链乘A(35*40) A(40*20) A(20*10) A(10*15)的最佳相乘次序。 算法来自:计算机算法导引

// Metrix.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream.h>

#define METRIX_NUM 4

struct Metrix 
{
	int row;
	int list;
};
Metrix A[METRIX_NUM+1];

struct Count   //
{
	int MinCount;
	int k;     //
};
Count m[METRIX_NUM+1][METRIX_NUM+1];

void SetCount(int i,int j)
{
	static int Min,Temp,k;
	Min=0xffff;
	for (k=i;k<j;k++){
		Temp=m[i][k].MinCount+m[k+1][j].MinCount+A[i].row*A[k+1].row*A[j].list;
		if (Min>Temp) {Min=Temp; m[i][j].k=k;}
	}
	m[i][j].MinCount =Min;
}

int main(int argc, char* argv[])
{
	int i,j;
	A[1].row=35;
	A[1].list=40;
	A[2].row=40;
	A[2].list=20;
	A[3].row=20;
	A[3].list=10;
	A[4].row=10;
	A[4].list=15;
	for(i=1;i<=METRIX_NUM;i++) m[i][i].MinCount=0; //
	for (i=1;i<METRIX_NUM;i++)
		for (j=1;j+i<=METRIX_NUM;j++){
			SetCount(j,j+i);
		}
    // 
    cout<<"m[1][4].MinCount ="<<m[1][4].MinCount<<endl;
	cout<<"m[1][4].k ="<<m[1][4].k<<endl;
    cout<<"m[1][3].MinCount ="<<m[1][3].MinCount<<endl;
	cout<<"m[1][3].k ="<<m[1][3].k<<endl;
	cout<<"m[2][3].MinCount ="<<m[2][3].MinCount<<endl;
	return 0;
}