斐波那契矩阵乘法应用

叁歲伎倆 2024-04-03 11:11 63阅读 0赞

## 斐波那契矩阵乘法应用 ##

### 1 斐波那契数列 ###

1）斐波那契数列的线性求解（O(N)）的方式非常好理解
     
    2）同时利用线性代数，也可以改写出另一种表示
    
     | F(N) , F(N-1) | = | F(2), F(1) |  *  某个二阶矩阵的N-2次方
    
    3）求出这个二阶矩阵，进而最快求出这个二阶矩阵的N-2次方
    
    "类似斐波那契数列递归优化":
    如果某个递归，除了初始项之外，具有如下的形式
    
    F(N) = C1 * F(N) + C2 * F(N-1) + … + Ck * F(N-k) ( C1…Ck 和k都是常数)
    
    并且这个递归的表达式是严格的、不随条件转移的
    
    那么都存在类似斐波那契数列的优化，时间复杂度都能优化成O(logN)

> O(N)求法与 O(logN)求法

public class FibonacciProblem {
        
    
    	public static int f1(int n) {
        
    		if (n < 1) {
        
    			return 0;
    		}
    		if (n == 1 || n == 2) {
        
    			return 1;
    		}
    		return f1(n - 1) + f1(n - 2);
    	}
    
    	public static int f2(int n) {
        
    		if (n < 1) {
        
    			return 0;
    		}
    		if (n == 1 || n == 2) {
        
    			return 1;
    		}
    		int res = 1;
    		int pre = 1;
    		int tmp = 0;
    		for (int i = 3; i <= n; i++) {
        
    			tmp = res;
    			res = res + pre;
    			pre = tmp;
    		}
    		return res;
    	}
    
    	// O(logN)
    	public static int f3(int n) {
        
    		if (n < 1) {
        
    			return 0;
    		}
    		if (n == 1 || n == 2) {
        
    			return 1;
    		}
    		// [ 1 ,1 ]
    		// [ 1, 0 ]
    		int[][] base = {
         
    				{
         1, 1 }, 
    				{
         1, 0 } 
    				};
    		int[][] res = matrixPower(base, n - 2);
    		return res[0][0] + res[1][0];
    	}
    
    	public static int[][] matrixPower(int[][] m, int p) {
        
    		int[][] res = new int[m.length][m[0].length];
    		for (int i = 0; i < res.length; i++) {
        
    			res[i][i] = 1;
    		}
    		// res = 矩阵中的1
    		int[][] t = m;// 矩阵1次方
    		for (; p != 0; p >>= 1) {
        
    			if ((p & 1) != 0) {
        
    				res = product(res, t);
    			}
    			t = product(t, t);
    		}
    		return res;
    	}
    
    	// 两个矩阵乘完之后的结果返回
    	public static int[][] product(int[][] a, int[][] b) {
        
    		int n = a.length;
    		int m = b[0].length;
    		int k = a[0].length; // a的列数同时也是b的行数
    		int[][] ans = new int[n][m];
    		for(int i = 0 ; i < n; i++) {
        
    			for(int j = 0 ; j < m;j++) {
        
    				for(int c = 0; c < k; c++) {
        
    					ans[i][j] += a[i][c] * b[c][j];
    				}
    			}
    		}
    		return ans;
    	}
    
    	public static int s1(int n) {
        
    		if (n < 1) {
        
    			return 0;
    		}
    		if (n == 1 || n == 2) {
        
    			return n;
    		}
    		return s1(n - 1) + s1(n - 2);
    	}
    
    	public static int s2(int n) {
        
    		if (n < 1) {
        
    			return 0;
    		}
    		if (n == 1 || n == 2) {
        
    			return n;
    		}
    		int res = 2;
    		int pre = 1;
    		int tmp = 0;
    		for (int i = 3; i <= n; i++) {
        
    			tmp = res;
    			res = res + pre;
    			pre = tmp;
    		}
    		return res;
    	}
    
    	public static int s3(int n) {
        
    		if (n < 1) {
        
    			return 0;
    		}
    		if (n == 1 || n == 2) {
        
    			return n;
    		}
    		int[][] base = {
         {
         1, 1 }, {
         1, 0 } };
    		int[][] res = matrixPower(base, n - 2);
    		return 2 * res[0][0] + res[1][0];
    	}
    
    	public static int c1(int n) {
        
    		if (n < 1) {
        
    			return 0;
    		}
    		if (n == 1 || n == 2 || n == 3) {
        
    			return n;
    		}
    		return c1(n - 1) + c1(n - 3);
    	}
    
