Nick, you don't have to make size+1
it works with your changing the structure of the statement that makes the recursive calls
i get the correct reults now, THANKS!
The parenthization is wrong, but i can fix that!
Code:
Results:
Recursive
0 0 0 0 0 0 0
0 0 15750 7875 9375 11875 15125
0 0 0 2625 4375 7125 10500
0 0 0 0 750 2500 5375
0 0 0 0 0 1000 3500
0 0 0 0 0 0 5000
0 0 0 0 0 0 0
0 1 2 3 4 5
0 0 2 3 4 5
0 0 0 3 4 5
0 0 0 0 4 5
0 0 0 0 0 5
(((((A1A2)A3)A4)A5)A6)
Non-Recursive
0 15750 7875 9375 11875 15125
0 0 2625 4375 7125 10500
0 0 0 750 2500 5375
0 0 0 0 1000 3500
0 0 0 0 0 5000
0 1 1 3 3 3
0 0 2 3 3 3
0 0 0 3 3 3
0 0 0 0 4 5
0 0 0 0 0 5
((A1(A2A3))((A4A5)A6))
********************CODE
#include <iostream>
#include <cstdlib>
using namespace std;
const int SIZE = 7;
const int MAX = 999999;
int M[SIZE][SIZE];
int S[SIZE][SIZE];
// multiply
// 1x1, 1x2, 2x3, 4x5, 6x7
//int P[SIZE + 1] = { 1, 1, 2, 3, 4, 5, 6, 7};
int P[SIZE] = {30,35,15,5,10,20,25};
int Recursive_Matrix(int i, int j);
void Print_Optimal_Parens(int S[][SIZE], int i, int j);
void Print_M();
void Print_S();
int main()
{
Recursive_Matrix( 1, SIZE - 1);
Print_M();
cout << endl << endl;
Print_S();
cout << endl << endl;
Print_Optimal_Parens( S, 1, SIZE-1);
cout << endl << endl;
system("PAUSE");
return 0;
}
int Recursive_Matrix(int i, int j)
{
int q;
if( i == j )
return 0;
else
{
M[i][j] = MAX;
for(int k = i; k <= j - 1; k++)
{
q = Recursive_Matrix(i, k);
q += Recursive_Matrix( k+1, j);
q += P[i-1] * P[k] * P[j];
if( q < M[i][j])
M[i][j] = q;
S[i][j] = k;
}
}
return M[i][j];
}
void Print_M()
{
for(int x = 0; x < SIZE; x++)
{
for(int y = 0; y < SIZE; y++)
{
cout << M[x][y] << " ";
}
cout << endl;
}
}
void Print_Optimal_Parens(int S[][SIZE], 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 << ")";
}
}
void Print_S()
{
for(int x = 1; x<= SIZE-2; x++)
{
for(int y = 1; y <= SIZE-1; y++)
{
cout << S[x][y] << " ";
}
cout << endl;
}
}