【相当困难】斐波那契系列问题的递归和动态规划－Java：补充题目２

分享一个大牛的人工智能教程。零基础！通俗易懂！风趣幽默！希望你也加入到人工智能的队伍中来！请轻击人工智能教程大家好！欢迎来到我的网站！ 人工智能被认为是一种拯救世界、终结世界的技术。毋庸置疑，人工智能时代就要来临了，科… 继续阅读 前言https://www.captainai.net/troubleshooter

package live.every.day.ProgrammingDesign.CodingInterviewGuide.RecursionAndDynamicPrograming; /** * 斐波那契系列问题的递归和动态规划 * * 【题目】 * 给定整数N，返回斐波那契数列的第N项。 * * 【补充题目１】 * 给定整数N，代表台阶数，一次可以跨２个或者１个台阶，返回有多少种走法。 * * 【补充题目２】 * 假设农场中成熟的母牛每年只会生１头小母牛，并且永远不会死。第一年农场有１只成熟的母牛，从第二年开始，母牛开始生小母牛。 * 每只小母牛３年之后成熟又可以生小母牛。给定整数N，求出N年后牛的数量。 * * 【要求】 * 对以上所有的问题，请实现时间复杂度O(logN)的解法。 * * 【难度】 * 相当困难 * * 【解答】 * 补充问题２。 * * 所有的牛都不会死，所以第N-1年的牛会毫无损失地活到第N年。同时所有成熟的优缺点都会生出１头新的牛，那么成熟牛的数量如何 * 估计？就是第N-3年的所有牛，到第N年肯定都是成熟的牛，其间出生的牛肯定都没有成熟。所以C(n)=C(n-1)+C(n-3)，初始项为 * C(1)==1，C(2)==2，C(3)==3。这个和斐波那契数列又十分类似，只不过C(n)依赖C(n-1)和C(n-3)的值，而斐波那契数列F(n) * 依赖F(n-1)和F(n-2)的值。同样可以很轻易地写出O(2^N)与O(N)的方法，请参看如下代码中的c1和c2方法。 * * O(logN)的方法。C(n)=C(n-1)+C(n-3)是一个三阶递推数列，一定可以用矩阵乘法的形式表示，且状态矩阵为3x3的矩阵。 * (Cn,Cn-1,Cn-2)=(Cn-1,Cn-2,Cn-3)x|abc,def,ghi| * 把前5项C(1)==1，C(2)==2，C(3)==3，C(4)==4，C(5)==6代入，求出状态矩阵： * |abc,def,ghi|=|110,001,100| * 求矩阵之后，当n>3时，原来的公式可化简为： * (Cn,Cn-1,Cn-2)=(C3,C2,C1)x|110,001,100|^n-3=(3,2,1)x|110,001,100|^n-3 * 接下来的过程又是利用加速矩阵乘法的方式进行实现，具体请参看如下代码中的c3方法。 * * 如果递归式严格符合F(n)=axF(n-1)+bxF(n-2)+...+kxF(n-i)，那么它就是一个i阶的递推式，必然有与ixi的状态矩阵有关的 * 矩阵乘法的表达。一律可以用加速矩阵乘法的动态规划将时间复杂度降为O(logN)。 * * @author Created by LiveEveryDay */ public class FibonacciSeries3 { 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]; } private static int[][] matrixPower(int[][] m, int p) { int[][] res = new int[m.length][m[0].length]; // 先把res设为单位矩阵，相当于整数中的１ 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 = multiMatrix(res, tmp); } tmp = multiMatrix(tmp, tmp); } return res; } private static int[][] multiMatrix(int[][] m1, int[][] m2) { int[][] res = new int[m1.length][m2[0].length]; for (int i = 0; i < m2[0].length; i++) { for (int j = 0; j < m1.length; j++) { for (int k = 0; k < m2.length; k++) { res[i][j] += m1[i][k] * m2[k][j]; } } } return res; } public static void main(String[] args) { int n = 8; System.out.printf("c1: %d%n", c1(n)); System.out.printf("c2: %d%n", c2(n)); System.out.printf("c3: %d%n", c3(n)); } } // ------ Output ------ /* c1: 19 c2: 19 c3: 19 */