C++ 递推算法详解：GESP 四级考试核心考点

比如：

第 1 天 = 1
第 2 天 = 1

否则无法开始。就像没有第一块积木，无法搭房子。

2. 递推公式（核心）

比如：

a[i] = a[i-1] + a[i-2]

意思：第 i 个 = 前两个推出来。

3. 递推的顺序

必须：

先算小的 再算大的

不能跳着算。

第五章：最基础递推模板

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int a[100];
    // ① 初始值
    a[1] = 1;
    a[2] = 1;
    // ② 递推
    for(int i = 3; i <= n; i++) {
        a[i] = a[i-1] + a[i-2];
    }
    // ③ 输出
    cout << a[n];
    return 0;
}

第六章：故事例题 1《爬楼梯的小朋友》

1. 小明要爬楼梯

（1）每次可以：

走 1 步
或
走 2 步

（2）问：

爬到第 n 级，有多少种方法？

2. 我们画图：

（1）画一画

第 1 级：1 种
第 2 级：1+1, 2 (2 种)
第 3 级：1+1+1, 1+2, 2+1 (3 种)
第 4 级：1+1+1+1, 1+2+1, 2+1+1, 1+1+2, 2+2 (5 种)

（2）找规律：

f[n] = f[n-1] + f[n-2]

（3）因为：

最后一步：

可能从 n-1 来
可能从 n-2 来

3. 参考程序

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int f[100];
    f[1] = 1;
    f[2] = 2;
    for(int i = 3; i <= n; i++) {
        f[i] = f[i-1] + f[i-2];
    }
    cout << f[n];
    return 0;
}

第七章：故事例题 2《存金币的小猪》

1. 小猪每天存金币

（1）第 1 天：存 1 个

以后每天比前一天多存 2 个

（2）问第 n 天存多少？

2. 填表格：

1, 1+2=3, 3+2=5, 5+2=7, 7+2=9

这是一个等差数列！

3. 递推公式：

a[i] = a[i-1] + 2

4. 核心程序：

a[1] = 1;
for(int i=2; i<=n; i++) {
    a[i] = a[i-1] + 2;
}

第八章：故事例题 3《会繁殖的细菌》

1. 细菌每天：

变成昨天的 3 倍

2. 递推公式：

a[i] = a[i-1] * 3;

第九章：递推万能模板

int a[100];
a[1] = 初始值;
a[2] = 初始值;
for(int i = 2; i <= n; i++) {
    a[i] = 用 a[i-1] 或 a[i-2] 计算;
}

第十章：递推和普通循环的区别

1. 普通循环：

只是重复

2. 递推：

用'以前的结果'

3. 例如：

（1）普通循环：

for(int i=1; i<=n; i++) {
    cout<<i;
}

（2）递推算法：

a[i] = a[i-1] + 5;

使用递推公式，生成新的结果，用到了上一轮刚刚生成的结果。

第十一章：GESP 考试最常见递推类型

类型 1：每次加

a[i]=a[i-1]+k;

类型 2：每次乘

a[i]=a[i-1]*k;

类型 3：前两个相加

楼梯问题、兔子问题

a[i]=a[i-1]+a[i-2];

⭐⭐⭐⭐⭐考试最爱

类型 4：平方递推

a[i]=a[i-1]*a[i-1];

第十二章：小学生记忆口诀

递推递推不要猜
前面结果推出来
先有开始第一项
再用公式往后排

第十三章：图解理解

想象：

text
a[1] → a[2] → a[3] → a[4] → a[5]
↓      ↓      ↓      ↓      ↓
开始   推出   推出   推出

像多米诺骨牌一样倒下

第十四章：GESP 考试标准递推模板

#include <iostream>
using namespace std;

int main() {
    int n;
    cin>>n;
    int a[1000];
    a[1]=...;
    a[2]=...;
    for(int i=3; i<=n; i++) {
        a[i]=...;
    }
    cout<<a[n];
    return 0;
}

第十五章：一句话总结

递推就是：
用过去，推未来
就像是种子、小苗、变大树
一步一步长出来