2022-04-26发表2023-05-23更新4 分钟读完 (大约611个字)0次访问

【算法】使用Java实现斐波那契数列的三种方法，太酷啦

InterviewCoder

# 【算法】使用 Java 实现斐波那契数列的三种方法，太酷啦

# Java 实现斐波那契数列的三种方法

什么是斐波那契数列

这里借用一下度娘的一段话：斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家列昂纳多・斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为 “兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……
其规律很明显，从第 3 个数开始，每个数都等于它前两个数的和。
那么通过 java 可以如何实现斐波那契数列呢？这里介绍三种方法。
通过代码实现以下效果：当你输入 n 时，会获取斐波那契数列的第 n 个数的值。

# 1.for 循环实现

public static int fibonacci(int n) {
    if (n <= 1) {
        return n;
    }

   	int[] fib = new int[n+1];
   	fib[0] = 0;
   	fib[1] = 1;

    for (int i = 2; i <= n; i++) {
       fib[i] = fib[i-1] + fib[i-2];
    }

    return fib[n];
}

# 2. 平方根实现

public static int fibonacci(int n) {
     double goldenRatio = (1 + Math.sqrt(5)) / 2;
     return (int) Math.round(Math.pow(goldenRatio, n) / Math.sqrt(5));
}

# 3. 矩阵快速幂实现

public static int fibonacci(int n) {
    if (n <= 1) {
        return n;
    }

    int[][] base = {{1, 1}, {1, 0}};
    int[][] result = pow(base, n - 1);

    return result[0][0];
}

private static int[][] pow(int[][] base, int power) {
    int[][] result = new int[base.length][base.length];
    for (int i = 0; i < base.length; i++) {
        result[i][i] = 1;
    }

    while (power > 0) {
        if (power % 2 == 1) {
            result = multiply(result, base);
        }
        base = multiply(base, base);
        power /= 2;
    }

    return result;
}

private static int[][] multiply(int[][] a, int[][] b) {
    int[][] c = new int[a.length][b[0].length];
    for (int i = 0; i < a.length; i++) {
        for (int j = 0; j < b[0].length; j++) {
            for (int k = 0; k < b.length; k++) {
                c[i][j] += a[i][k] * b[k][j];
            }
        }
    }
    return c;
}