C++ Matrix-Chain-Order/无法获得所需的输出

Question

#include <string>
#include <iostream>
#include <vector>
#include <iomanip>

using namespace std;

int main()
{
     double m[7][7]; //2d dimension array m
     int s[7][7]; //2d dimension array s
     int p[7] = {30,35,15,5,10,20,25}; //array p to store numbers

     int j;
     double q;

     int n = 5;

    for(int i = 1; i != n; ++i) //initialize m[1][1], m[2][2], ... to zero
        m[i][i] = 0;
    for(int l = 2; l != n; ++l) // performing the algorithm 
    {
        for(int i = 1; i != (n-l+1); ++i)
        {
            j = i + (l-1);
            m[i][j] = numeric_limits<double>::max(); // find the max
            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][j] = k;
                }
            }
        }
    }

测试如下:

    for(int i = 0; i != 4; ++i)
    {
        for(int j = 0; j != 4; ++j)
        {
            // print the m[i][j] to test the output
            cout << "m[" << i << "][" << j << "] " << " = " << m[i][j] << endl;;
        }
    }
}

我正在执行矩阵链顺序，输出(我的测试用例)在执行算法后应该有值。但它就像图片一样都是零。例如，m 1 [2] 应该是 30*35*15 = 15750。

Answer 1

C 数组的索引从 0 开始，而不是 1。

改变

for(int i = 1; i != n; ++i)
    m[i][i] = 0;

到

for(int i = 0; i != n; ++i)
    m[i][i] = 0;

改变

for(int l = 2; l != n; ++l)
{
    for(int i = 1; i != (n-l+1); ++i)

到

for(int l = 1; l != n; ++l)
// Start from 1 instead of 2
{
    for(int i = 0; i != (n-l+1); ++i)
    // Start from 0 instead of 1

更新

不清楚你的算法是什么但是线

for(int k = i; k != (j-1); ++k)

好像有问题。当你进入循环时，你有:

l = 1
i = 0
j = 0

您将 k 初始化为 i，即 0。因此，条件 k != (j-1) 永远不会为真，循环会一直运行直到达到某种限制——很可能会造成 float 的溢出/下溢。

改变那一行:

for(int k = i; k < (j-1); ++k)

会让你的程序运行，但我不知道这是否是你程序的正确逻辑。