умножение цепи mtrix печатать последовательность матриц

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 должна возвращать число, в соответствии с этим 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 functi на

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] ... 
}