Advertisement
daskalot

Untitled

May 11th, 2019
224
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 6.24 KB | None | 0 0
  1. import java.util.Scanner;
  2. class Matrix {
  3. int[][] mat;
  4. public int N,M;
  5. public Matrix(int n,int m){
  6. this.N = n;
  7. this.M = m;
  8. mat = new int[N][M];
  9. }
  10. public Matrix(int n) {
  11. this.N = n;
  12. this.M = n;
  13. this.mat = new int[N][M];
  14. }
  15. public void fix2(int newN, int newM) {
  16. int[][] c = new int[newN][newM];
  17. for(int i=0;i<this.N;i++)
  18. for(int j=0;j<this.M;j++)
  19. c[i][j] = this.mat[i][j];
  20. this.N = newN; this.M = newM;
  21. this.mat = c;
  22. }
  23. public void fix(int newDim) {
  24. int[][] c = new int[newDim][newDim];
  25. for(int i=0;i<N;i++)
  26. for(int j=0;j<M;j++)
  27. c[i][j] = mat[i][j];
  28. this.N = newDim;
  29. this.M = newDim;
  30. mat = c;
  31. }
  32. public void init(Scanner sc) {
  33. for(int i=0;i<N;i++)
  34. for(int j=0;j<M;j++)
  35. mat[i][j] = sc.nextInt();
  36. }
  37. public Matrix getSubmatrix(int startRow, int startCol, int dim){
  38. Matrix subM = new Matrix(dim);
  39. for (int i = 0; i<dim ; i++ )
  40. for (int j=0;j<dim ; j++ )
  41. subM.mat[i][j] = this.mat[startRow+i][startCol+j];
  42. return subM;
  43. }
  44. public void putSubmatrix(int startRow, int startCol, Matrix b){
  45. for (int i = 0; i<b.N; i++ )
  46. for (int j=0;j<b.N; j++ )
  47. mat[startRow+i][startCol+j] = b.mat[i][j];
  48. }
  49.  
  50. public Matrix sum(Matrix b){
  51. Matrix c = new Matrix(this.N);
  52. for(int i = 0; i<N;i++){
  53. for(int j = 0;j<M;j++)
  54. c.mat[i][j] = mat[i][j]+b.mat[i][j];
  55. }
  56. return c;
  57. }
  58. public Matrix sub(Matrix b){
  59. Matrix c = new Matrix(this.N);
  60. for(int i = 0;i<this.N;i++)
  61. for(int j = 0;j<this.M;j++)
  62. c.mat[i][j] = this.mat[i][j]-b.mat[i][j];
  63. return c;
  64. }
  65. public void printDims() {
  66. System.out.printf("DIMS: %dx%d\n",N,M);
  67. }
  68. public void printMatrix(){
  69. printDims();
  70. for(int i=0;i<this.N;i++,System.out.println())
  71. for(int j=0;j<this.M;System.out.printf("%d ",this.mat[i][j]),j++);
  72. }
  73. public int elementSum(){
  74. int rez = 0;
  75. for(int i=0;i<this.N;i++)
  76. for(int j=0;j<this.M;j++)
  77. rez += this.mat[i][j];
  78. return rez;
  79. }
  80. //TO DO
  81. public Matrix block2(int n1,int n2,int m2,Matrix b, int block) {
  82. Matrix c = new Matrix(this.N,b.M);
  83. for(int i=0;i<this.N/block;i++)
  84. for(int j=0;j<b.M/block;j++) {
  85. Matrix s = new Matrix(block);
  86. for(int k=0;k<this.M/block;k++) {
  87. Matrix aa = this.getSubmatrix(i, k, block);
  88. Matrix bb = b.getSubmatrix(k, j, block);
  89. Matrix p = aa.naiveMultiply(bb);
  90. System.out.println(p.elementSum());
  91. s = s.sum(p);
  92. }
  93. c.putSubmatrix(i, j, s);
  94. }
  95. return c;
  96. }
  97. public Matrix naiveMultiply(Matrix b){
  98. Matrix c = new Matrix(this.N,b.M);
  99. for(int i=0;i<this.N;i++)
  100. for(int j=0;j<b.M;j++)
  101. for(int k=0;k<b.N;k++)
  102. c.mat[i][j] += this.mat[i][k] * b.mat[k][j];
  103. return c;
  104. }
  105. public Matrix DC(Matrix b,int stop, boolean isStrassen) {
  106. Matrix c = new Matrix(this.N);
  107. if(N == stop) return this.naiveMultiply(b);
  108. //SubMatrix
  109. Matrix a11 = this.getSubmatrix(0,0,N/2);
  110. Matrix a12 = this.getSubmatrix(0,N/2,N/2);
  111. Matrix a21 = this.getSubmatrix(N/2,0,N/2);
  112. Matrix a22 = this.getSubmatrix(N/2,N/2,N/2);
  113. Matrix b11 = b.getSubmatrix(0,0,N/2);
  114. Matrix b12 = b.getSubmatrix(0,N/2,N/2);
  115. Matrix b21 = b.getSubmatrix(N/2,0,N/2);
  116. Matrix b22 = b.getSubmatrix(N/2,N/2,N/2);
  117. if(isStrassen) {
  118. Matrix m1 = a11.DC(b12.sub(b22),stop,isStrassen); System.out.println(m1.elementSum());
  119. Matrix m2 = (a11.sum(a12)).DC(b22,stop,isStrassen); System.out.println(m2.elementSum());
  120. Matrix m3 = (a21.sum(a22)).DC(b11,stop,isStrassen); System.out.println(m3.elementSum());
  121. Matrix m4 = a22.DC(b21.sub(b11),stop,isStrassen); System.out.println(m4.elementSum());
  122. Matrix m5 = (a11.sum(a22)).DC(b11.sum(b22),stop,isStrassen); System.out.println(m5.elementSum());
  123. Matrix m6 = (a12.sub(a22)).DC(b21.sum(b22),stop,isStrassen); System.out.println(m6.elementSum());
  124. Matrix m7 = (a11.sub(a21)).DC(b11.sum(b12),stop,isStrassen); System.out.println(m7.elementSum());
  125. //Conquer
  126. c.putSubmatrix(0,0,(m5.sum(m4.sub(m2))).sum(m6));
  127. c.putSubmatrix(0,N/2,m1.sum(m2));
  128. c.putSubmatrix(N/2,0,m3.sum(m4));
  129. c.putSubmatrix(N/2,N/2,((m1.sum(m5).sub(m3)).sub(m7)));
  130. return c;
  131. }
  132. else {
  133. Matrix m1 = a11.DC(b11, stop,isStrassen); System.out.println(m1.elementSum());
  134. Matrix m2 = a12.DC(b21, stop,isStrassen); System.out.println(m2.elementSum());
  135. Matrix m3 = a11.DC(b12, stop,isStrassen); System.out.println(m3.elementSum());
  136. Matrix m4 = a12.DC(b22,stop,isStrassen); System.out.println(m4.elementSum());
  137. Matrix m5 = a21.DC(b11, stop,isStrassen); System.out.println(m5.elementSum());
  138. Matrix m6 = a22.DC(b21, stop,isStrassen); System.out.println(m6.elementSum());
  139. Matrix m7 = a21.DC(b12, stop,isStrassen); System.out.println(m7.elementSum());
  140. Matrix m8 = a22.DC(b22, stop,isStrassen); System.out.println(m8.elementSum());
  141. //Conquer
  142. c.putSubmatrix(0, 0, m1.sum(m2));
  143. c.putSubmatrix(0, N/2, m3.sum(m4));
  144. c.putSubmatrix(N/2,0,m5.sum(m6));
  145. c.putSubmatrix(N/2,N/2,m7.sum(m8));
  146. return c;
  147. }
  148. }
  149. }
  150. public class Naloga2 {
  151. static int n1, m1, n2, m2, stop;
  152. static Matrix a, b,result;
  153. static String in;
  154. static void read() {
  155. Scanner sc = new Scanner(System.in);
  156. in = sc.next();
  157. if(!in.equals("os")) stop = sc.nextInt();
  158. n1 = sc.nextInt(); m1 = sc.nextInt();
  159. a = new Matrix(n1,m1);
  160. a.init(sc);
  161. n2 = sc.nextInt(); m2 = sc.nextInt();
  162. b = new Matrix(n2,m2);
  163. b.init(sc);
  164. sc.close();
  165. }
  166. static void solve() {
  167. Matrix c = new Matrix(n1);
  168. if(in.equals("os")) c = a.naiveMultiply(b);
  169. else if(in.equals("bl")) {
  170. fix2();
  171. return;
  172. }
  173. else {
  174. fix();
  175. c = a.DC(b,stop,in.contentEquals("st"));
  176. }
  177. c.printMatrix();
  178. }
  179. static void fix2() {
  180. int l = n1, m = n2, r = m2;
  181. while(n1%stop!=0) n1++;
  182. while(n2%stop!=0) n2++;
  183. while(m1%stop!=0) m1++;
  184. while(m2%stop!=0) m2++;
  185. a.fix2(n1,n2);
  186. b.fix2(m1, m2);
  187. Matrix c = new Matrix(n1);
  188. c = a.block2(l,m,r,b,stop);
  189. for(int i=0;i<l;i++,System.out.println())
  190. for(int j=0;j<r;System.out.printf("%d ",c.mat[i][j]),j++);
  191.  
  192. }
  193. static void fix() {
  194. int newDim = Math.max(Math.max(n1, m1),Math.max(n2,m2));
  195. while(!((newDim & (newDim-1)) == 0)) newDim++;
  196. a.fix(newDim); b.fix(newDim);
  197. }
  198. public static void main(String[] args) {
  199. read();
  200. solve();
  201. }
  202. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement