困难C++7 分钟2,460 字

C++递推经典问题(斐波那契数列)

什么是递推?为什么学它?

在编程中,“递推”是一种从已知出发、一步步推出未知的思考方法。就像你玩多米诺骨牌:推倒第一块,它撞倒第二块,第二块再撞倒第三块……结果整排都会倒下。递推的核心是利用前面已经算好的结果,计算出后面的结果​​,特别适合解决那些有规律、能一步一步往前推的问题。

生活中还有很多递推的例子,比如:

  • 零花钱存钱​​:你每周存10元,第一周有10元,第二周就是10+10=20元,第三周20+10=30元……这其实是一个递推:本周总额 = 上周总额 + 10。
  • 排队买冰淇淋​​:排在第1个的小朋友花了2分钟,第2个小朋友要等前面的人买完再加上自己的2分钟,所以等待时间依次增加。这些都可以用递推公式来描述。

今天我们要学的斐波那契数列​​,就是递推里最经典、最有意思的例子之一。


故事:兔子生宝宝(回顾)

这个数列来自一个古老的数学问题——兔子生宝宝。让我们再仔细捋一遍:

假设一对小兔子需要一个月​才能长大成年,成年后每个月​能生一对新的小兔子(一雌一雄),且兔子不会死。一开始(第1个月)我们有1对刚出生的幼兔。问:第 n 个月一共有多少对兔子?

我们一步步推:

  • 第1个月​​:1对幼兔(还没长大,不能生宝宝)。
  • 第2个月​​:幼兔长成了成兔,但还没生宝宝,所以还是1对成兔。
  • 第3个月​​:这对成兔生下了1对幼兔,所以现在有1对成兔 + 1对幼兔 = 2对​​。
  • 第4个月​​:原来的成兔又生1对幼兔,同时上个月的幼兔长成了成兔。这时候有:原来的1对成兔 + 新生的1对幼兔 + 上月幼兔变成的1对成兔 = 总共3对​​。
  • 第5个月​​:所有成兔(原来那对+上月变成的那对)各生1对幼兔,加上上个月的幼兔长大,总共5对​​。

你发现规律了吗? 这个月的兔子总数 = 上个月的兔子总数 + 上上个月的兔子总数​​。

为什么?因为上个月的所有兔子都存活(就是上个月的总数),而只有成兔能生宝宝。成兔的数量恰好等于上上个月的兔子总数(因为上上个月的幼兔到这个月已经成年了)。所以:

这个月总数 = 上个月总数(全部存活) + 上上个月总数(新生的幼兔)

这就是斐波那契数列的由来:1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ……


递推公式

用数学公式来表示斐波那契数列(通常用 F(n) 代表第 n 项):

  • 初始条件​​:F(1) = 1,F(2) = 1
  • 递推关系​​:当 n ≥ 3 时,F(n) = F(n-1) + F(n-2)

注意:有些教材把初始值设为 F(0)=0, F(1)=1,但本例我们按兔子问题取 F(1)=1, F(2)=1。

这个递推关系就是“从两个已知值推出下一个值”。你只需要知道前两个数,就能依次算出所有后面的数。


另一个贴近生活的例子:爬楼梯

我们换个例子加深理解:小明爬楼梯,每次可以跨1级​或2级​台阶。问:爬到第 n 级台阶,有多少种不同的爬法?

  • 第1级:只能跨1级,1种方法。
  • 第2级:可以两次1级,或一次2级,共2种方法。
  • 第3级:可以从第2级跨1级上来,也可以从第1级跨2级上来,所以方法数 = 第2级的方法数 + 第1级的方法数 = 2 + 1 = 3。
  • 第4级:从第3级跨1级,或从第2级跨2级,方法数 = 3 + 2 = 5。

你看,这又是一个斐波那契数列!只不过初始值变成了 F(1)=1, F(2)=2。递推思想一模一样:​当前项等于前两项之和​​。


C++代码实现(带详细解释)

