8.斐波那契数列
题目描述
大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。
n<=39
本题知识点： 递归
斐波那契
斐波那契数列来源于兔子繁殖问题，所以也叫兔子序列。指的是这样一个数列：1、1、2、3、5、8、13、21、34、……在数学上，斐波那契数列以如下被以递推的方法定义：F(1)=1，F(2)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 3，n ∈ N*）
递归实现
解题思路
递归实现就是套用 公式F(1)=1，F(2)=1,当n>=3时：F(n)=F(n - 1)+F(n - 2) 来实现的。
递归n次，时间复杂度O(2^n)
代码实现
java 代码
/**
* 递归求斐波那契数列
*
* @param n
* @return
*/
public int fibonacci(int n) {
if (n == 0) {
return 0;
} else if (n == 1 || n == 2) {
return 1;
}
return fibonacci(n - 1) + fibonacci(n - 2);
}
public static void main(String[] args){
System.out.println(fibonacci(6));
}Kotlin 代码
/**
* 递归求斐波那契数列
*
* @param n
* @return
*/
fun fibonacci(n: Int): Int {
if (n == 0) {
return 0
} else if (n == 1 || n == 2) {
return 1
}
return fibonacci(n - 1) + fibonacci(n - 2)
}
/**
* 入口函数
*/
fun main(args: Array<String>) {
println(fibonacci(6))
}
动态规划（迭代）实现
解题思路
因为斐波那契数列可以从左到右顺序的求出每一项的值，因此只需要顺序计算到n项即可，时间复杂度为O(n)的
代码实现
java 代码
/**
* 循环求斐波那契数列
*
* @param n
* @return
*/
public int fibonacci(int n) {
int a = 1, b = 1, c = 0;
if (n == 0) {
return 0;
} else if (n == 1 || n == 2) {
return 1;
} else {
for (int i = 3; i <= n; i++) {
c = a + b;
a = b;
b = c;
}
}
return c;
}
public static void main(String[] args){
System.out.println(fibonacci(6));
}Kotlin 代码
/**
* 循环求斐波那契数列
*
* @param n
* @return
*/
fun fibonacci(n: Int): Int {
var a = 1
var b = 1
var c = 0
if (n == 0) {
return 0
} else if (n == 1 || n == 2) {
return 1
} else {
for (i in 3..n) {
c = a + b
a = b
b = c
}
}
return c
}
/**
* 入口函数
*/
fun main(args: Array<String>) {
println(fibonacci(6))
}
状态矩阵相乘求法
矩阵乘法
一个 m * p 的矩阵和一个 p * n的矩阵相乘得到一个 m * n的矩阵
\begin{bmatrix}
a&b \\
c&d \\
\end{bmatrix}
\begin{bmatrix}
e&f \\
g&h \\
\end{bmatrix}
=
\begin{bmatrix}
ae+bg&af+bh \\
ce+dg&cf+dh \\
\end{bmatrix}解题思路
这是一个时间复杂度为O(log n)的算法。因为斐波那契数列在n大于等于三的时候严格遵守递推数列f(n) = f(n-1) + f(n-2)，而对于一个二阶的递推数列来说，我们可以用矩阵乘法来表示，且状态矩阵是2阶的方阵：
实现的推导原理如下：
数列的递推公式为：f(0)=0,f(1)=1，f(2)=2，
用矩阵表示为：
\begin{bmatrix}
f(n) \\
f(n-1) \\
\end{bmatrix}
=
\begin{bmatrix}
1&1 \\
1&0 \\
\end{bmatrix}
\begin{bmatrix}
f(n-1) \\
f(n-2) \\
\end{bmatrix}进一步，可以得出直接推导公式：
\begin{bmatrix}
f(n+1) \\
f(n) \\
\end{bmatrix}
=
\begin{bmatrix}
1&1 \\
1&0 \\
\end{bmatrix}
\begin{bmatrix}
f(n) \\
f(n-1) \\
\end{bmatrix}
=
\begin{bmatrix}
1&1 \\
1&0 \\
\end{bmatrix}^2
\begin{bmatrix}
f(n-1) \\
f(n-2) \\
\end{bmatrix}
=
...
=
\begin{bmatrix}
1&1 \\
1&0 \\
\end{bmatrix}^{n-1}
\begin{bmatrix}
f(2) \\
f(1) \\
\end{bmatrix}
=
\begin{bmatrix}
1&1 \\
1&0 \\
\end{bmatrix}^n
\begin{bmatrix}
f(1) \\
f(0) \\
\end{bmatrix}
=
\begin{bmatrix}
1&1 \\
1&0 \\
\end{bmatrix}^n
\begin{bmatrix}
1 \\
0 \\
\end{bmatrix}也可以推导为：
\begin{bmatrix}
f(n+1)&f(n)\\
f(n)&f(n-1)
\end{bmatrix}
=
\begin{bmatrix}
1&1 \\
1&0 \\
\end{bmatrix}^n
=
\begin{bmatrix}
1&1 \\
1&0 \\
\end{bmatrix}
\begin{bmatrix}
1&1 \\
1&0 \\
\end{bmatrix}
...
\begin{bmatrix}
1&1 \\
1&0 \\
\end{bmatrix}
（不是很懂）
代码实现
java 代码
/**
* 采用矩阵的解法
* 时间复杂度为O(logN)
*
* @param n
* @return
*/
public int fibonacci(int n) {
if (n == 0) {
return 0;
}
int[][] fbnq = fbnq(n);
return fbnq[1][0];
}
/**
* 单元矩阵
*/
private static final int[][] UNIT = {{1, 1}, {1, 0}};
/**
* 矩阵求斐波那契
*
* @param n
* @return
*/
private int[][] fbnq(int n) {
if (n == 1) {
return UNIT;
}
if (n % 2 == 0) {
int[][] matrix = fbnq(n / 2);
//相当于矩阵的n次幂(A^n/2 * A^n/2 = A^(n/2+n/2) = A^n
return matrixMultiply(matrix, matrix);
} else {
int[][] matrix = fbnq((n - 1) / 2);
//相当于矩阵的n次幂(A^(n-1)/2 * A^(n-1)/2 = A^((n-1)/2+(n-1)/2+1) = A^n
return matrixMultiply(UNIT, matrixMultiply(matrix, matrix));
}
}
/**
* 矩阵乘法
*
* @param a 相乘的矩阵a
* @param b 相乘的矩阵b
* @return 矩阵相乘的结果
*/
private static int[][] matrixMultiply(int[][] a, int[][] b) {
int rows = a.length;
int cols = b[0].length;
int[][] matrix = new int[rows][cols];
for (int i = 0; i < a.length; i++) {
for (int j = 0; j < b[0].length; j++) {
for (int k = 0; k < a[i].length; k++) {
matrix[i][j] += a[i][k] * b[k][j];
}
}
}
return matrix;
}
public static void main(String[] args){
System.out.println(fibonacci(6));
}Kotlin 代码
/**
* 采用矩阵的解法
* 时间复杂度为O(logN)
*
* @param n
* @return
*/
private fun fibonacci(n: Int): Int {
if (n <= 2) {
return 1
}
val arr = fbnq(n);
return arr[0][1]
}
/**
* 单元矩阵
*/
private val UNIT = arrayOf(intArrayOf(1, 1), intArrayOf(1, 0))
/**
* 矩阵求斐波那契
*
* @param n
* @return
*/
private fun fbnq(n: Int): Array<IntArray> {
if (n == 1) {
return UNIT
}
if (n % 2 == 0) {
val matrix = fbnq(n / 2)
return matrixMultiply(matrix, matrix)
} else {
val matrix = fbnq((n-1) / 2)
return matrixMultiply(UNIT,matrixMultiply(matrix, matrix))
}
}
/**
* 矩阵乘法
*
* @param a 相乘的矩阵a
* @param b 相乘的矩阵b
* @return 矩阵相乘的结果
*/
private fun matrixMultiply(a: Array<IntArray>, b: Array<IntArray>): Array<IntArray> {
val row = a.size
val col = b[0].size
val matrix = Array<IntArray>(row) { IntArray(col) }
for (i in 0 until row) {
for (j in 0 until col) {
for (k in a[i].indices) {
matrix[i][j] += a[i][k]*b[k][j]
}
}
}
return matrix
}
/**
* 入口函数
*/
fun main(args: Array<String>) {
println(fibonacci(6))
}
引用声明
该题目引用自
牛客网