GESP 四级 · GESP202609 C++ 四级 第 9 题

某机器人每次可以向前移动 1 格或 2 格，到达第 n 格的方法数由下面函数计算。ways(6) 的返回值是 （　　）。

int ways(int n) {
if (n <= 2)
return n;
int a = 1, b = 2, c = 0;
for (int i = 3; i <= n; i++) {
c = a + b;
a = b;
b = c;
}
return b;
}

本题是经典的斐波那契数列变体。看到题先识别出 ways(n) 就是求第 n 项递推值，n≤2 时直接返回 n 是基准情形，循环里用 a、b 滚动保存前两项，每次迭代计算 c=a+b 再更新 a、b，本质就是递推公式 f(i)=f(i−1)+f(i−2) 的 O(n) 实现。求 ways(6) 只需模拟循环 3 到 6 这 4 次迭代即可。

易错点：1）误以为 ways(6) 是斐波那契数列第 6 项 8，忽略了基准值 ways(1)=1、ways(2)=2 导致序列为 1,2,3,5,8,13；2）循环次数数错，i 从 3 到 n 共 n−2 次，n=6 时是 4 次；3）混淆 a、b 与 c 的更新顺序，若先 a=b 再 c=a+b 会得到错误值；4）忘记函数返回的是 b 而非 c，循环结束后 b 已指向最新结果。

1. 考纲定位

本题考查《GESP 考试大纲》四级"算法与数据结构"模块中的递推与循环，属于基础算法题。命题人放这道题，就是要卡住那些只会套模板、不真正理解递推逻辑的考生——很多人看到斐波那契就下意识选 8，却忘了本题的基准值从 1、2 开始，序列整体偏移了一位。

2. 解题思维

看到题先想：ways(n) 是什么？n≤2 时直接返回 n，说明 ways(1)=1、ways(2)=2。循环里 a、b 初始为 1、2，每次迭代 c=a+b 再更新 a、b，这就是递推公式 f(i)=f(i−1)+f(i−2) 的实现。求 ways(6) 只需模拟循环 3 到 6 这 4 次迭代即可。

数值推演（自己算一遍，别含糊）：

• 初始：a=1, b=2, c=0
• i=3：c=1+2=3, a=2, b=3
• i=4：c=2+3=5, a=3, b=5
• i=5：c=3+5=8, a=5, b=8
• i=6：c=5+8=13, a=8, b=13

循环结束返回 b，即 13。

通法：这类递推题，先找基准情形，再识别递推公式，然后用循环或递归实现。本题用循环是 O(n) 时间、O(1) 空间，比递归更优。