#include <iostream>
#include<cstdlib>
#include<iomanip>
using namespace std;
int* userInput(int mat);
void multiply(int mat, int* array);
void print(int **mult, int **divides, int mat, int row, int col);
//Main method, calls IO and handles the case for only 1 matrix.
int main()
{
int mat = 0,i,j;
int arrayA[mat][mat];
cout << "Enter the number of matrices: ";
cin >> mat;
if(mat == 1 | mat == 0)
{ cout << endl;
cout << endl;
cout << "There are no multiplications." << endl;
}
else
{
int *array = userInput(mat);
multiply(mat, array);
}
cout << "---------------------------------"<<endl;
cout << endl;
}
//handes input, given a number of matrices, asks for the dimensions and returns them in an array
int* userInput(int mat)
{
int *arrayB;
arrayB = new int[mat+1];
for(int i = 0; i < mat+1; i++)
{
if(i == 0)
cout << "Please enter the number of rows in matrix 1: ";
else
if(i == mat)
cout << "Enter the number of columns in matrix " << mat << ": ";
else
cout << "Enter the number of columns in matrix " << i << " and rows in matrix " << i+1 << ": ";
cin >> arrayB[i];
}
return arrayB;
}
//given a number of matrices, and an array of dimensions (size 1+mat)
//computes the table of the least amount of multiplies from matrices a through b
//where this is stored in mult[a][b] (arrays start at 0, that is the number
//of mult required for the first through third arrays are stored in mult[0][2])
//and computes the appropropriate divide point for each multipilication in divides
void multiply(int mat, int* array)
{
int **mult = new int*[mat];
int **divides = new int*[mat];
for(int i = 0; i < mat; i++)
{
mult[i] = new int[mat];
divides[i] = new int[mat];
}
for(int i = 0; i < mat; i++)
for(int j = 0; j < mat; j++)
{mult[i][j] = -1; divides[i][j] = -1;}
for(int i = 0; i < mat; i++)
mult[i][i] = 0;
int y = 0;
for(int i = 1; i < mat; i++)
{
y = 0;
for(int x = i; x < mat; x++)
{
//here is where the order we want happens within the array, for x,y
//so what is the least number of multiplications to multiply arrays y through x?
//cout << x << "," << y << endl;
//int othermult = mult[x-1][y];
//if(mult[x][y+1] < othermult) othermult = mult[x][y+1];
int multto = 0;
if(x-y < 2)
{
multto = array[y]*array[x]*array[x+1];
}
else
{
for(int div = y; div < x; div++) //divide after the divide numnumber
{
int temp = array[y]*array[div+1]*array[x+1];
temp += mult[div][y];
temp += mult[x][div+1];
if(temp < multto || multto == 0)
{
multto = temp;
divides[x][y] = div;
}
}
}
mult[x][y] = multto;
//increment the y at the end
y++;
}
}
cout << endl;
cout<<endl;
cout << "---------------------------------"<<endl;
cout << "You need " << mult[mat-1][0] << " multiplications." << endl;
print(mult, divides, mat, 0, mat-1);
cout << endl;
for(int x = mat - 1; x >= 0 ; x--)
{
for( int y=0; y <= x; y++)
//printf("%7d ", arrayM[i][j]);
cout<<setw(7)<<mult[x][y]<<" ";
cout<<endl;
}
}
//given a divides matrix and a row and column, prints out
//the parenthatized multiplation pattern for the optimal
//matrix multiplication of matrices row through column (again starting at 0)
// mult = 5, 1,2,3,4,5,6 should be (((( 1 2 ) 3 ) 4 ) 5 )
// or in our format, (((( 0 1 ) 2 ) 3 ) 4 )
void print(int **mult, int **divides, int mat, int row, int col)
{
//cout << "row is " << row << " col is " << col << endl;
if(col-row == 0) cout << " " << row+1 << " ";
else if(col-row == 1) cout << "( " << row+1 << " " << row+2 << " )";//cout << "( "<< row << " " << row+1 << " )" << " ";
else
{
int divide = divides[col][row];
cout << "(";
print(mult, divides, mat, row, divide);
print(mult, divides, mat, divide+1, col);
cout << ")";
}
}how do i change my nested loops so it will look like
0abcdef
0****g
0***h
0**i
0*j
0k
0
instead of
fghijk0
e****0
d***0
c**0
b*0
a0
0
plz help...thank you
