행렬 곱셈의 최우선 순서
동태적인 기획으로 이 문제를 풀다.
/*
* =====================================================================================
*
* Filename: MatrixMul.cpp
*
* Description:
*
* Version: 1.0
* Created: 2011 12 01 10 43 13
* Revision: none
* Compiler: gcc
*
* Author: MaZheng (blog.csdn.net/mazheng1989), [email protected]
* Company: Dalian University Of Technology
*
* =====================================================================================
*/
#include<stdio.h>
const int n=4;
int Matrix[n][2]={20,2,2,15,15,40,40,4};
int cost[n][n];
int root[n][n];
int Proc(int i,int r,int j)
{
return Matrix[i][0]*Matrix[r][1]*Matrix[j][1];
}
int pri(int i,int r,int j)
{
if(i==r&&r==j)
return -1;
pri(i,root[i][r],r);
pri(r+1,root[r+1][j],j);
printf(" %d ",root[i][j]+1);
}
int main()
{
for(int i=n-1;i>=0;i--)
{
for(int j=i;j<=n-1;j++)
{
if(j==i)
{
cost[i][j]=0;
root[i][j]=i;
continue;
}
for(int r=i;r<=j-1;r++)
{
int temp=cost[i][r]+cost[r+1][j]+Proc(i,r,j);
if(cost[i][j]==0)
{
cost[i][j]=temp;
root[i][j]=r;
}
else if(cost[i][j]!=0&&cost[i][j]>=temp)
{
cost[i][j]=temp;
root[i][j]=r;
}
}
// printf("%d %d %d %d
",i+1,j+1,cost[i][j],root[i][j]+1);
}
}
printf("least multiply times = %d
",cost[0][n-1]);
printf("compute sequece is:
");
pri(0,root[0][n-1],n-1);
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.