小型网站项目策划书,wordpress閱讀主题,做市级网站需要什么,郑州网站制作哪家便宜之前写了一篇从斐波那契数列分析递归与动态规划#xff08;JAVA#xff09;来优化斐波那契数列#xff0c;这样可以使算法的时间复杂度从O(n^2)变到O(n),这是使用递归公式f(n)f(n-1)f(n-2)求斐波那契数列的最优算法#xff0c;但是这只是一维世界下的极限。下面我们将其从一…之前写了一篇从斐波那契数列分析递归与动态规划JAVA来优化斐波那契数列这样可以使算法的时间复杂度从O(n^2)变到O(n),这是使用递归公式f(n)f(n-1)f(n-2)求斐波那契数列的最优算法但是这只是一维世界下的极限。下面我们将其从一维上升到二维用二阶矩阵推导斐波那契数列该算法的复杂度为O(logn)。
矩阵定义一个m*n的矩阵是一个由m行n列元素排成的矩形阵列。矩阵里的元素可以是数字符号或者数学式.
下面是一个典型的二阶矩阵二阶矩阵的乘法高效幂运算第一种方法在高效幂运算JAVA中有类似的描述虽然本文中是对矩阵进行幂运算实质是一样的
第二种方法利用位运算转换成二进制处理
斐波那契数列的矩阵算法import java.util.Scanner;/*** [F(n1) F(n)] [1 1 ]^n| | | |[F(n) F(n-1)] [1 0 ]* */
public class Main {// 公式矩阵 private static final int[][] UNIT {{1, 1}, {1, 0}};// 零矩阵 private static final int[][] ZERO {{0, 0}, {0, 0}};public static void main(String[] args) {Scanner in new Scanner(System.in);int n in.nextInt();int[][] m fb(n);System.out.println(m[0][1]);}/*** 利用二进制进行高效幂运算* 求斐波那契数列* */public static int[][] fb(int n) {if (n 0) {return ZERO;}if (n 1) {return UNIT;}if (n%2 0) {System.out.println(n 1);int[][] matrix fb(n 1);return Multiply(matrix, matrix);} else {int[][] matrix fb((n - 1) 1);return Multiply(Multiply(matrix, matrix), UNIT);}}/*** 矩阵乘法* */public static int[][] Multiply(int[][] m, int[][] n) {/*** 对于斐波那契数列来说行和列都是2这样写更易于理解下面也给出了标准的矩阵乘法算法是通用的* 用到此算法除非进行算法学习和研究否则一般都是进行较大数据的斐波那契求值所以对结果取(10e9)7的模* */int[][] r new int[2][2];r[0][0] (m[0][0]*n[0][0] m[0][1]*n[1][0])%1000000007;r[0][1] (m[0][0]*n[0][1] m[0][1]*n[1][1])%1000000007;r[1][0] (m[1][0]*n[0][0] m[1][1]*n[1][0])%1000000007;r[1][1] (m[1][0]*n[0][1] m[1][1]*n[1][1])%1000000007;return r;}
}标准矩阵乘法算法public static int[][] Multiply(int[][] m, int[][] n) {
// 标准计算矩阵乘法算法int rows m.length;int cols n[0].length;int[][] r new int[rows][cols];for (int i 0; i rows; i) {for (int j 0; j cols; j) {r[i][j] 0;for (int k 0; k m[i].length; k) {r[i][j] m[i][k] * n[k][j];}}}return r;}
}
