matrix.cpp

矩阵连乘问题 对多个矩阵连乘时 的消耗进行分析

#include "stdio.h"
#include "iostream.h"
#define N 4

//矩阵处理
static int sub[N+1];
static  int Data[N+1][N+1];

void DataMatrix(){
     int i,j,k;
     int T;

    
    //矩阵的运算
    for(i=1;i<N;i++){
        for(j=1;j<N&&(j+i<=N);j++){
            Data[j][j+i]=65535;
            for(k=0;k<i;k++){
                T=Data[j][j+k]+Data[j+k+1][j+1]+sub[j-1]*sub[j+k]*sub[j+i];
                if(T<Data[j][j+i]){
                    Data[j][j+i]=T;
                    Data[j+i][j]=j+k;
                }
            }
        }
    }
 }
 
 void Print( int i, int j){
     int T=1;
    if(i==j){printf("M %d ",i);}
    else if(i+1==j){
        printf("(M%d M%d)",i,j);
    }
    else{
        T=Data[j][i];
        printf("(");
        Print(i,T);
        Print(T+1,j);
        printf(")");
    }
  }
  
  void main(){
    int i,j;
     sub[0]=10;
     sub[1]=30;
     sub[2]=70;
     sub[3]=1;
     sub[4]=200;

    //赋初值为0
    for(i=0;i<N+1;i++){
        for(j=0;j<N+1;j++){
        Data[i][j]=0;
        }
    }

        DataMatrix();
        Print(1,N);
        printf("\n");
  }