20260228 142406 Cpp 入门第十四课

第十四章：递推算法——从已知推未知 ¶

你好！欢迎来到第十四章！你有没有玩过“多米诺骨牌”？只要推倒第一张，后面的就会一张接一张倒下。这种“由前面推出后面”的思想，就是递推算法。递推在数学和编程中非常重要，比如斐波那契数列、爬楼梯问题，都可以用递推轻松解决。这一章我们就来学习如何用递推思想解决问题！

14.1 递推算法程序范例 ¶

先来看一个经典的递推问题：斐波那契数列。数列定义：第一项和第二项都是1，从第三项开始，每一项等于前两项之和。即：
- F(1) = 1
- F(2) = 1
- F(n) = F(n-1) + F(n-2) （n≥3）

用递推算法（循环）求第 n 项：

#include <iostream>
using namespace std;

int main() {
    int n;
    cout << "请输入n：";
    cin >> n;

    if (n <= 2) {
        cout << "第" << n << "项是：1" << endl;
    } else {
        int a = 1, b = 1, c;
        for (int i = 3; i <= n; i++) {
            c = a + b;   // 递推关系
            a = b;       // 向前移动
            b = c;
        }
        cout << "第" << n << "项是：" << b << endl;
    }
    return 0;
}

运行示例（输入10）：

第10项是：55

这个程序用循环不断更新前两项的值，一步步推出第 n 项。这就是递推：从已知的初始条件出发，按照递推公式逐步计算。

14.2 递推算法的用法 ¶

14.2.1 什么是递推？¶

递推就是利用已知的初始值，通过一定的递推关系（公式），逐步推出后面的结果。就像搭积木：先放好第一块，然后根据它放第二块，再根据前两块放第三块……

递推通常分为：
- 顺推：从已知条件向后推，比如斐波那契数列。
- 逆推：从结果向前推，但初学者先掌握顺推。

14.2.2 递推的要素 ¶

初始条件：最开始已知的值，比如 F(1)=1, F(2)=1。
递推关系：如何从前面推出后面，比如 F(n) = F(n-1) + F(n-2)。
计算顺序：通常用循环从小到大计算，避免重复。

14.2.3 递推 vs 递归 ¶

递归：函数自己调用自己，代码简洁，但容易重复计算，效率低（比如斐波那契递归会算很多次）。
递推：用循环从前往后算，每个值只算一次，效率高。

所以，当可以用递推时，优先用递推（循环）。

14.3 编程实例讲解 ¶

实例1：爬楼梯问题 ¶

题目：小明爬楼梯，每次可以跨1级或2级台阶。问爬到第n级台阶有多少种不同的爬法？

分析：
- 到第1级：只有1种（1步）
- 到第2级：有2种（1+1 或 2）
- 到第3级：可以从第1级跨2步，或从第2级跨1步，所以方法数 = 到第1级的方法 + 到第2级的方法 = 1+2=3
- 到第4级：可以从第2级跨2步，或从第3级跨1步，所以 = 2+3=5
- 发现规律：F(n) = F(n-1) + F(n-2)（和斐波那契一样，只是初始值 F(1)=1, F(2)=2）

#include <iostream>
using namespace std;

int main() {
    int n;
    cout << "请输入台阶数n：";
    cin >> n;

    if (n == 1) {
        cout << "爬法总数：1" << endl;
    } else if (n == 2) {
        cout << "爬法总数：2" << endl;
    } else {
        int a = 1, b = 2, c;
        for (int i = 3; i <= n; i++) {
            c = a + b;
            a = b;
            b = c;
        }
        cout << "爬法总数：" << b << endl;
    }
    return 0;
}

实例3：蜜蜂爬行 ¶

题目：蜜蜂从蜂房1出发，只能爬到编号相邻的蜂房（比如从1到2，从2到3或1，等等）。问从1爬到n有多少种不同的路径？

