/*
 * Thomas H. Cormen, Charles E. Leiserson, 
 * Ronald L. Rivest, Clifford Stein
 * ÚJ ALGORITMUSOK : Mátrixok véges sorozatainak szorzása 295-300. oldal
 * megvalósítása java-ban
 * 
 */

package matrixszorzas;

public class MatrixSzorzas {
    
    static void optimalis_zarojelezes_nyomtatas(int[][] s, int i, int j){
        if (j==i) {
            System.out.print("A"+i) ;
        }else{
            System.out.print("(") ;
            optimalis_zarojelezes_nyomtatas(s,i,s[i][j]);
            optimalis_zarojelezes_nyomtatas(s,s[i][j]+1,j);
            System.out.print(")") ;
        }
    }

  static void matrix_nyomtatas( int [][] a ) {
     System.out.println() ;
     for ( int i=1; i<a.length; i++ ) {
        for ( int j=1; j<a[i].length; j++ ) {
           System.out.print( a[i][j] + ", " );
        }
        System.out.println() ;
     }
  }

  static void matrix_szorzas_sorrend(int [][] m,int[][] s, int [] p) {
     int n = p.length - 1 ;
     for ( int i=1; i<=n; i++ ) m[i][i] = 0 ;   //foatlo kinullazasa
     for ( int d=2; d<=n; d++ ) {               //d a szorzat hossza
        for ( int i=1; i<=(n-d+1); i++ ) {
          int j = i + d -1;
          m[i][j] = -1 ;                        //m[i][j]<-vegtelen
          for ( int k=i; k<=(j-1); k++ ) {
              int q = m[i][k] + m[k+1][j] +  p[i-1]*p[k]*p[j] ;
              if ( m[i][j]==-1 || q < m[i][j] ){
                  m[i][j] = q;
                  s[i][j] = k;
              }
         }
          /*
           * //Részeredmények kiíratása (opcionális):
           * matrix_nyomtatas(m) ;
           * System.out.print("Zárójelezés: ");
           * optimalis_zarojelezes_nyomtatas(s,i,j);
           * System.out.println() ;
           */
        }
     }
  }
  
  public static void main(String[] args) {
      // A_1 30x35-os, A_2 35x15-os, A_3 15x5-os, ...
      int[] p = { 30, 35, 15, 5, 10, 20, 25 } ;
      int n = p.length - 1 ;
      int[][] m = new int[n+1][n+1] ;
      int[][] s = new int[n+1][n+1] ;
      
      matrix_szorzas_sorrend(m,s,p) ;
      
      //Kiíratások...    
      System.out.println("Mátrixok:");
      for (int i=0; i<n; i++) System.out.println("A"+i+"("+p[i]+"x"+p[i+1]+")");
      System.out.print("\nSkalárszorzások száma:");
      matrix_nyomtatas(m) ;
      System.out.print("\nOptimális zárójelezés:");
      optimalis_zarojelezes_nyomtatas(s,1,n);
      System.out.println("\nSkalár szorzasok optimalis száma = "+ m[1][n] ) ;
  }
}
/* Output:
 * 
Mátrixok:
A0(30x35)
A1(35x15)
A2(15x5)
A3(5x10)
A4(10x20)
A5(20x25)

Skalárszorzások száma:
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, 0, 0, 0, 0, 0, 

Optimális zárójelezés:((A1(A2A3))((A4A5)A6))
Skalár szorzasok optimalis száma = 15125
 */