Question

矩阵链相乘问题 来个C#写的或C/C++写的

1. 编写程序使用动态规划算法MATCHAIN求解n个矩阵连乘所需最找数量乘法次数，并用实际数据对算法进行测试。
2. 要求对算法MATCHAIN加以改进，不仅能够输出数量乘法次数，还要能输出最佳乘法方案，如(M1M2)((M3M4)M5)。
1. 编写函数MATCHAIN求解矩阵链相乘问题，函数头为：
int MATCHAIN(int r[], int n)
r为数组名，r[i]和r[j]分别表示矩阵Mi的行数和列数，n表示连乘矩阵的个数。
2. 在main函数中使用给定数组{4,5,3,6,4,5}测试MATCHAIN函数，效果如下图所示。

其算法伪代码如下：
1. for i←1 to n
2. C[i,j]←0
3. end for
4. for d←1 to n-1
5. for i←1 to n-d
6. j←i+d
7. C[i,j]←∞
8. for k←i+1 to j
9. C[i,j]←min{C[i,j],C[i,k-1]+C[k,j]+r[i]r[k]r[j+1]}
10. end for
11. end for
12.end for
13.return C[1,n]

Answer 1

#include<stdio.h>
#include<stdlib.h>
#define MAXN 1000000
void Matrix_Chain_Order(int * p, int * s, int N)
{
       int n = N - 1;
       int m[N][N];
       for(int i = 1; i <= n; i++)
       {
             m[i][i] = 0;          
       }   
       for(int l = 2; l <= n; l++) /*lÊÇÁ´µÄ³¤¶È*/
       {
               for(int i = 1; i <= n - l + 1; i++)
               {
                    int j = i + l - 1;
                    m[i][j] = MAXN;       
                    int q; 
                    for(int k = i; k <= j - 1; k++)
                    {
                         q = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];
                         if(q < m[i][j])
                         {
                              m[i][j] = q;
                              *(s + i * N + j) = k;     
                         }           
                    }     
               }             
       }      
}

void Print_Optimal_Parens(int * s, int i, int j, int N)
{
     if(i == j)
     {
          printf("A%d",i);     
     }     
     else
     {
         printf("(");
         Print_Optimal_Parens((int *)s, i, *(s + i * N + j), N);
         Print_Optimal_Parens((int *)s,  *(s + i * N + j)+1, j, N);
         printf(")");    
     }
}

int main()
{
    int P[7] = {30,35,15,5,10,20,25};
    int S[7][7];
    Matrix_Chain_Order(P,(int *)S,7);
    Print_Optimal_Parens((int *)S,1,6,7);
    system("pause");
    return 0;    
}

这是我以前实现矩阵链相乘的算法，不符合你最终的显示，你稍微改一下就好