首页 > 编程语言 >【常见算法题】斐波那契数列（矩阵快速幂）

【常见算法题】斐波那契数列（矩阵快速幂）

时间：2024-08-14 12:27:26浏览次数：15  
标签：BigInteger 数列 int 矩阵 斐波 000 Fibonacci 那契

一、题目描述

大家都知道斐波那契数列，现在要求输入一个正整数 n ，请你输出斐波那契数列的第 n 项。

斐波那契数列满足如下

二、解题思路

2.1 普通处理方式

使用递归直接计算

int fib(int n) {
    if (n == 1 || n == 2) return 1;
    return fib(n - 1) + fib(n - 2);
}

这种方法是学习软件开发或者算法时最原始，最容易理解的方法。但是缺点很多

  • 1、未对n进行参数检查；
  • 2、性能差，数据量比较大的时候，计算很慢；
  • 3、返回结果时int类型，能支持的n很小；

2.2 分析优化及处理

如果使用递归求解，会重复计算一些子问题。例如，计算 f(4) 需要计算 f(3) 和 f(2)，计算 f(3) 需要计算 f(2) 和 f(1)，可以看到 f(2) 被重复计算了。

递归是将一个问题划分成多个子问题求解。动态规划也是如此，但是动态规划会把子问题的解缓存起来，从而避免重复求解子问题。

public int Fibonacci(int n) {
    if (n <= 1)
        return n;
    int[] fib = new int[n + 1];
    fib[1] = 1;
    for (int i = 2; i <= n; i++)
        fib[i] = fib[i - 1] + fib[i - 2];
    return fib[n];
}

考虑到第 i 项只与第 i-1 和第 i-2 项有关，因此只需要存储前两项的值就能求解第 i 项，从而将空间复杂度由 O(N) 降低为 O(1)。

尤其时n数值比较大时，可以降低很多内存占用，避免栈溢出。

public int Fibonacci(int n) {
    if (n <= 1)
        return n;
    int pre2 = 0, pre1 = 1;
    int fib = 0;
    for (int i = 2; i <= n; i++) {
        fib = pre2 + pre1;
        pre2 = pre1;
        pre1 = fib;
    }
    return fib;
}

三、再优化，支持更大的参数n和更大的返回结果

由于int只有4个字节，能处理的n比较小，因此可以考虑用long、BigInteger处理

3.1 long版本

对n进行参数检查，由于long是8个字节，要考虑到返回的结果不能超过long的最大值。

    public long fibLongPlus(int n) {
        if (n <= 0) {
            return 0;
        }
        if (n >= 92) {
            throw new IllegalArgumentException("n is too large to compute within available memory");
        }
        // base case
        long a = 0;
        long b = 1;
        // 状态转移
        long temp;
        for (int i = 2; i <= n; i++) {
            temp = a + b;
            a = b;
            b = temp;
        }
        return b;
    }

3.2 BigInteger版本

BigInteger可以支持更大的n，支持更大的结果返回

    public BigInteger fibPlus(int n) {
        if (n <= 0) {
            return BigInteger.ZERO;
        }
        // 考虑到内存和性能，n最大限制为1_000_000
        if (n > 1_000_000) {
            throw new IllegalArgumentException("n is too large to compute within available memory");
        }
        // base case
        BigInteger pre1 = BigInteger.ZERO;
        BigInteger pre2 = BigInteger.ONE;
        // 状态转移
        BigInteger fib;
        for (int i = 2; i <= n; i++) {
            fib = pre1.add(pre2);
            pre1 = pre2;
            pre2 = fib;
        }
        return pre2;
    }

四、再优化，使用`矩阵快速幂`提升计算性能

