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的矩阵

[abcd][efgh]=[ae+bgaf+bhce+dgcf+dh]\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,
用矩阵表示为:

[f(n)f(n1)]=[1110][f(n1)f(n2)]\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}

进一步,可以得出直接推导公式:

[f(n+1)f(n)]=[1110][f(n)f(n1)]=[1110]2[f(n1)f(n2)]=...=[1110]n1[f(2)f(1)]=[1110]n[f(1)f(0)]=[1110]n[10]\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}

也可以推导为:

[f(n+1)f(n)f(n)f(n1)]=[1110]n=[1110][1110]...[1110]\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))
}

引用声明

该题目引用自
牛客网