程序.txt

用C++实现矩阵连乘问题

1. 递归方法
int C(int i, int j)
{ //返回c(i,j) 且计算k(i,j) = kay[i][j]
	if (i==j) return 0; //一个矩阵的情形
	if (i == j-1)
	{ //两个矩阵的情形
		kay[i][i+1]=i;
		return r[i]*r[i+1]*r[i+2];
	}
	//多于两个矩阵的情形
	//设u为k = i 时的最小值
	int u=C(i,i)+C(i+1,j)+r[i]*r[i+1]*r[j+1];
	kay[i][j]=i;
	//计算其余的最小值并更新u
	for (int k=i+1;k<j;k++)
	{
		int t=C(i,k)+C(k+1,j)+r[i]*r[k+1]*r[j+1];
		if(t<u)
		{  //小于最小值的情形
			u=t;
			kay[i][j]=k;
		}
		return u;
	}
}

3. 迭代方法
void MatrixChain(int r[],int q,int **c,int **kay)
{ // 为所有的Mij 计算耗费和k a y
  // 初始化c[i][i], c[i][i+1]和kay[i][i+1]
	for(int i=1;i<q;i++)
	{
		c[i][i]=0;
		c[i][i+1]=r[i]*r[i+1]*r[i+2];
		kay[i][i+1]=i;
	}
	c[q][q]=0;
	//计算余下的c和kay
	for(int s=2;s<q;s++)
		for(int i=1;i<=q-s;i++)
		{
			// k=i时的最小项
			c[i][i+s]=c[i][i]+c[i+1][i+s]+r[i]*r[i+1]*r[i+s+1];
			kay[i][i+s]=i;
			// 余下的最小项
			for(int k=i+1;k<i+s;k++)
			{
				int t=c[i][k]+c[k+1][i+s]+r[i]*r[k+1]*r[i+s+1];
				if(t<c[i][i+s])
				{ // 更小的最小项
					c[i][i+s]=t;
					kay[i][i+s]=k;
				}
			}
		}
}