4.1 矩阵快速幂实现

    /**
     * 计算两个2x2矩阵的乘积。
     *
     * @param a 第一个矩阵
     * @param b 第二个矩阵
     * @return 两个矩阵的乘积
     */
    private BigInteger[][] matrixMultiply(BigInteger[][] a, BigInteger[][] b) {
        // 创建结果矩阵
        BigInteger[][] result = new BigInteger[2][2];   
        // 遍历结果矩阵的行
        for (int i = 0; i < 2; i++) {
            // 遍历结果矩阵的列  
            for (int j = 0; j < 2; j++) {
                // 初始化结果矩阵的当前元素为0
                result[i][j] = BigInteger.ZERO;
                // 遍历乘法的中间索引
                for (int k = 0; k < 2; k++) {
                    // 执行矩阵乘法
                    result[i][j] = result[i][j].add(a[i][k].multiply(b[k][j]));
                }
            }
        }
        // 返回结果矩阵
        return result;
    }

    /**
     * 使用矩阵快速幂算法计算矩阵的n次幂。
     *
     * @param matrix 要计算幂的矩阵
     * @param n      幂次
     * @return 矩阵的n次幂的结果
     */
    private BigInteger[][] matrixPower(BigInteger[][] matrix, int n) {
        BigInteger[][] result = new BigInteger[][]{
            // 初始化结果矩阵为单位矩阵 
            {BigInteger.ONE, BigInteger.ZERO},
            {BigInteger.ZERO, BigInteger.ONE}
        };

        // 当幂次大于0时循环
        while (n > 0) {
            // 如果幂次是奇数
            if ((n & 1) == 1) {
                // 将结果矩阵乘以原矩阵
                result = matrixMultiply(result, matrix);
            }

            // 将原矩阵平方
            matrix = matrixMultiply(matrix, matrix);

            // 幂次减半
            n >>= 1;
        }

        // 返回结果矩阵
        return result;
    }

    /**
     * 使用矩阵快速幂算法计算斐波那契数列的第n项。
     *
     * @param n 斐波那契数列的项数
     * @return 斐波那契数列的第n项
     */
    public BigInteger fibPlus(int n) {
        // 如果n小于等于0，返回0
        if (n <= 0) {
            return BigInteger.ZERO;
        }
        // 限制n大小
        if(n > 1_000_000_0){
            throw new IllegalArgumentException("n is too large to compute within available memory");
        }
        // 创建斐波那契变换矩阵
        BigInteger[][] fibMatrix = new BigInteger[][]{
            {BigInteger.ONE, BigInteger.ONE},
            {BigInteger.ONE, BigInteger.ZERO}
        };

        // 计算斐波那契变换矩阵的n-1次幂
        BigInteger[][] result = matrixPower(fibMatrix, n - 1);

        // 返回结果矩阵的第一行第一列元素，即斐波那契数列的第n项
        return result[0][0];
    }

4.2 单元测试

4.2.1 测试小数据量

    @Test
    public void test_fibPlus() {
        for (int i = 0; i < 100; i++) {
            // 设置要计算的斐波那契数列的项数
            int n = i;
            // 输出斐波那契数列的第n项
            System.out.println("Fibonacci(" + n + ") = " + fibPlus(n));
        }
    }

输出结果