分析：
- 到1：1种（已经在）
- 到2：可以从1来，1种
- 到3：可以从2来，也可以从1来？但1只能到2，不能直接到3？题目说相邻，所以从1只能到2，从2可以到1或3。所以到3的路径：1→2→3，只有1种。实际上这是一个斐波那契数列变种。我们仔细分析：
- 设 f[i] 表示从1到i的路径数。
- f[1] = 1
- f[2] = 1（1→2）
- f[3] = f[2] + f[1]？但1到3不能直接，所以实际上 f[3] = f[2]（因为只能从2来）？不对，还可以从哪？蜜蜂可以来回爬，但一般这种问题是不允许重复的，所以通常是从左向右爬，即只能爬到比当前大的编号？这样题目才合理。通常这类题目是“蜜蜂只能向右爬”，那么 f[i] = f[i-1] + f[i-2]（因为可以从i-1和i-2来）。初始 f[1]=1, f[2]=1（1→2）。这样 f[3]=f[2]+f[1]=2，即1→2→3 和 1→3（如果允许1直接到3？但题目说相邻，所以1不能直接到3）。所以矛盾。我们假设蜜蜂只能爬到编号大1的蜂房，那就是线性的，只有1种。所以需要明确规则。

通常这类问题是在一个环上？常见的递推题：蜜蜂从蜂房a爬到蜂房b，只能爬向相邻的蜂房，且不能回头，求路径数。这实际上就是斐波那契数列：f(n) = f(n-1) + f(n-2)，初始 f(1)=1, f(2)=2？我们来看标准版：在一个直线上，蜜蜂只能向右爬，那么到第i个蜂房的路径数 = 到i-1的路径数 + 到i-2的路径数（因为可以从i-1跨一步，或从i-2跨两步）。这样 f(1)=1, f(2)=2（1→2 或直接到2？但1不能直接到2？实际上，如果蜂房编号连续，那么从1到2只有一种走法：1→2。但如果我们允许跨两步，那从1可以到2？不，跨两步就到3了。所以常见的是“每次可以走1步或2步”，那就是爬楼梯问题，初始 f(1)=1, f(2)=2。我们以爬楼梯为例即可。

所以我们可以直接用爬楼梯的代码。

实例4：平面分割问题 ¶

题目：n条直线最多能把平面分成多少个区域？

分析：
- 0条直线：1个区域
- 1条直线：2个区域
- 2条直线：最多4个区域（相交）
- 3条直线：最多7个区域
- 递推关系：第k条直线最多与前面k-1条直线相交于k-1个点，从而被分成k段，每段将原来的一个区域一分为二，所以增加k个区域。
- 设 f(n) 表示n条直线最多区域数，则 f(0)=1, f(n)=f(n-1)+n。

#include <iostream>
using namespace std;

int main() {
    int n;
    cout << "请输入直线条数：";
    cin >> n;
    int f = 1;  // 0条直线
    for (int i = 1; i <= n; i++) {
        f = f + i;   // 递推公式
    }
    cout << "最多能分成" << f << "个区域" << endl;
    return 0;
}

14.4 阶段性编程练习 ¶

练习1：求斐波那契数列的第20项（用递推循环）。
练习2：一个人上台阶，每次可以跨1级、2级或3级，求上10级台阶有多少种不同的走法。
练习3：用递推求 n!（阶乘），n! = n * (n-1)!，初始 1! = 1。
练习4：一对兔子，从出生后第3个月起每个月都生一对兔子。假设兔子不死，问第n个月有多少对兔子？（这就是斐波那契数列的由来，但初始值不同：第1个月1对，第2个月1对，第3个月2对，第4个月3对，第5个月5对… 即 f(1)=1, f(2)=1, f(3)=2, f(4)=3… 其实 f(n)=f(n-1)+f(n-2) 对 n≥3，f(1)=1, f(2)=1。就是斐波那契。）
练习5：用递推求杨辉三角的第n行（用一维数组递推）。

20260228 142406 Cpp 入门第十四课

第十四章：递推算法——从已知推未知 ¶

14.1 递推算法程序范例 ¶

14.2 递推算法的用法 ¶

14.2.1 什么是递推？¶

14.2.2 递推的要素 ¶

14.2.3 递推 vs 递归 ¶

14.3 编程实例讲解 ¶

实例1：爬楼梯问题 ¶

实例2：数字三角形（简单版）¶

实例3：蜜蜂爬行 ¶

实例4：平面分割问题 ¶

14.4 阶段性编程练习 ¶

14.5 第14章编程作业 ¶

作业1：母牛的故事 ¶

作业2：铺砖问题 ¶

作业3：骨牌铺满 ¶

作业4：猴子吃桃 ¶

作业5：数字三角形最大路径（文件版）¶