Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.Scanner;
- class Matrix {
- int[][] mat;
- public int N,M;
- public Matrix(int n,int m){
- this.N = n;
- this.M = m;
- mat = new int[N][M];
- }
- public Matrix(int n) {
- this.N = n;
- this.M = n;
- this.mat = new int[N][M];
- }
- public void fix2(int newN, int newM) {
- int[][] c = new int[newN][newM];
- for(int i=0;i<this.N;i++)
- for(int j=0;j<this.M;j++)
- c[i][j] = this.mat[i][j];
- this.N = newN; this.M = newM;
- this.mat = c;
- }
- public void fix(int newDim) {
- int[][] c = new int[newDim][newDim];
- for(int i=0;i<N;i++)
- for(int j=0;j<M;j++)
- c[i][j] = mat[i][j];
- this.N = newDim;
- this.M = newDim;
- mat = c;
- }
- public void init(Scanner sc) {
- for(int i=0;i<N;i++)
- for(int j=0;j<M;j++)
- mat[i][j] = sc.nextInt();
- }
- public Matrix getSubmatrix(int startRow, int startCol, int dim){
- Matrix subM = new Matrix(dim);
- for (int i = 0; i<dim ; i++ )
- for (int j=0;j<dim ; j++ )
- subM.mat[i][j] = this.mat[startRow+i][startCol+j];
- return subM;
- }
- public void putSubmatrix(int startRow, int startCol, Matrix b){
- for (int i = 0; i<b.N; i++ )
- for (int j=0;j<b.N; j++ )
- mat[startRow+i][startCol+j] = b.mat[i][j];
- }
- public Matrix sum(Matrix b){
- Matrix c = new Matrix(this.N);
- for(int i = 0; i<N;i++){
- for(int j = 0;j<M;j++)
- c.mat[i][j] = mat[i][j]+b.mat[i][j];
- }
- return c;
- }
- public Matrix sub(Matrix b){
- Matrix c = new Matrix(this.N);
- for(int i = 0;i<this.N;i++)
- for(int j = 0;j<this.M;j++)
- c.mat[i][j] = this.mat[i][j]-b.mat[i][j];
- return c;
- }
- public void printDims() {
- System.out.printf("DIMS: %dx%d\n",N,M);
- }
- public void printMatrix(){
- printDims();
- for(int i=0;i<this.N;i++,System.out.println())
- for(int j=0;j<this.M;System.out.printf("%d ",this.mat[i][j]),j++);
- }
- public int elementSum(){
- int rez = 0;
- for(int i=0;i<this.N;i++)
- for(int j=0;j<this.M;j++)
- rez += this.mat[i][j];
- return rez;
- }
- //TO DO
- public Matrix block2(int n1,int n2,int m2,Matrix b, int block) {
- Matrix c = new Matrix(this.N,b.M);
- for(int i=0;i<this.N/block;i++)
- for(int j=0;j<b.M/block;j++) {
- Matrix s = new Matrix(block);
- for(int k=0;k<this.M/block;k++) {
- Matrix aa = this.getSubmatrix(i, k, block);
- Matrix bb = b.getSubmatrix(k, j, block);
- Matrix p = aa.naiveMultiply(bb);
- System.out.println(p.elementSum());
- s = s.sum(p);
- }
- c.putSubmatrix(i, j, s);
- }
- return c;
- }
- public Matrix naiveMultiply(Matrix b){
- Matrix c = new Matrix(this.N,b.M);
- for(int i=0;i<this.N;i++)
- for(int j=0;j<b.M;j++)
- for(int k=0;k<b.N;k++)
- c.mat[i][j] += this.mat[i][k] * b.mat[k][j];
- return c;
- }
- public Matrix DC(Matrix b,int stop, boolean isStrassen) {
- Matrix c = new Matrix(this.N);
- if(N == stop) return this.naiveMultiply(b);
- //SubMatrix
- Matrix a11 = this.getSubmatrix(0,0,N/2);
- Matrix a12 = this.getSubmatrix(0,N/2,N/2);
- Matrix a21 = this.getSubmatrix(N/2,0,N/2);
- Matrix a22 = this.getSubmatrix(N/2,N/2,N/2);
- Matrix b11 = b.getSubmatrix(0,0,N/2);
- Matrix b12 = b.getSubmatrix(0,N/2,N/2);
- Matrix b21 = b.getSubmatrix(N/2,0,N/2);
- Matrix b22 = b.getSubmatrix(N/2,N/2,N/2);
- if(isStrassen) {
- Matrix m1 = a11.DC(b12.sub(b22),stop,isStrassen); System.out.println(m1.elementSum());
- Matrix m2 = (a11.sum(a12)).DC(b22,stop,isStrassen); System.out.println(m2.elementSum());
- Matrix m3 = (a21.sum(a22)).DC(b11,stop,isStrassen); System.out.println(m3.elementSum());
- Matrix m4 = a22.DC(b21.sub(b11),stop,isStrassen); System.out.println(m4.elementSum());
- Matrix m5 = (a11.sum(a22)).DC(b11.sum(b22),stop,isStrassen); System.out.println(m5.elementSum());
- Matrix m6 = (a12.sub(a22)).DC(b21.sum(b22),stop,isStrassen); System.out.println(m6.elementSum());
- Matrix m7 = (a11.sub(a21)).DC(b11.sum(b12),stop,isStrassen); System.out.println(m7.elementSum());
- //Conquer
- c.putSubmatrix(0,0,(m5.sum(m4.sub(m2))).sum(m6));
- c.putSubmatrix(0,N/2,m1.sum(m2));
- c.putSubmatrix(N/2,0,m3.sum(m4));
- c.putSubmatrix(N/2,N/2,((m1.sum(m5).sub(m3)).sub(m7)));
- return c;
- }
- else {
- Matrix m1 = a11.DC(b11, stop,isStrassen); System.out.println(m1.elementSum());
- Matrix m2 = a12.DC(b21, stop,isStrassen); System.out.println(m2.elementSum());
- Matrix m3 = a11.DC(b12, stop,isStrassen); System.out.println(m3.elementSum());
- Matrix m4 = a12.DC(b22,stop,isStrassen); System.out.println(m4.elementSum());
- Matrix m5 = a21.DC(b11, stop,isStrassen); System.out.println(m5.elementSum());
- Matrix m6 = a22.DC(b21, stop,isStrassen); System.out.println(m6.elementSum());
- Matrix m7 = a21.DC(b12, stop,isStrassen); System.out.println(m7.elementSum());
- Matrix m8 = a22.DC(b22, stop,isStrassen); System.out.println(m8.elementSum());
- //Conquer
- c.putSubmatrix(0, 0, m1.sum(m2));
- c.putSubmatrix(0, N/2, m3.sum(m4));
- c.putSubmatrix(N/2,0,m5.sum(m6));
- c.putSubmatrix(N/2,N/2,m7.sum(m8));
- return c;
- }
- }
- }
- public class Naloga2 {
- static int n1, m1, n2, m2, stop;
- static Matrix a, b,result;
- static String in;
- static void read() {
- Scanner sc = new Scanner(System.in);
- in = sc.next();
- if(!in.equals("os")) stop = sc.nextInt();
- n1 = sc.nextInt(); m1 = sc.nextInt();
- a = new Matrix(n1,m1);
- a.init(sc);
- n2 = sc.nextInt(); m2 = sc.nextInt();
- b = new Matrix(n2,m2);
- b.init(sc);
- sc.close();
- }
- static void solve() {
- Matrix c = new Matrix(n1);
- if(in.equals("os")) c = a.naiveMultiply(b);
- else if(in.equals("bl")) {
- fix2();
- return;
- }
- else {
- fix();
- c = a.DC(b,stop,in.contentEquals("st"));
- }
- c.printMatrix();
- }
- static void fix2() {
- int l = n1, m = n2, r = m2;
- while(n1%stop!=0) n1++;
- while(n2%stop!=0) n2++;
- while(m1%stop!=0) m1++;
- while(m2%stop!=0) m2++;
- a.fix2(n1,n2);
- b.fix2(m1, m2);
- Matrix c = new Matrix(n1);
- c = a.block2(l,m,r,b,stop);
- for(int i=0;i<l;i++,System.out.println())
- for(int j=0;j<r;System.out.printf("%d ",c.mat[i][j]),j++);
- }
- static void fix() {
- int newDim = Math.max(Math.max(n1, m1),Math.max(n2,m2));
- while(!((newDim & (newDim-1)) == 0)) newDim++;
- a.fix(newDim); b.fix(newDim);
- }
- public static void main(String[] args) {
- read();
- solve();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement