C 언어 매트릭스 연결(동적 기획)상세 설명

동적 계획 법
제목 설명:n 개의 행렬{A1,A2...............................................................................
매트릭스 체인 ABCD 를 예 로 들 면
매트릭스 체인 길이 증가 에 따라 최 적 화 된 값 을 계산 합 니 다.
매트릭스 체인 길이 가 1 일 때 각각 매트릭스 체인 A,B,C,D 의 최 우수 치 를 계산한다.
매트릭스 체인 길이 가 2 일 때 각각 매트릭스 체인 AB,BC,CD 의 최 우수 치 를 계산한다.
매트릭스 체인 길이 가 3 일 때 각각 매트릭스 체인 ABC,BCD 의 최 우수 치 를 계산한다.
매트릭스 체인 길이 가 4 일 때 매트릭스 체인 ABCD 의 최 적 화 된 값 을 계산 합 니 다.
동 귀 방정식:

분석:
k 매트릭스 체인 이 끊 어 진 위치
d 배열 저장 매트릭스 체인 컴 퓨 팅 의 최 적 화 된 값,d[i][j]는 i 번 째 행렬 을 비롯 하여 j 번 째 행렬 을 마지막 으로 하 는 매트릭스 체인 의 최 적 화 된 값 입 니 다.i>0
m 배열 에 행렬 체인 의 행렬 정 보 를 저장 합 니 다.m[i-1]과 m[i]는 각각 i 번 째 행렬 의 줄 과 열(i=1,2,3...)입 니 다.
c 언어 구현 코드:

#include <stdio.h>
#define N 20 
void MatrixChain(int p[N],int n,int m[N][N],int s[N][N]){ 
  int i,j,t,k;   
  int r;             //            
  for(i=1;i<=n;i++){ 
    m[i][i]=0;         //        ，      0  
  }   
  //               
  for(r=2;r<=n;r++){ 
    //            
    for(i=1;i<=n-r+1;i++){ 
      //          
      j=i+r-1; 
      //    i   j          
      m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j]; 
      //             
      s[i][j]=i; 
      //       ，          ，   m   ，       s     
      for(k=i+1;k<j;k++){ 
        t=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j]; 
        if(t<m[i][j]){ 
          m[i][j]=t; 
          s[i][j]=k; 
        } 
      } 
    } 
  }  
} 
 
int main(void){ 
  int n,n1,m1,i,j=2; 
  int p[N]={0};          //            
  int m[N][N]={0};        //               
  int s[N][N]={0};        //                
  printf("       :
"); 
  scanf("%d",&n); 
  for(i=1;i<=n;i++){ 
    printf("    %d       (n1*m1   ):",i); 
    scanf("%d*%d",&n1,&m1); 
    if(i==1){ 
      p[0]=n1; 
      p[1]=m1; 
    } 
    else{ 
      p[j++]=m1; 
    } 
  } 
  printf("
       :
"); 
  for(i=0;i<=n;i++){ 
    printf("%d ",p[i]); 
  } 
  printf("
"); 
  MatrixChain(p,n,m,s); 
  printf("
            :
"); 
  for(i=1;i<=n;i++){ 
    for(j=1;j<=n;j++){ 
      printf("%d  ",m[i][j]); 
    } 
    printf("
"); 
  } 
  printf("
            :
"); 
  for(i=1;i<=n;i++){ 
    for(j=1;j<=n;j++){ 
      printf("%d ",s[i][j]); 
    } 
    printf("
"); 
  } 
  printf("         :%d
",m[1][n]); 
  return 0; 
} 

읽 어 주 셔 서 감사합니다. 여러분 에 게 도움 이 되 기 를 바 랍 니 다.본 사이트 에 대한 여러분 의 지지 에 감 사 드 립 니 다!