矩阵链相乘问题-白红宇

矩阵链相乘问题

阅读量：3962 次

发布时间：2019-05-24

本文共 912 字，大约阅读时间需要 3 分钟。

矩阵的乘法定义如下：设A是m×p的矩阵，B是p×n的矩阵，则A与B的乘积为m×n的矩阵，记作C=AB，其中，矩阵C中的第i行第j列元素cij可以表示为：

当多个矩阵相乘时，采用不同的计算顺序所需的乘法次数不相同。例如，A是50×10的矩阵，B是10×20的矩阵，C是20×5的矩阵，计算ABC有两种方式：(AB)C和A(BC)，前一种需要15000次乘法计算，后一种则只需3500次。
设A1,A2,…,An为矩阵序列，Ai是阶为Pi−1∗Pi的矩阵(1≤i≤n)。试确定矩阵的乘法顺序，使得计算A1A2…An过程中元素相乘的总次数最少。
输入格式:
每个输入文件为一个测试用例，每个测试用例的第一行给出一个正整数n(1≤n≤100)，表示一共有n个矩阵A1,A2,…,An，第二行给出n+1个整数P0 ,P1…Pn，以空格分隔，其中1≤Pi≤100(0≤i≤n)，第i个矩阵Ai是阶为Pi−1∗Pi的矩阵。
输出格式:
获得上述矩阵的乘积，所需的最少乘法次数。
输入样例:
在这里给出一组输入。例如：

530 35 15 5 10 20

输出样例:

在这里给出相应的输出。例如：

#include 
   
    using namespace std;const int MAX = 1005;int p[MAX];int m[MAX][MAX];int n;void  matrix(){
       int i,j,r,k;    memset(m,0,sizeof(m));    for(r = 2; r<=n; r++)    {
           for(i = 1; i<=n-r+1; i++)        {
               j = i+r-1;            m[i][j] = m[i+1][j]+p[i-1]*p[i]*p[j];            for(k = i+1; k
    
     >n;    for(int i=0; i
     
      >p[i];    matrix();    cout<
      
       <

转载地址：http://vyezi.baihongyu.com/

你可能感兴趣的文章