    	public static int c2(int n) {
        
    		if (n < 1) {
        
    			return 0;
    		}
    		if (n == 1 || n == 2 || n == 3) {
        
    			return n;
    		}
    		int res = 3;
    		int pre = 2;
    		int prepre = 1;
    		int tmp1 = 0;
    		int tmp2 = 0;
    		for (int i = 4; i <= n; i++) {
        
    			tmp1 = res;
    			tmp2 = pre;
    			res = res + prepre;
    			pre = tmp1;
    			prepre = tmp2;
    		}
    		return res;
    	}
    
    	public static int c3(int n) {
        
    		if (n < 1) {
        
    			return 0;
    		}
    		if (n == 1 || n == 2 || n == 3) {
        
    			return n;
    		}
    		int[][] base = {
         
    				{
         1, 1, 0 }, 
    				{
         0, 0, 1 }, 
    				{
         1, 0, 0 } };
    		int[][] res = matrixPower(base, n - 3);
    		return 3 * res[0][0] + 2 * res[1][0] + res[2][0];
    	}
    
    	public static void main(String[] args) {
        
    		int n = 19;
    		System.out.println(f1(n));
    		System.out.println(f2(n));
    		System.out.println(f3(n));
    		System.out.println("===");
    
    		System.out.println(s1(n));
    		System.out.println(s2(n));
    		System.out.println(s3(n));
    		System.out.println("===");
    
    		System.out.println(c1(n));
    		System.out.println(c2(n));
    		System.out.println(c3(n));
    		System.out.println("===");
    
    	}
    
    }

### 2 0字符左边挨着1 ###

public class ZeroLeftOneStringNumber {
        
    
    	public static int getNum1(int n) {
        
    		if (n < 1) {
        
    			return 0;
    		}
    		return process(1, n);
    	}
    
    	public static int process(int i, int n) {
        
    		if (i == n - 1) {
        
    			return 2;
    		}
    		if (i == n) {
        
    			return 1;
    		}
    		return process(i + 1, n) + process(i + 2, n);
    	}
    
    	public static int getNum2(int n) {
        
    		if (n < 1) {
        
    			return 0;
    		}
    		if (n == 1) {
        
    			return 1;
    		}
    		int pre = 1;
    		int cur = 1;
    		int tmp = 0;
    		for (int i = 2; i < n + 1; i++) {
        
    			tmp = cur;
    			cur += pre;
    			pre = tmp;
    		}
    		return cur;
    	}
    
    	public static int getNum3(int n) {
        
    		if (n < 1) {
        
    			return 0;
    		}
    		if (n == 1 || n == 2) {
        
    			return n;
    		}
    		int[][] base = {
         {
         1, 1 }, {
         1, 0 } };
    		int[][] res = matrixPower(base, n - 2);
    		return 2 * res[0][0] + res[1][0];
    	}
    	
    	
    	
    	
    	
    	
    	public static int fi(int n) {
        
    		if (n < 1) {
        
    			return 0;
    		}
    		if (n == 1 || n == 2) {
        
    			return 1;
    		}
    		int[][] base = {
         {
         1, 1 }, 
    				         {
         1, 0 } };
    		int[][] res = matrixPower(base, n - 2);
    		return res[0][0] + res[1][0];
    	}
    
    	
    	
    	
    	public static int[][] matrixPower(int[][] m, int p) {
        
    		int[][] res = new int[m.length][m[0].length];
    		for (int i = 0; i < res.length; i++) {
        
    			res[i][i] = 1;
    		}
    		int[][] tmp = m;
    		for (; p != 0; p >>= 1) {
        
    			if ((p & 1) != 0) {
        
    				res = product(res, tmp);
    			}
    			tmp = product(tmp, tmp);
    		}
    		return res;
    	}
    
    	// 两个矩阵乘完之后的结果返回
    	public static int[][] product(int[][] a, int[][] b) {
        
    		int n = a.length;
    		int m = b[0].length;
    		int k = a[0].length; // a的列数同时也是b的行数
    		int[][] ans = new int[n][m];
    		for(int i = 0 ; i < n; i++) {
        
    			for(int j = 0 ; j < m;j++) {
        
    				for(int c = 0; c < k; c++) {
        
    					ans[i][j] += a[i][c] * b[c][j];
    				}
    			}
    		}
    		return ans;
    	}
    
    	public static void main(String[] args) {
        
    		for (int i = 0; i != 20; i++) {
        
    			System.out.println(getNum1(i));
    			System.out.println(getNum2(i));
    			System.out.println(getNum3(i));
    			System.out.println("===================");
    		}
    
    	}
    }

> 跳台阶、不死神兔（母牛问题）、 铺瓷砖都可以用斐波那契数列矩阵乘法求解