Advertisement
Caio_25

Multiplicação de Matrizes Dynamic Programming

Apr 24th, 2019
134
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.83 KB | None | 0 0
  1. #include<stdio.h>
  2.  
  3. int b[1000];
  4. int mat[1000][1000];
  5. int contador = 0;
  6.  
  7. int m(int i, int j);
  8. void inicializar_matriz();
  9. void imprimir(int n);
  10.  
  11. int main()
  12. {
  13.     int n;
  14.    
  15.     inicializar_matriz();
  16.     printf("Informe a quantidade de matrizes: ");
  17.     scanf("%d", &n);
  18.    
  19.     printf("Informe as dimensoes das matrizes: ");
  20.     for(int i = 0; i <= n; i++)
  21.     {
  22.         scanf("%d", &b[i]);
  23.     }
  24.      
  25.      
  26.     printf("Menor numero de op: %d\n", m(1, n) );
  27.     printf("Contador %d\n", contador);
  28.    
  29.    
  30.    
  31.     imprimir(n);
  32. }
  33.  
  34. void inicializar_matriz()
  35. {
  36.     for(int i = 1; i < 1000; i++)
  37.     {
  38.         for(int j = 1; j < 1000; j++)
  39.         {
  40.             mat[i][j] = 0;
  41.         }
  42.     }
  43. }
  44.  
  45. int m(int i, int j)
  46. {
  47.     contador = contador + 1;
  48.     if(i <= j)
  49.     {
  50.         if(i == j)
  51.         {
  52.             return(0);
  53.         }
  54.        
  55.         int aux;
  56.        
  57.         if(mat[i][i] == 0)
  58.         {
  59.             mat[i][i] = m(i, i);
  60.         }
  61.        
  62.         //printf("mat[i][i] %d %d : %d\n", i, i, mat[i][i]);
  63.        
  64.        
  65.         if(mat[i+1][j] == 0)
  66.         {
  67.             mat[i+1][j] == m(i+1, j);
  68.         }
  69.        
  70.         //printf("mat[i+1][j] %d %d : %d\n", i + 1, j, mat[i + 1][j]);
  71.        
  72.         mat[i][j] = mat[i][i] + mat[i+1][j] + b[i-1] * b[i] * b[j];
  73.        
  74.         //printf("mat[i][j] %d %d : %d\n",i, j , mat[i][j]);
  75.        
  76.         for(int k = i + 1; k < j; k++)
  77.         {
  78.             if(mat[i][k] == 0)
  79.             {
  80.                 mat[i][k] = m(i, k);
  81.             }
  82.             //printf("mat[i][k] %d %d : %d\n", i, k , mat[i][k]);
  83.            
  84.             if(mat[k+1][j] == 0)
  85.             {
  86.                 mat[k+1][j] = m(k+1, j);
  87.             }
  88.            
  89.             //printf("mat[k+1][j] %d %d : %d\n", k+1, j, mat[k+1][j]);
  90.            
  91.             aux = mat[i][k] + mat[k+1][j]  + b[i - 1] * b[k] * b[j] ;
  92.            
  93.             if( aux < mat[i][j])
  94.             {
  95.                 mat[i][j] = aux;
  96.             }
  97.            
  98.             //printf("mat[i][j] %d %d : %d\n", i, j , mat[i][j]);
  99.         }
  100.        
  101.         return(mat[i][j]);
  102.     }
  103.    
  104.     return(0);
  105. }
  106.  
  107. void imprimir(int n)
  108. {
  109.    
  110.     for(int i = 1; i <=n; i++)
  111.     {
  112.         for(int j = 1; j <=n; j++)
  113.         {
  114.             printf("%d ", mat[i][j]);
  115.         }printf("\n");
  116.     }printf("\n");
  117. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement