C++算法
C++ 递推算法详解：GESP 四级考试核心考点
详细讲解 C++ 递推算法的基础概念，涵盖初始值设定、递推公式构建及计算顺序。通过兔子繁殖、爬楼梯、存金币等实例演示斐波那契数列与等差数列的推导过程。提供标准代码模板及四种常见递推类型总结，旨在帮助考生掌握 GESP 四级考试中的核心算法考点。
详细讲解 C++ 递推算法的基础概念，涵盖初始值设定、递推公式构建及计算顺序。通过兔子繁殖、爬楼梯、存金币等实例演示斐波那契数列与等差数列的推导过程。提供标准代码模板及四种常见递推类型总结，旨在帮助考生掌握 GESP 四级考试中的核心算法考点。
| 天数 | 叶子数 |
|---|---|
| 第 1 天 | 1 |
| 第 2 天 | 2 |
| 第 3 天 | 4 |
| 第 4 天 | 8 |
| 第 5 天 | 16 |
今天的叶子数 = 昨天的叶子数 × 2
这就是：递推公式
就像：
text
今天 = 昨天 推出来的
未来 = 现在 推出来的
这就叫：递推（一步一步推出来）
第 1 个月：1 只兔子
第 2 个月：1 只兔子
每只成熟兔子每个月生 1 只新兔子
| 月份 | 兔子数 |
|---|---|
| 1 | 1 |
| 2 | 1 |
| 3 | 2 |
| 4 | 3 |
| 5 | 5 |
| 6 | 8 |
第 n 月兔子数 = 第 n-1 月兔子数 + 第 n-2 月兔子数
斐波那契数列
任何递推必须有：
比如：
第 1 天 = 1
第 2 天 = 1
否则无法开始。就像没有第一块积木，无法搭房子。
比如：
a[i] = a[i-1] + a[i-2]
意思：第 i 个 = 前两个推出来。
必须：
先算小的 再算大的
不能跳着算。
#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 步
或
走 2 步
爬到第 n 级，有多少种方法？
第 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 种)
f[n] = f[n-1] + f[n-2]
最后一步：
可能从 n-1 来
可能从 n-2 来
#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+2=3, 3+2=5, 5+2=7, 7+2=9
这是一个等差数列！
a[i] = a[i-1] + 2
a[1] = 1;
for(int i=2; i<=n; i++) {
a[i] = a[i-1] + 2;
}
变成昨天的 3 倍
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] 计算;
}
只是重复
用'以前的结果'
for(int i=1; i<=n; i++) {
cout<<i;
}
a[i] = a[i-1] + 5;
使用递推公式，生成新的结果，用到了上一轮刚刚生成的结果。
a[i]=a[i-1]+k;
a[i]=a[i-1]*k;
楼梯问题、兔子问题
a[i]=a[i-1]+a[i-2];
⭐⭐⭐⭐⭐考试最爱
a[i]=a[i-1]*a[i-1];
递推递推不要猜
前面结果推出来
先有开始第一项
再用公式往后排
想象：
text
a[1] → a[2] → a[3] → a[4] → a[5]
↓ ↓ ↓ ↓ ↓
开始 推出 推出 推出
像多米诺骨牌一样倒下
#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;
}
递推就是：
用过去，推未来
就像是种子、小苗、变大树
一步一步长出来
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online