【数据结构】——斐波那契数列

最新推荐文章于 2025-02-05 10:54:23 发布

mbtlami

最新推荐文章于 2025-02-05 10:54:23 发布

阅读量1.8k

点赞数

分类专栏：数据结构

本文链接：https://blog.csdn.net/tang_2214/article/details/96306859

版权

数据结构专栏收录该内容

4 篇文章

订阅专栏

求斐波那契数列的第N项。

斐波那契数列指的是这样一个数列 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233，377，610，987，1597，2584，4181，6765，10946，17711，28657，46368…

这个数列从第3项开始，每一项都等于前两项之和。
$\begin{cases} 0 & \text{n=0} \\[2ex] 1 & \text{n=1}\\[2ex] f(n-1)+f(n-2) & \text{n>1} \end{cases}$

解决方案1：递归

    /**
     * 递归
     *
     * @param n 第N项
     * @return 结果：当n=0为0，当n=1为1
     */
    private static long recursiveFibonacci(int n) {
        if (n <= 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        return recursiveFibonacci(n - 1) + recursiveFibonacci(n - 2);
    }

解决方案2：顺序循环递推求解，时间复杂度 O(n)

    /**
     * 顺序循环递推求解
     */
    private static long cycleFibonacci(int n) {
        if (n <= 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        int n0 = 0;
        int n1 = 1;
        int fibN = 0;
        for (int i = 2; i <= n; i++) {
            fibN = n0 + n1;
            n0 = n1;
            n1 = fibN;
        }
        return fibN;
    }

解决方案3：公式求解

    /**
     * 公式求解
     */
    private static long formulaFibonacci(int n) {
        double temp = Math.sqrt(5.0);
        double result = (Math.pow((1 + temp) / 2, n) - Math.pow((1 - temp) / 2, n)) / temp;
        return (long) result;
    }

解决方案4：矩阵求解
有一个数学公式：

$\begin{Bmatrix}f(n) & f(n-1) \\ f(n-1) & f(n-2)\\ \end{Bmatrix}$ = $\begin{Bmatrix}1 & 1 \\ 1 & 0\\ \end{Bmatrix}$ ^n-1

证明此公式：

n=2 时 $\begin{Bmatrix}f(2) & f(1) \\ f(1) & f(0)\\ \end{Bmatrix}$ = $\begin{Bmatrix}1 & 1 \\ 1 & 0\\ \end{Bmatrix}$

$\begin{Bmatrix}f(n) & f(n-1) \\ f(n-1) & f(n-2)\\ \end{Bmatrix}$ = $\begin{Bmatrix}f(n-1) & f(n-2) \\ f(n-2) & f(n-3)\\ \end{Bmatrix}$ * $\begin{Bmatrix}1 & 1 \\ 1 & 0\\ \end{Bmatrix}$

$\begin{Bmatrix}f(n) & f(n-1) \\ f(n-1) & f(n-2)\\ \end{Bmatrix}$ = $\begin{Bmatrix}f(n-2) & f(n-3) \\ f(n-3) & f(n-4)\\ \end{Bmatrix}$ * $\begin{Bmatrix}1 & 1 \\ 1 & 0\\ \end{Bmatrix}$ ²

$\begin{Bmatrix}f(n) & f(n-1) \\ f(n-1) & f(n-2)\\ \end{Bmatrix}$ = $\begin{Bmatrix}f(2) & f(1) \\ f(1) & f(0)\\ \end{Bmatrix}$ * $\begin{Bmatrix}1 & 1 \\ 1 & 0\\ \end{Bmatrix}$ ^n-2

$\begin{Bmatrix}f(n) & f(n-1) \\ f(n-1) & f(n-2)\\ \end{Bmatrix}$ = $\begin{Bmatrix}1 & 1 \\ 1 & 0\\ \end{Bmatrix}$ ^n-1

    /**
     * 矩阵求解
     */
    private static long matrixFibonacci(int n) {
        if (n <= 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        int[][] matrix = INIT;
        while (n-- - 2 > 0) {
            matrix = matrixMultiply(matrix, INIT);
        }
        //最终结果为矩阵相乘之后的第一个元素
        return matrix[0][0];
    }

解决方案5：递归矩阵
利用乘方的特性，时间复杂度O(logn)
在这里插入图片描述

    /**
     * 递归矩阵
     */
    private static int[][] recursiveMatrixFibonacci(int n) {
        if (n <= 0) {
            return new int[][]{{0, 0}, {0, 0}};
        }
        if (n == 1) {
            return INIT;
        }
        // n是偶数
        if ((n & 1) == 0) {
            int[][] matrix = recursiveMatrixFibonacci(n >> 1);
            return matrixMultiply(matrix, matrix);
        }
        // n是奇数
        int[][] matrix = recursiveMatrixFibonacci((n - 1) >> 1);
        return matrixMultiply(matrixMultiply(matrix, matrix), INIT);
    }

解决方案6：优化矩阵求解，不使用递归

    /**
     * 优化矩阵求解
     */
    private static long advancedMatrixFibonacci(int n) {
        if (n <= 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        int[][] temp = INIT;
        // 单位矩阵
        int[][] result = {{1, 0}, {0, 1}};
        int m = n - 1;
        while (m > 0) {
            if ((m & 1) == 1) {
                result = matrixMultiply(temp, result);
            }
            temp = matrixMultiply(temp, temp);
            m >>= 1;
        }
        return result[0][0];
    }

public class Fibonacci {

    /**
     * f(n) = INIT矩阵的(n-1)次方
     */
    private static final int[][] INIT = {{1, 1}, {1, 0}};

    public static void main(String[] args) {
        int[] nums = new int[]{0, 10, 11};
        for (int num : nums) {
            System.out.println(recursiveFibonacci(num));
            System.out.println(cycleFibonacci(num));
            System.out.println(formulaFibonacci(num));
            System.out.println(matrixFibonacci(num));
            int[][] m = recursiveMatrixFibonacci(num);
            System.out.println(m[0][1]);
            System.out.println(advancedMatrixFibonacci(num));
            System.out.println("--------------");
        }
    }

    /**
     * 矩阵相乘
     *
     * @param m r1*c1
     * @param n c1*c2
     * @return 新矩阵, r1*c2
     */
    private static int[][] matrixMultiply(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;
    }
}