Fibonacci(0) = 0
Fibonacci(1) = 1
Fibonacci(2) = 1
Fibonacci(3) = 2
Fibonacci(4) = 3
Fibonacci(5) = 5
Fibonacci(6) = 8
Fibonacci(7) = 13
Fibonacci(8) = 21
Fibonacci(9) = 34
Fibonacci(10) = 55
Fibonacci(11) = 89
Fibonacci(12) = 144
Fibonacci(13) = 233
Fibonacci(14) = 377
Fibonacci(15) = 610
Fibonacci(16) = 987
Fibonacci(17) = 1597
Fibonacci(18) = 2584
Fibonacci(19) = 4181
Fibonacci(20) = 6765
Fibonacci(21) = 10946
Fibonacci(22) = 17711
Fibonacci(23) = 28657
Fibonacci(24) = 46368
Fibonacci(25) = 75025
Fibonacci(26) = 121393
Fibonacci(27) = 196418
Fibonacci(28) = 317811
Fibonacci(29) = 514229
Fibonacci(30) = 832040
Fibonacci(31) = 1346269
Fibonacci(32) = 2178309
Fibonacci(33) = 3524578
Fibonacci(34) = 5702887
Fibonacci(35) = 9227465
Fibonacci(36) = 14930352
Fibonacci(37) = 24157817
Fibonacci(38) = 39088169
Fibonacci(39) = 63245986
Fibonacci(40) = 102334155
Fibonacci(41) = 165580141
Fibonacci(42) = 267914296
Fibonacci(43) = 433494437
Fibonacci(44) = 701408733
Fibonacci(45) = 1134903170
Fibonacci(46) = 1836311903
Fibonacci(47) = 2971215073
Fibonacci(48) = 4807526976
Fibonacci(49) = 7778742049
Fibonacci(50) = 12586269025
Fibonacci(51) = 20365011074
Fibonacci(52) = 32951280099
Fibonacci(53) = 53316291173
Fibonacci(54) = 86267571272
Fibonacci(55) = 139583862445
Fibonacci(56) = 225851433717
Fibonacci(57) = 365435296162
Fibonacci(58) = 591286729879
Fibonacci(59) = 956722026041
Fibonacci(60) = 1548008755920
Fibonacci(61) = 2504730781961
Fibonacci(62) = 4052739537881
Fibonacci(63) = 6557470319842
Fibonacci(64) = 10610209857723
Fibonacci(65) = 17167680177565
Fibonacci(66) = 27777890035288
Fibonacci(67) = 44945570212853
Fibonacci(68) = 72723460248141
Fibonacci(69) = 117669030460994
Fibonacci(70) = 190392490709135
Fibonacci(71) = 308061521170129
Fibonacci(72) = 498454011879264
Fibonacci(73) = 806515533049393
Fibonacci(74) = 1304969544928657
Fibonacci(75) = 2111485077978050
Fibonacci(76) = 3416454622906707
Fibonacci(77) = 5527939700884757
Fibonacci(78) = 8944394323791464
Fibonacci(79) = 14472334024676221
Fibonacci(80) = 23416728348467685
Fibonacci(81) = 37889062373143906
Fibonacci(82) = 61305790721611591
Fibonacci(83) = 99194853094755497
Fibonacci(84) = 160500643816367088
Fibonacci(85) = 259695496911122585
Fibonacci(86) = 420196140727489673
Fibonacci(87) = 679891637638612258
Fibonacci(88) = 1100087778366101931
Fibonacci(89) = 1779979416004714189
Fibonacci(90) = 2880067194370816120
Fibonacci(91) = 4660046610375530309
Fibonacci(92) = 7540113804746346429
Fibonacci(93) = 12200160415121876738
Fibonacci(94) = 19740274219868223167
Fibonacci(95) = 31940434634990099905
Fibonacci(96) = 51680708854858323072
Fibonacci(97) = 83621143489848422977
Fibonacci(98) = 135301852344706746049
Fibonacci(99) = 218922995834555169026

4.2.2 测试大数据量

n=1_000_000 时很快，不到1秒。

再大一些（比如n=1_000_000_0）的时候，计算就比较慢了

  • 测试 1_000_000_0
    @Test
    public void test_fibPlus() {
        int n = 1_000_000_0;
        System.out.println("Fibonacci(" + n + ") = " + fibPlus(n));
    }

测试大数结果（结果太长了，发布不了，就不展示了，感兴趣的可以自己写UT验证下）

Fibonacci(10000000) = 1129834378225399760317063637745866372944837190489040881513577643245534731167933137524219777458247745488503329541529737982917618975273928543637913029320511080393607160947067632276156828424897006419736620682555596286851200164878524757142799029763435331462543748832574728019186803442609337613122078718093224952473835489645047696411558824438103526892104885863028289108.............

标签：BigInteger,数列,int,矩阵,斐波,000,Fibonacci,那契
From： https://blog.csdn.net/yyp0719/article/details/141186667

