矩阵链乘法打印矩阵序列

Question

我用c++编写了动态规划中矩阵链乘法的代码。打印正确的矩阵括号的递归调用中存在错误。我正在从文本文件中获取输入并在文本文件上提供输出。请帮助..

#include <iostream>
#include <fstream>
#include <limits.h>
using namespace std;
int * MatrixChainOrder(int p[], int n)
{
    static   int m[100][100];
    static int s[100][100];
    int j, q;
    int min = INT_MAX;
    for (int i = 1; i <= n; i++)
        m[i][i] = 0;

    for (int L = 2; L <= n; L++) {
        for (int i = 1; i <= n - L + 1; i++) {
            j = i + L - 1;
            m[i][j] = min;
            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;
                }
            }
        }
    }
    return (*s);
}

void Print(int *s, int i, int j)
{
    ofstream outfile("output.text");

    if (i == j)
    {
        outfile << "a1";
    }
    else
        outfile << "(";
    {
        Print(*s, i, s[i][j]);
        Print(*s, s[i][j] + 1, j);
        outfile << ")";
    }
    outfile.close();
}

int main()
{
    int arr[100];
    int num, i = 0;
    ifstream infile("input.text");
    while (infile)
    {
        infile >> num;
        arr[i] = num;
        i++;
    }
    i = i - 1;
    infile.close();
    Print(MatrixChainOrder(arr, i - 1), 0, i - 1);
    return 0;
}

Answer 1

在 C++ 中，最好对数组使用 std::vector。除此之外，您不能像那样混合使用指针和数组，因为编译器会丢失数组大小。

例如这不起作用：

int x[10][20];
void foo(int *ptr)
{
    //the numbers 10 and 20 have not been passed through
}

不过你可以改成

int x[10][20];
void foo(int arr[10][20])
{
    //the numbers 10 and 20 are available
}

MatrixChainOrder 应该是 return 一个数字，根据这个 link

int MatrixChainOrder(int s[100][100], int p[], int n)
{
    int m[100][100];
    for (int i = 0; i < 100; i++) m[i][i] = 0;
    for (int i = 0; i < 100; i++) s[i][i] = 0;
    int q = 0;
    for (int L = 2; L <= n; L++) {
        for (int i = 1; i <= n - L + 1; i++) {
            int j = i + L - 1;
            m[i][j] = INT_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;
                }
            }
        }
    }
    return q;
}

int main()
{
    int arr[] = { 40, 20, 30, 10, 30 };
    int array_size = sizeof(arr) / sizeof(int);
    int n = array_size - 1;
    int s[100][100];
    int minimum = MatrixChainOrder(s, arr, n);
    printf("{ 40, 20, 30, 10, 30 } should result in 26000 : %d\n", minimum);
    return 0;
}

同样你可以改变你的Print函数

void Print(int s[100][100], int i, int j)
{
    if (i < 0 || i >= 100 || j < 0 || j >= 100)
    {
        cout << "array bound error\n";
    }
    //safely access s[i][j] ...
}

矩阵链乘法打印矩阵序列

mtrix chain multiplication print the sequence of the mattrices

c++

matrix

multiplication

chain