下面我们用C++循环来计算斐波那契数列的第 n 项。代码里我们使用三个变量来“滚动”更新,避免用数组占用太多空间。

cpp
#include <iostream>
using namespace std;

int main() {
    int n;                                  // 用户输入,想求第几个月
    cout << "请输入你想知道第几个月的兔子对数(正整数):";
    cin >> n;

    int a = 1, b = 1;                        // a存第1个月,b存第2个月
    int result;                              // 用于存放最终结果

    if (n == 1 || n == 2) {
        result = 1;                         // 前两个月都是1
    } else {
        // 从第3项开始循环,一直算到第n项
        // 循环次数 = n - 2
        for (int i = 3; i <= n; i++) {
            result = a + b;                 // 当前项 = 前两项之和
            a = b;                          // 把原来的b变成新的a(向前滚动)
            b = result;                     // 把新算出的结果变成新的b
            // 下一轮循环时,a就是原来的b,b就是刚算出的结果
        }
    }

    cout << "第" << n << "个月的兔子对数是:" << result << endl;
    return 0;
}

变量变化追踪(以 n=5 为例):​

循环 i a (原来) b (原来) result = a+b 新的 a 新的 b
初始 1 1 / 1 1
i=3 1 1 2 1 2
i=4 1 2 3 2 3
i=5 2 3 5 3 5

循环结束,result = 5,正确。

运行示例:​

请输入你想知道第几个月的兔子对数(正整数):6
第6个月的兔子对数是:8

新手常见错误

  1. 忘记处理 n=1 或 n=2 的情况 如果直接进入循环(比如 for(i=3; i<=n; i++)),当 n=1 时循环条件 3<=1 不成立,result 就没有被赋值,输出会是随机值。所以一定要加 if 判断。
  2. 循环次数算错 有些人写 for(int i=1; i<=n; i++) 然后里面做 result = a+b; a = b; b = result;,这样会多算一次。正确应该是从第3项开始,执行 n-2 次。可以这样记忆:​​已知两项,还需要推 n-2 次才能到第 n 项​。
  3. 变量更新顺序搞反 // 错误写法 a = b; b = result; result = a + b; // 这时候 a 已经被覆盖了! 一定要先计算 result,再更新 a 和 b,否则会用到错误的值。
  4. 把斐波那契数列从 0 开始记混 有些数学教材定义 F(0)=0, F(1)=1,而兔子问题从1开始。编程时注意根据题目调整初始值。

完整示例:打印前10个月的兔子对数

上面的代码只输出第 n 个月。如果你想看看整个数列的生成过程,可以稍加改造:

cpp
#include <iostream>
using namespace std;

int main() {
    int a = 1, b = 1;                       // 前两月
    cout << "前10个月的兔子对数为:" << endl;
    cout << a << " " << b << " ";           // 先打印前两个

    for (int i = 3; i <= 10; i++) {
        int next = a + b;                   // 当前项
        cout << next << " ";
        a = b;                              // 向前滚动
        b = next;
    }
    cout << endl;
    return 0;
}

输出:​

前10个月的兔子对数为:
1 1 2 3 5 8 13 21 34 55

相关知识点指引

学完斐波那契数列的递推实现后,你可以继续探索:

  • 递归写法​​:F(n) = F(n-1) + F(n-2) 可以直接写成递归函数,但效率很低(重复计算太多)。递推(循环)是更优的解法。
  • 动态规划​​:递推是动态规划的基础,许多更复杂的问题(如背包问题、最短路径)也采用类似“从已知推到未知”的思想。
  • 矩阵快速幂​​:当 n 非常大(比如 10^18)时,用循环会超时,可以用矩阵乘法加速,这是算法竞赛中的进阶技巧。
  • 生活应用​​:斐波那契数列在自然界(向日葵的种子排列、花瓣数)、股票分析、计算机算法(如斐波那契查找)中都有应用。

递推就像多米诺骨牌,只要你掌握了前几块,就能轻松推到任意一块。希望你能用这个思路解决更多有趣的编程问题!

同类知识点