相关文章

  • C语言实现斐波那契数列
    斐波那契数列（Fibonaccisequence）是一个经典的数学问题，在数学和计算机科学领域都有广泛的应用。斐波那契数列是以意大利数学家列昂纳多·斐波那契（LeonardodaFibonacci）的名字命名的，他通过兔子繁殖的例子引入了这一数列。斐波那契数列的每一项都是前两项的和，且从第三项开始，即1、......
  • PAT乙级1030 || 完美数列（C示例解决运行超时）
    完美数列给定一个正整数数列，和正整数p，设这个数列中的最大值是M，最小值是m，如果M≤mp，则称这个数列是完美数列。现在给定参数p和一些正整数，请你从中选择尽可能多的数构成一个完美数列。输入格式：输入第一行给出两个正整数N和p，其中N（≤105）是输入的正整数的个数，p（≤109）是......
  • 逆序对数列（P2513） - 题解
    [HAOI2009]逆序对数列原题链接题目描述对于一个数列\(\{a_i\}\)，如果有\(i<j\)且\(a_i>a_j\)，那么我们称\(a_i\)与\(a_j\)为一对逆序对数。若对于任意一个由\(1\simn\)自然数组成的数列，可以很容易求出有多少个逆序对数。那么逆序对数为\(k\)的这样自然数数列到底......
  • 黑马Java零基础视频教程精华部分_15_基本查找/顺序查找、二分查找/折半查找、插值查找
    系列文章目录文章目录系列文章目录一、基本查找/顺序查找核心思想：从0索引开始挨个往后查找代码：练习：定义一个方法利用基本查找，查询某个元素在数组中的索引，数组包含重复数据。二、二分查找/折半查找核心思想:属于有序查找算法。用给定值先与中间结点比较，每次排除一半的......
  • VS Code 未从 launch.json 中获取参数列表
    我有一个正在试验的基本python文件。我想在vscode中使用两个参数启动它。我已从命令窗口(ctrl+shift+p)打开launch.json文件，但每次运行时都无法获取我的参数列表。这是怎么回事？{//UseIntelliSensetolearnaboutpossibleattributes.//Hovertoviewdescripti......
  • 数列 题解
    题目id：1753题目描述给你一个长度为\(N\)的正整数序列，如果一个连续的子序列，子序列的和能够被K整除，那么就视此子序列合法，求原序列包括多少个合法的连续子序列？对于一个长度为\(8\)的序列，\(K=4\)的情况：\(2,1,2,1,1,2,1,2\)。它的答案为\(6\)，子序列是位置\(1->\)位置\(8\)，\(2->4\)......
  • 超详细明了的C语言函数递归，望周知。（包含求n的阶乘顺序打印⼀个整数的每⼀位求第n个斐
    1.递归是什么？递归是学习C语⾔函数绕不开的⼀个话题，那什么是递归呢？递归其实是⼀种解决问题的⽅法，在C语⾔中，递归就是函数⾃⼰调⽤⾃⼰。写⼀个史上最简单的C语⾔递归代码#include<stdio.h>intmain(){printf......
  • P3200 [HNOI2009] 有趣的数列
    哇，太恶心了思路首先我们将题意简化，简化后为对于任意一个偶数位所填数必然大于等于自己的下标，那么考虑填数，如果填的偶数比奇数多，那么此时要么填尽偶数后失败，或者下一个位置填奇数就炸，比如偶数刚好多一个，那么必然有一个偶数放在了奇数位，那么本来下一个要填的偶数往前移了一个，导致......
  • PHP中如何实现函数的可变参数列表
    在PHP中，实现函数的可变参数列表主要有两种方式：使用func_get_args()函数和使用可变数量的参数（通过...操作符，自PHP5.6.0起引入）。1.使用func_get_args()函数func_get_args()函数用于获取传递给函数的参数列表，并作为一个数组返回。这种方式不需要在函数定义时明确指定参数的数......
  • 5***斐波那契兔子数列
    题目：古典问题（兔子生崽）：有一对兔子，从出生后第3个月起每个月都生一对兔子，小兔子长到第三个月后每个月又生一对兔子，假如兔子都不死，问每个月的兔子总数为多少？（输出前40个月即可）详解：首先这个输出的值就是斐波那契数列：1,1,2,3,5,8,13,21....，重要特点，也是解题关键是：    每一......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99