Advertisement
Guest User

Untitled

a guest
Nov 24th, 2015
83
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.35 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. #define lld long long int
  4.  
  5. using namespace std;
  6.  
  7. lld** base(lld** a, lld** b, int x){
  8. lld** aux = new lld*[1];
  9. aux[0] = new lld[1];
  10. aux[0][0] = 0;
  11. for(int i = 0; i < x; i++)
  12. aux[0][0] += a[0][i] * b[i][0];
  13. return aux;
  14. }
  15.  
  16. lld** recorta(lld** A, int y1, int x1, int y2, int x2){
  17. int n = y2 - y1 + 1;
  18. int m = x2 - x1 + 1;
  19. if(n == 0 || m == 0)
  20. return NULL;
  21. lld** aux = new lld*[n];
  22. for(int i = 0; i < n; i++)
  23. aux[i] = new lld[m];
  24. for(int i = 0; i < n; i++){
  25. for(int j = 0; j < m; j++){
  26. aux[i][j] = A[i + y1][j + x1];
  27. //cout << aux[i][j] << " ";
  28. }
  29. // cout << endl;
  30. }
  31. return aux;
  32. }
  33.  
  34. lld **reconstruye(lld **a, lld **b, lld **c, lld **d, int n, int m){
  35. lld ** aux = new lld*[n];
  36. for(int i = 0; i < n; i++)
  37. aux[i] = new lld[m];
  38. int nMitad = (n + 1) / 2;
  39. int mMitad = (m + 1) / 2;
  40.  
  41. for(int i = 0; i < nMitad; i++){
  42. for(int j = 0; j < mMitad; j++){
  43. aux[i][j] = a[i][j];
  44. }
  45. }
  46. for(int i = 0; i < nMitad; i++){
  47. for(int j = 0; j < m - mMitad; j++){
  48. aux[i][j + mMitad] = b[i][j];
  49. }
  50. }
  51. for(int i = 0; i < n - nMitad; i++){
  52. for(int j = 0; j < mMitad; j++){
  53. aux[i + nMitad][j] = c[i][j];
  54. }
  55. }
  56. for(int i = 0; i < n - nMitad; i++){
  57. for(int j = 0; j < m - mMitad; j++){
  58. aux[i + nMitad][j + mMitad] = d[i][j];
  59. }
  60. }
  61. return aux;
  62. }
  63.  
  64. lld **suma(lld **a, lld **b, int n, int m){
  65. for(int i = 0; i < n; i++)
  66. for(int j = 0; j < m; j++)
  67. a[i][j] += b[i][j];
  68. return a;
  69. }
  70.  
  71. lld **multi(lld** A, lld** B, int n, int p, int m){
  72. if(n == 0 || p == 0 || m == 0)
  73. return NULL;
  74. if(n == 1 && m == 1)
  75. return base(A, B, p);
  76. lld **a11, **a12, **a21, **a22, **b11, **b12, **b21, **b22;
  77. int nMitad = (n - 1) / 2;
  78. int mMitad = (m - 1) / 2;
  79. int pMitad = (p - 1) / 2;
  80.  
  81. a11 = recorta(A, 0, 0, nMitad, pMitad);
  82. a12 = recorta(A, 0, pMitad + 1, nMitad, p - 1);
  83. a21 = recorta(A, nMitad + 1, 0, n - 1, pMitad);
  84. a22 = recorta(A, nMitad + 1, pMitad + 1, n - 1, p - 1);
  85.  
  86. b11 = recorta(B, 0, 0, pMitad, mMitad);
  87. b12 = recorta(B, 0, mMitad + 1, pMitad, m - 1);
  88. b21 = recorta(B, pMitad + 1, 0, p - 1, mMitad);
  89. b22 = recorta(B, pMitad + 1, mMitad + 1, p - 1, m - 1);
  90.  
  91. lld **C11 = suma(multi(a11, b11, nMitad + 1, pMitad + 1, mMitad + 1), multi(a12, b21, nMitad + 1, p - pMitad - 1, mMitad + 1), nMitad + 1, mMitad + 1) ;
  92. lld **C12 = suma(multi(a11, b12, nMitad + 1, pMitad + 1, m - mMitad - 1), multi(a12, b22, nMitad + 1, p - pMitad - 1, m - mMitad - 1), nMitad + 1, m - mMitad - 1) ;
  93. lld **C21 = suma(multi(a21, b11, n - nMitad - 1, pMitad + 1, mMitad + 1), multi(a22, b21, n - nMitad - 1, p - pMitad - 1, mMitad + 1), n - nMitad - 1, mMitad + 1) ;
  94. lld **C22 = suma(multi(a21, b12, n - nMitad - 1, pMitad + 1, m - mMitad - 1), multi(a22, b22, n - nMitad - 1, p - pMitad - 1, m - mMitad - 1), n - nMitad - 1, m - mMitad - 1) ;
  95.  
  96. return reconstruye(C11, C12, C21, C22, n, m);
  97. }
  98.  
  99. int main(){
  100. int n, p, m;
  101. cin >> n >> p >> m;
  102. lld **A = new lld*[n];
  103. for(int i = 0; i < n; i++)
  104. A[i] = new lld[p];
  105.  
  106. lld **B = new lld*[p];
  107. for(int i = 0; i < p; i++)
  108. B[i] = new lld[m];
  109. puts("Inserte la matriz A:");
  110. for(int i = 0; i < n; i++)
  111. for(int j = 0; j < p; j++)
  112. cin >> A[i][j];
  113. puts("Inserte la matriz B:");
  114. for(int i = 0; i < p; i++)
  115. for(int j = 0; j < m; j++)
  116. cin >> B[i][j];
  117. puts("La multipilacion es:");
  118. lld** ans = multi(A, B, n, p, m);
  119. for(int i = 0; i < n; i++){
  120. for(int j = 0; j < m; j++){
  121. cout << ans[i][j] << " ";
  122. }
  123. puts("");
  124. }
  125. return 0;
  126. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement