#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

Which particular nested loops are you talking about?

Perhaps it would be better to give a small test program as an example, one that contains only the bit that you want to know how to fix. This way people will be able to see how to help you a bit more.

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;
}

This is the loop which causes the shape of the triangle to change...

(line 124 to 131)

It's still not clear to me what you're asking, since I'm not sure about your notation with the letters in the example you gave. The piece of code below prints out the indices that you'd try to access in the mult array in your example. The first is what I thought you wanted from your example, the second is what you actually have. Are we getting close?

#include <iostream>

using namespace std;

int main()
{
    int mat = 7;
    for(int y = 0; y < mat; y++)
    {
        for(int x = mat - y - 1; x >= 0; x--)
            cout << '(' << x << ',' << y << ") ";
        cout << endl;
    }
    cout << endl;
    for(int x = mat - 1; x >= 0 ; x--)
    {
         for( int y=0; y <= x; y++)
             cout << '(' << x << ',' << y << ") ";
         cout << endl;
    }
}

Ah, OK then. I think that you want something like:

for(int y = 0; y < mat; y++)
{
    for(int i = 0; i < y; y++)
        cout << ',';
    for(int x = y; x < mat - 1; x++)
        cout << mult[x][y] << ',';
    cout << mult[x][y] << endl;
}

this will output array elements with indices in this order:

(0 0) (1 0) (2 0) (3 0) (4 0) (5 0)
      (1 1) (2 1) (3 1) (4 1) (5 1)
            (2 2) (3 2) (4 2) (5 2)
                  (3 3) (4 3) (5 3)
                        (4 4) (5 4)
                              (5 5)

as opposed to what you had originally:

(0,0) 
(1,0) (1,1) 
(2,0) (2,1) (2,2) 
(3,0) (3,1) (3,2) (3,3) 
(4,0) (4,1) (4,2) (4,3) (4,4) 
(5,0) (5,1) (5,2) (5,3) (5,4) (5,5)

If you're copying the result into excel, then it's probably easiest to separate the values with commas, which I have in the code fragment above. There's an extra loop before values actually start getting outputted, which basically pads the line so that the columns (separated by commas) line up in a spreadsheet. The final value is also printed outside the second loop, so that there's no comma at the end of the line. I think that's more what you're looking for?

This wasn't really a coding problem, as such, since you already had a working program. This seems more like just getting yourself confused. In future, I would make a small test program that just outputs the array indices that you're trying to access (like the one I posted previously). This way you can easily play about with different loop conditions and see what you want to access and what you're actually trying to access.

Edited 5 Years Ago by ravenous: corrected typing error

thank you very much:) i tried copying your code and running it,it didnt really output like what you shower..but im very sure its there..so i`ll try to play around with the codes that you gave and try.. :) thank you very much again

thank you very much:) i tried copying your code and running it,it didnt really output like what you shower..

No, it should have had commas instead of tabs, so the alignment on the terminal will be messed up. However, if you save the output with the extension "csv", then it should open in the correct way in a spreadsheet. Is there something else, or just the format? You can get the order of the indices right by trial an error, I think.

This article has been dead for over six months. Start a new discussion instead.