wordpress版权信息上方图片,网站内部代码优化,唐山网站制作网络公司,东营网站制作方案斐波那契数#xff0c;通常用 F(n) 表示#xff0c;形成的序列称为斐波那契数列。该数列由 0 和 1 开始#xff0c;后面的每一项数字都是前面两项数字的和。也就是#xff1a;
F(0) 0, F(1) 1 F(N) F(N - 1) F(N - 2), 其中 N 1. 给定 N#xff0c;计算 F(N)。…斐波那契数通常用 F(n) 表示形成的序列称为斐波那契数列。该数列由 0 和 1 开始后面的每一项数字都是前面两项数字的和。也就是
F(0) 0, F(1) 1 F(N) F(N - 1) F(N - 2), 其中 N 1. 给定 N计算 F(N)。
示例 1
输入2 输出1 解释F(2) F(1) F(0) 1 0 1. 示例 2
输入3 输出2 解释F(3) F(2) F(1) 1 1 2. 示例 3
输入4 输出3 解释F(4) F(3) F(2) 2 1 3.
矩阵快速幂
class Solution {int fib(int N) {if (N 1) {return N;}int[][] A new int[][]{{1, 1}, {1, 0}};matrixPower(A, N-1);return A[0][0];}void matrixPower(int[][] A, int N) {if (N 1) {return;}matrixPower(A, N/2);multiply(A, A);int[][] B new int[][]{{1, 1}, {1, 0}};if (N%2 ! 0) {multiply(A, B);}}void multiply(int[][] A, int[][] B) {int x A[0][0] * B[0][0] A[0][1] * B[1][0];int y A[0][0] * B[0][1] A[0][1] * B[1][1];int z A[1][0] * B[0][0] A[1][1] * B[1][0];int w A[1][0] * B[0][1] A[1][1] * B[1][1];A[0][0] x;A[0][1] y;A[1][0] z;A[1][1] w;}
}
