Para ejecutar(solo para los casos de los ejercicios del cuaderno, aunque funciona para otros

datos)

1ero COPIAR TODOS LOS ARCHIVOS AL ESCRITORIO

Para ejecutar el algoritmo de matrix_chain_mult()

Abrir el CMD y digitar los comandos siguientes:

#include <bits/stdc++.h>
#define INF 999999999
using namespace std;
int** Init(int n)
{
int** M = new int*[n];
for (int i = 0; i < n; ++i)
M[i] = new int[n];
return M;
}
void Ver(int**A, int Length_A)
{
for (int i = 0; i < Length_A; ++i)
{
for (int j = 0; j < Length_A; ++j)
{
if(A[i][j] != INF)
cout << A[i][j] << " ";
else
cout < " - ";
}
cout << "\n";
}
}
vector<int**> matrix_chain_mult(int* P, int P_length)
{
vector<int**> vect;
int n = P_length - 1;
int** m;
int** s;
m = Init(P_length);
s = Init(P_length);
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)
{
 int j = i + l - 1;
m[i][j] = INF;
for (int k = i; k < j; ++k)
{
int 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;
}
}
}
}
vect.push_back(m);
vect.push_back(s);
return vect;
}
void PRINT_OPTIMAL_PARENS(int** s, int i, int j)
{
if(i == j)
cout << "A" << i;
else
{
cout << "(" ;
PRINT_OPTIMAL_PARENS(s, i, s[i][j]);
PRINT_OPTIMAL_PARENS(s, s[i][j] + 1, j);
cout << ")";
}

}
int main ()//paara el caso del ejemplo
{
vector<int**> Vect;
int n;
cin >> n;
int* v = new int[n];
for (int i = 0; i < n; ++i)
{
int c;
cin >> c;
v[i] = c;
}
int** A = Init(n);
int** S = Init(n);
Vect = matrix_chain_mult(v, n);
A = Vect[0];
S = Vect[1];
cout << " m\n\n";
cout << " " << A[1][6] << "\n";
cout << " " << A[1][5] << " " << A[2][6] << "\n";
cout << " " << A[1][4] << " " << A[2][5] << " " << A[3][6] << "\n";
cout << " " << A[1][3] << " " << A[2][4] << " " << A[3][5] << " " << A[4][6] << "\n";
 cout << " " << A[1][2] << " " << A[2][3] << " " << A[3][4] << " " << A[4][5] << " " << A[5][6]
<< "\n";
cout << " " << A[1][1] << " " << A[2][2] << " " << A[3][3] << " " << A[4][4] << " " <<
A[5][5] << " " << A[6][6] << "\n";
cout << "\n---------------------------------------\n s\n\n";
cout << " " << S[1][6] << "\n";
cout << " " << S[1][5] << " " << S[2][6] << "\n";
cout << " " << S[1][4] << " " << S[2][5] << " " << S[3][6] << "\n";
cout << " " << S[1][3] << " " << S[2][4] << " " << S[3][5] << " " << S[4][6] << "\n";
cout << " " << S[1][2] << " " << S[2][3] << " " << S[3][4] << " " << S[4][5] << " " <<
S[5][6] << "\n";
cout << "\n---------------------------------------\n\t\t";
PRINT_OPTIMAL_PARENS(S, 1, 6);
}
Input (Entradas)

30 35 15 5 10 20 25

Output (salidas)

15125

11875 10500

9375 7125 5375

7875 4375 2500 3500

15750 2625 750 1000 5000

0 0 0 0 0 0

---------------------------------------

3 3

3 3 3

1 3 3 5

1 2 3 4 5

---------------------------------------

((A1(A2A3))((A4A5)A6))