package dataStructures; class Matrix { private static int nDigits(int n) { boolean signal = n<0; if (n==0) return 1; return ((int)Math.ceil(Math.log(Math.abs(n)+1) / Math.log(10))) + (signal?1:0); } public static void printMatrix( int[][] m) { //find maximum length int max=0; for (int i=0;ii) { int [][] X = ordMultMatrix(A,s,i,s[i][j]); int [][] Y = ordMultMatrix(A,s,s[i][j]+1,j); int [][] Z = new int[X.length][Y[0].length]; multMatrix(X,Y,Z); return Z; } return A[i]; } /////////////////////////////////////////// public static long fib1( int n ) { long[] solutions = new long[n+1]; solutions[0] = 1; solutions[1] = 1; for(int i=2;i<=n;i++) solutions[i] = solutions[i-2] + solutions[i-1]; return solutions[n]; } //******************************* private static final int UNKNOWN = -1; public static long fib(int n) { long[] sols = new long[n+1]; for(int i=0;i<=n;i++) sols[i] = UNKNOWN; return fib(sols,n); } public static long fib( long[] sols, int n ) { if (sols[n] != UNKNOWN) return sols[n]; if (n==0 || n==1) return sols[n] = 1; return sols[n] = fib(sols,n-1) + fib(sols,n-2); } /////////////////////////////////////////// private static int[][] lcsMatrix(String a, String b) { int[][] m = new int[a.length()+1][b.length()+1]; for(int i=1;i<=a.length();i++) for(int j=1;j<=b.length();j++) if (a.charAt(i-1)==b.charAt(j-1)) m[i][j] = m[i-1][j-1] + 1; else m[i][j] = m[i-1][j] >= m[i][j-1] ? m[i-1][j] : m[i][j-1]; return m; } // using memoization private static int[][] lcsMatrix2(String a, String b) { int[][] sols = new int[a.length()+1][b.length()+1]; for(int i=0;i<=a.length();i++) for(int j=0;j<=b.length();j++) sols[i][j] = UNKNOWN; lcsMatrix2Aux(sols,a,b,a.length(),b.length()); return sols; } private static int lcsMatrix2Aux(int[][] sols, String a, String b, int n, int m) { if (sols[n][m] != UNKNOWN) return sols[n][m]; if (n==0 || m==0) return sols[n][m] = 0; if (a.charAt(n-1)==b.charAt(m-1)) sols[n][m] = 1+lcsMatrix2Aux(sols,a,b,n-1,m-1); else { int n1 = lcsMatrix2Aux(sols,a,b,n,m-1), m1 = lcsMatrix2Aux(sols,a,b,n-1,m); sols[n][m] = n1>m1 ? n1 : m1; } return sols[n][m]; } //*************************** private static String getLcsAux(String a, int[][] m, int i, int j) { if (i==0 || j==0) return ""; if ((m[i][j] == m[i-1][j-1] + 1) && (m[i][j] > m[i-1][j]) && (m[i][j] > m[i][j-1])) return getLcsAux(a,m,i-1,j-1) + a.charAt(i-1); else if (m[i-1][j] >= m[i][j-1]) return getLcsAux(a,m,i-1,j); else return getLcsAux(a,m,i,j-1); } public static String getLcs(String a, String b) { return getLcsAux(a,lcsMatrix2(a,b),a.length(),b.length()); } //******************************* static int now; private static void permutations(String original, char[] s, int k) { now++; s[k] = original.charAt(now); if (now+1==s.length) // print permutation System.out.print(String.valueOf(s)); for(int t=1;t=moves[j] && !s[i-moves[j]]) { s[i] = true; break; } } return s[N]; } /** * Verifica se o proximo jogador ganha - SOLUÇAO EXPONENCIAL * @param N O número de pedras inicial da mesa * @param moves Quais as jogadas possíveis (inclui 1) * @return TRUE se o proximo jogador ganha, FALSE c.c. */ public static boolean bachet2(int N, int[] moves) { for(int i=0;i=moves[i] && !bachet2(N-moves[i],moves))) return true; return false; } /** * Verifica se o proximo jogador ganha - SOLUÇAO COM MEMORIZAÇÃO * @param N O número de pedras inicial da mesa * @param moves Quais as jogadas possíveis (inclui 1) * @return TRUE se o proximo jogador ganha, FALSE c.c. */ public static boolean bachet3(int N, int[] moves) { int[] sols = new int[N+1]; for(int i=0;i<=N;i++) sols[i] = UNKNOWN; boolean b = b3(N,moves,sols); for(int i=0;i=moves[i] && !b3(N-moves[i],moves,sols))) { sols[N] = 1; return true; } sols[N] = 0; return false; } //******************************* public static void main(String[] args) { int[] m = {4, 7}; bachet3(12,m); /* for (int i=1;i<10;i++) { System.out.print((bachet(i,m)?"Primeiro":"Segundo")); System.out.print((bachet2(i,m)?"/Primeiro":"/Segundo")); System.out.println((bachet3(i,m)?"/Primeiro":"/Segundo")); } */ // showPermutations("abcd"); // System.out.println(fib(2)); /* int[][] A0 = { {0,1,2}, {1,2,3} }; //2x3 int[][] A1 = { {0,1,2}, {1,2,3}, {2,3,4} }; //3x3 int[][] A2 = { {0,1,2,3}, {1,2,3,4}, {2,3,4,5} }; //3x4 int[][] A3 = { {1,2,3}, {2,3,4}, {3,4,5}, {4,5,6} }; //4x3 int[][] A4 = { {1,2}, {2,3}, {3,4} }; //3x2 int[] r = {2, 3, 3, 4, 3, 2}; //2x3 3x3 3x4 4x3 3x2 int[][] s = new int[r.length-1][r.length-1]; System.out.println(ordMatrix(r,s)); int[][][] A = { A0, A1, A2, A3, A4 }; int[][] R = ordMultMatrix(A,s,0,3); */ // printMatrix(lcsMatrix("abcdefghijklmnopqsrtuv","beghijkmnoooo")); /* String a = "abcdefg"; String b = "efaefg"; int s[][]; s = lcsMatrix(a,b); printMatrix(s); s = lcsMatrix2(a,b); printMatrix(s); System.out.println(getLcs(a,b)); */ System.out.println(fib1(100) + ":" + fib(100)); } }