欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

DP---矩阵连乘

程序员文章站 2022-06-23 15:40:06
动态规划法是解决问题的一种方法。它不规定为了得到结果需如何将问题划分为子问题的固定方法,而是按不同输入给出问题的具体实例的子问题划分方法,然后再进行运算、解答问题。   矩阵连乘问题的主要...

动态规划法是解决问题的一种方法。它不规定为了得到结果需如何将问题划分为子问题的固定方法,而是按不同输入给出问题的具体实例的子问题划分方法,然后再进行运算、解答问题。
 
矩阵连乘问题的主要思想如下:
1)设置大小为连乘个数的方阵
2)主对角线上方各元素di,j(i<j)表示矩阵mi连乘到mj的最小工作量
3)下方元素di,j(i>j)记录获得该最小工作量矩阵分组的第一组的最后一个矩阵的序列号
 最后通过下方元素可知最终结果的分组方式。
 
算法描述:
1)读入n, 即矩阵的个数;
2)读入n+1个数, 即n个矩阵的行数和列数, 将它们存入数组r中;
3)将d主对角线元素置为零;
4)求出d矩阵的其它元素的数值;
5)给出n个矩阵的结合方式.
 
code:

[html] 
#define maxint 1000 
int d[10][10],r[11]; 
void print(int i, int j) 

    int k; 
    if(i==j) printf("m%d",i); 
    else if (i+1==j) printf("m%d,m%d",i,j); 
    else 
    { 
        k =d[j][i]; 
        printf(" ("); 
        print(i,k); 
        print(k+1, j); 
        printf(")"); 
    } 

 
dm(int n) 

    int i,j,k,t; 
    for(i=1;i<n-1;i++) 
        for(j=1;j<n-1;j++) 
        { 
            d[j][j+1]=maxint; 
            for(k=0;k<i-1;k++) 
            { 
                t=d[j][j+k]+d[j+k+1][j+1]+r[j-1]*r[j+k]*r[j+1]; 
                if(t<d[j][j+1]) 
                { 
                    d[j][j+1]=t; 
                    d[j][j+1]=j+k; 
                } 
            } 
        } 

 
main() 

    int flag=1,n,i; 
    char c; 
    printf("e------exit     i--------continue\n"); 
    while(flag==1) 
    { 
        scanf("%c",&c); 
        switch(c) 
        { 
        case 'i':   flag=1; 
            printf("please input the data:\n"); 
            printf("the value of matrix: n=");  
            scanf("%d",&n); 
            for(i=0;i<n;i++) 
            { 
                printf("r[i]=",i); 
                scanf("%d",&r[i]); 
            } 
            for(i=1;i<n;i++)  d[i][i]=0; 
            dm(n); 
            print(1,n+1); 
            break; 
        case 'e':  flag=0;break; 
        } 
    } 


作者:yyf573462811