coding problem (matrix multiply)

G

George

I have two questions that I need help with the first when I create the
array using the random function it does not print the first part of the
matrix ie:

Recursive Matrix Chain
0 0 0 0 0 0 0
0 0 88 300 668 560 562
0 0 0 80 360 472 496
0 0 0 0 560 720 708
0 0 0 0 0 560 588
0 0 0 0 0 0 168
0 0 0 0 0 0 0
Matrix Chain Order
0 0 0 0 0 0 0
0 0 0 300 668 560 562
0 0 0 80 360 472 496
0 0 0 0 560 720 708
0 0 0 0 0 560 588
0 0 0 0 0 0 168
0 0 0 0 0 0 0
the 88 is missing and I have played around with the functions and I
can't get it to work. But it does work when the matrix is declared by
me manually. Also I was wondering how I could get my code to output the
scalar mulitplications (op-count).

Thanks a lot the code is below.
#include <iomanip>
#include <iostream>
#include <cstdlib>

using namespace std;

const int SIZE = 7;
const int MAX = 999999;

int M[SIZE][SIZE];

//int P[SIZE + 1] = { 5, 10, 3, 12, 5, 50, 6};
int P[SIZE];

int Recursive_Matrix(int i, int j);
void Print_M();
int Matrix_Chain_Order();


int main()
{
for(int i=1; i<=SIZE; i++)
{
P=rand()%15;
cout<<P<<endl;
}
cout << "Recursive Matrix Chain" << endl;
Recursive_Matrix( 0, SIZE - 1);
Print_M();
cout << "Matrix Chain Order" << endl;
Matrix_Chain_Order();
Print_M();
return 0;
}

int Recursive_Matrix(int i, int j)
{
int q;

if( i == j )
return 0;
else
{
M[j] = MAX;
for(int k = i; k <= j - 1; k++)
{
q = Recursive_Matrix(i, k);
q += Recursive_Matrix( k+1, j);
q += P * P[k + 1] * P[j + 1];
if( q < M[j])
M[j] = q;
}
}
return M[j];
}

int Matrix_Chain_Order()
{
int n = SIZE;
int s[SIZE][SIZE];

for (int i=1;i<=n;i++)
{ M = 0; }
for (int l=2;l<=n;l++){
for (int i=1;i<=n-l+1;i++)
{
int j = i+l-1;
M[j] = MAX;
for(int k=i;k<=j-1;k++)
{
int q = M[k] + M[k+1][j] + P[i-1]*(P[k])*(P[j]);
if(q<M[j])
{
M[j] = q;
s[j] = k;
}
}
return M[j];
return s[j];
}
}
return 0;
}

void Print_M()
{
for(int x = 0; x < SIZE; x++)
{
for(int y = 0; y < SIZE; y++)
{
cout << setw(7) << M[x][y];
}
cout << endl;
}
}
 
V

Victor Bazarov

George said:
I have two questions that I need help with the first when I create the
array using the random function it does not print the first part of the
matrix ie:

Recursive Matrix Chain
0 0 0 0 0 0 0
0 0 88 300 668 560 562
0 0 0 80 360 472 496
0 0 0 0 560 720 708
0 0 0 0 0 560 588
0 0 0 0 0 0 168
0 0 0 0 0 0 0
Matrix Chain Order
0 0 0 0 0 0 0
0 0 0 300 668 560 562
0 0 0 80 360 472 496
0 0 0 0 560 720 708
0 0 0 0 0 560 588
0 0 0 0 0 0 168
0 0 0 0 0 0 0
the 88 is missing and I have played around with the functions and I
can't get it to work. But it does work when the matrix is declared by
me manually. Also I was wondering how I could get my code to output the
scalar mulitplications (op-count).

Thanks a lot the code is below.
#include <iomanip>
#include <iostream>
#include <cstdlib>

using namespace std;

const int SIZE = 7;
const int MAX = 999999;

int M[SIZE][SIZE];

//int P[SIZE + 1] = { 5, 10, 3, 12, 5, 50, 6};
int P[SIZE];

int Recursive_Matrix(int i, int j);
void Print_M();
int Matrix_Chain_Order();


int main()
{
for(int i=1; i<=SIZE; i++)
{
P=rand()%15;
cout<<P<<endl;
}
cout << "Recursive Matrix Chain" << endl;
Recursive_Matrix( 0, SIZE - 1);
Print_M();
cout << "Matrix Chain Order" << endl;
Matrix_Chain_Order();
Print_M();
return 0;
}

int Recursive_Matrix(int i, int j)
{
int q;

if( i == j )
return 0;
else
{
M[j] = MAX;
for(int k = i; k <= j - 1; k++)
{
q = Recursive_Matrix(i, k);
q += Recursive_Matrix( k+1, j);
q += P * P[k + 1] * P[j + 1];
if( q < M[j])
M[j] = q;
}
}
return M[j];
}

int Matrix_Chain_Order()
{
int n = SIZE;
int s[SIZE][SIZE];

for (int i=1;i<=n;i++)
{ M = 0; }
for (int l=2;l<=n;l++){
for (int i=1;i<=n-l+1;i++)
{
int j = i+l-1;
M[j] = MAX;
for(int k=i;k<=j-1;k++)
{
int q = M[k] + M[k+1][j] + P[i-1]*(P[k])*(P[j]);
if(q<M[j])
{
M[j] = q;
s[j] = k;
}
}
return M[j];
return s[j];


First of all, you have two returns in a row. Second, they are not
conditional, so this loop only executes once.

Second, if you remove those, a some point in this loop 'j' becomes 7
and you run over the buffer by indexing M[6][7] (and s[6][7] as well).
You need to work on this loop structure, I suggest looking into indices
and the fact that in C++ they begin with 0 and not with 1.

BTW, you could have figured all that yourself if you used a decent
compiler and debugger.
}
}
return 0;
}
[...]

V
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,482
Members
44,901
Latest member
Noble71S45

Latest Threads

Top