数楼梯（递归与递推）（斐波那契数列）

迷南。 2022-11-13 01:52 198阅读 0赞

需要求斐波那契数列的第5000项，基本上1000项左右long long 就爆炸了。  
看代码，高精度还得去练一练。

复习一下斐波那契数列的通项公式：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1a2VyNg_size_16_color_FFFFFF_t_70]

代码的话，感觉不太好些，精度的问题，带考究

作者：匿名用户  
链接：https://www.zhihu.com/question/25217301/answer/158291644  
来源：知乎  
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

#include <iostream>
    using namespace std;
    int a[5005][5005];
    int len = 1;
    
    void hp(int k) // 高精度
    { 
        // 个位数
        for(int i = 1; i <= len; i++){ 
            a[k][i] = a[k-1][i] + a[k-2][i];
        }
        // 进位
        for(int i = 1; i <= len; i++){ 
            if(a[k][i] >= 10){ 
                a[k][i+1] += a[k][i] / 10;
                a[k][i] = a[k][i] % 10;
                if(a[k][len+1]) len++;
            }
        }
    }
    
    int main()
    { 
        int n;
        cin >> n;
        a[1][1] = 1;
        a[2][1] = 2;
        for(int i = 3; i <= n; i++){ 
            hp(i);
        }
        for(int i = len ; i >= 1; i--){ 
            cout << a[n][i];
        }
        return 0;
    }

[代码转发自这里][Link 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1a2VyNg_size_16_color_FFFFFF_t_70]: /images/20221022/d02173116a774f9eb9c15429a57930e7.png
[Link 1]: https://www.luogu.com.cn/problem/solution/P1255

发表评论取消回复

表情：

评论列表（有 0 条评论，198人围观）

还没有评论，来说两句吧...

相关阅读

相关数楼梯（递归与递推）（斐波那契数列）

需要求斐波那契数列的第5000项，基本上1000项左右long long 就爆炸了。看代码，高精度还得去练一练。复习一下斐波那契数列的通项公式： ![在这里插入图

迷南。/ 2022年11月13日 01:52/ 0 赞/ 199 阅读

相关斐波那契数列(递归思想)

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhp

矫情吗；*/ 2022年11月11日 06:13/ 0 赞/ 223 阅读

相关斐波那契数列（递归与非递归算法）

斐波那契数列，又称[黄金分割][Link 1]数列，指的是这样一个数列：0、1、1、2、3、5、8、13、21、……在数学上，斐波纳契数列以如下被以递归的方法定义：F0=0，F

一时失言乱红尘/ 2022年09月19日 15:29/ 0 赞/ 248 阅读

相关 509 斐波那契数（递推）

1. 问题描述：斐波那契数，通常用 F(n) 表示，形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是： F(0)

秒速五厘米/ 2022年08月30日 00:48/ 0 赞/ 184 阅读

相关斐波那契数列--递归与非递归实现

初识斐波那契数列：斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖

ゝ一纸荒年。/ 2022年05月23日 05:40/ 0 赞/ 205 阅读

相关递归算法--斐波那契数列

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。n<=39 很容易我们想到使用递归求解： public

刺骨的言语ヽ痛彻心扉/ 2022年05月18日 01:06/ 0 赞/ 211 阅读

相关递归算法实现斐波那契数列

假定兔子在出生两个月后，就有繁殖能力，一对兔子每个月能生出一对小兔子来。如果所有兔子都不死，那么一年以后可以繁殖多少对兔子？这就是著名的斐波那契数列，也称作兔子数列。 >

Dear 丶/ 2022年05月14日 05:42/ 0 赞/ 214 阅读

相关斐波那契数列递归非递归实现

斐波那契数列是学习c语言递归时，必写的。递归实现代码 int fun(int n) //递归 { if(n==1||n==2)

桃扇骨/ 2022年03月30日 15:12/ 0 赞/ 216 阅读

相关箭头函数递归斐波那契数列

let Y = f => (g=>f(a=>g(g)(a)))(g=>f(a=>g(g)(a))) Y(f=>n=>n>1?f(n-1)+f(n-2)

╰+攻爆jí腚メ/ 2021年11月29日 18:08/ 0 赞/ 418 阅读

相关递归求斐波那契数列

斐波那契数列题目描述：编写一个函数，求斐波那契数列的第n项的值。首先，对于斐波那契数列，我们是非常熟悉了，对斐波那契定义为如下：f(0)=0,f(1)=0,f(2)=1

左手的ㄟ右手/ 2021年11月17日 12:34/ 0 赞/ 363 阅读