矩阵连乘问题.cpp

来自「算法设计分析的一些例子程序....凑字数..凑字数」· C++ 代码 · 共 37 行

#include <iostream>
using namespace std;

void mchain(int n ,int *p,int m[6][6])
{ 
	for(int i=0;i<n;i++)
		m[i][i]=0;
	for(int r=1;r<n;r++)
    for(int i=0;i<n-r;i++)
	{
		int j=i+r;
		m[i][j]=m[i+1][j]+p[i]*p[i+1]*p[j+1];
		for(int k=i+1;k<j;k++)
		{
			int t=m[i][k]+m[k+1][j]+p[i]*p[k+1]*p[j+1];
			if(t<m[i][j])
			m[i][j]=t;
		}
	}
}
void main()
{ 
	int n=6;
	int p[7]={30,35,15,5,10,20,25};
	int m[6][6]={0};
	mchain(n,p,m);
	cout<<"最少需要乘法次数为："<<m[0][n-1]<<endl;

}