小学生都能看懂的题解 | #斐波那契数列#

问题描述：

斐波那契数列是一个特殊的数列，其中每个数字都是前两个数字的和。给定一个正整数 nn，我们需要计算斐波那契数列的第 nn 项。

斐波那契数列的定义：

• 第1项是1。
• 第2项也是1。
• 从第3项开始，每一项都是前两项的和。

示例：

• 输入：4 输出：3 解释：fib(1) = 1, fib(2) = 1, fib(3) = fib(2) + fib(1) = 2, fib(4) = fib(3) + fib(2) = 3

解决方案：

我们可以用一个特殊的方法来快速计算斐波那契数列的第 n 项。这个方法叫做“矩阵快速幂”。

方法说明：

想象我们有一个魔法盒子，这个盒子可以帮我们快速计算出斐波那契数列的第 n 项。我们只需要输入 n，盒子就能给我们答案。

具体步骤：

1. 初始化：对于 n=1 或 n=2，直接返回 1。
2. 构造矩阵：我们用一个特殊的矩阵来表示斐波那契数列的规律。
3. 快速幂计算：我们使用快速幂的方法来计算这个矩阵的 n−1 次方。
4. 提取结果：计算出来的矩阵的第一行第一列就是我们想要的斐波那契数。

代码实现：

public class FibonacciFastExponentiation {

    /**
     * 计算斐波那契数列的第 n 项（时间复杂度 O(log n)）
     * @param n 正整数 n
     * @return 斐波那契数列的第 n 项
     */
    public int Fibonacci(int n) {
        if (n == 1 || n == 2) {
            return 1; // 对于 n = 1 或 n = 2，直接返回 1
        }
        
        // 特殊矩阵
        int[][] baseMatrix = {{1, 1}, {1, 0}};
        int[][] resultMatrix = matrixPower(baseMatrix, n - 1);
        
        // 结果矩阵的第一行第一列就是 Fn
        return resultMatrix[0][0];
    }

    /**
     * 计算矩阵的快速幂
     * @param matrix 要计算幂的矩阵
     * @param power 幂次
     * @return 计算结果矩阵
     */
    private int[][] matrixPower(int[][] matrix, int power) {
        int size = matrix.length;
        int[][] result = identityMatrix(size); // 单位矩阵
        
        while (power > 0) {
            if (power % 2 == 1) { // 如果 power 是奇数，则乘以当前矩阵
                result = multiplyMatrices(result, matrix);
            }
            matrix = multiplyMatrices(matrix, matrix); // 平方
            power /= 2; // power 除以 2
        }
        
        return result;
    }

    /**
     * 生成单位矩阵
     * @param size 矩阵大小
     * @return 单位矩阵
     */
    private int[][] identityMatrix(int size) {
        int[][] identity = new int[size][size];
        for (int i = 0; i < size; i++) {
            identity[i][i] = 1;
        }
        return identity;
    }

    /**
     * 矩阵乘法
     * @param a 第一个矩阵
     * @param b 第二个矩阵
     * @return 乘法结果矩阵
     */
    private int[][] multiplyMatrices(int[][] a, int[][] b) {
        int size = a.length;
        int[][] result = new int[size][size];
        
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                for (int k = 0; k < size; k++) {
                    result[i][j] += a[i][k] * b[k][j];
                }
            }
        }
        
        return result;
    }

    public static void main(String[] args) {
        FibonacciFastExponentiation fib = new FibonacciFastExponentiation();

        // 示例输入
        int input1 = 4;
        System.out.println("Fibonacci(" + input1 + ") = " + fib.Fibonacci(input1)); // 输出：3

        int input2 = 1;
        System.out.println("Fibonacci(" + input2 + ") = " + fib.Fibonacci(input2)); // 输出：1

        int input3 = 2;
        System.out.println("Fibonacci(" + input3 + ") = " + fib.Fibonacci(input3)); // 输出：1

        int input4 = 10;
        System.out.println("Fibonacci(" + input4 + ") = " + fib.Fibonacci(input4)); // 输出：55
    }
}

解释：

1. 初始化：对于 n=1 或 n=2，直接返回 1。
2. 构造矩阵：我们构造一个特殊的矩阵 {{1, 1}, {1, 0}}，这个矩阵可以帮助我们快速计算斐波那契数列。
3. 快速幂计算：使用快速幂的方法来计算矩阵的 n−1 次方。具体来说，我们通过不断平方来减少计算量。
4. 提取结果：计算出来的矩阵的第一行第一列就是我们想要的斐波那契数。

示例运行结果：

• 输入：4输出：3
• 输入：1输出：1
• 输入：2输出：1
• 输入：10输出：55

通过这种方式，我们可以在 O(log⁡n) 的时间复杂度下计算斐波那契数列的第 n 项。

如果这篇文章对你有帮助，请点个免费的赞👍，让它能够帮助更多的人。