六、循环：递推、模拟与综合

这一页 4 章 32 道题，其中第 19 章标了「选学」。

到这一页，你应该已经能熟练地写循环、读入、判断、累加。这一页不再教你新的语法，教的是怎么把一段自然语言的描述翻译成循环。

三个新套路：

• 递推：后一项由前一项算出来（斐波那契、兔子繁殖）
• 逆推：从结果倒着往回算（猴子吃桃）
• 模拟：把题目描述的过程，一步一步照着演一遍（角谷猜想、开关灯）

第三种最重要。大部分「应用题」都是模拟——题目怎么说，你就怎么写，不需要想什么技巧。

18. 数列与递推

18.1 递推：用前一项算后一项

斐波那契数列：1、1、2、3、5、8、13……每项等于前两项之和。

int a = 1, b = 1;
for (int i = 3; i <= n; i++) {
    int c = a + b;
    a = b;
    b = c;
}
printf("%d\n", b);

关键在于 a = b; b = c; 这两行——把窗口往后挪一格。配合 a、b 两个变量，就能一路推出第 n 项，不需要存整个数列。

这个技巧叫「滚动变量」。它省空间，也快。如果 n 很大（比如 100 万），存数组会爆内存，滚动变量不会。

a = b;      // 先把 b 覆盖掉 a
b = a + b;  // 这时 a 已经是新的值了，算出来是 2b

int c = a + b;   // 先算
a = b;           // 再挪
b = c;

18.2 逆推：从结果倒着算

猴子吃桃：第一天吃一半多一个，第二天吃剩下的一半多一个……第 n 天早上剩 1 个，问最初有多少个。

正着算不知道从哪开始，但倒着算很清楚：

int ans = 1;              // 第 n 天的桃子数
for (int i = 1; i < n; i++) {
    ans = (ans + 1) * 2;  // 往前推一天
}

正着是「除以 2 再减 1」，反着就是「加 1 再乘 2」。逆运算的规则要自己推一遍，别背公式。

18.3 带条件的累加

有时候循环不是「把所有项都加上」，而是「满足条件的才加」。

// 1 到 n 的奇数和
int sum = 0;
for (int i = 1; i <= n; i++) {
    if (i % 2 == 1) sum += i;
}

交错求和是另一种：符号一正一负。

// 1 - 1/2 + 1/3 - 1/4 + ...
double sum = 0;
int sign = 1;
for (int i = 1; i <= n; i++) {
    sum += sign * 1.0 / i;
    sign = -sign;            // 每轮翻转符号
}

sign = -sign 这个写法比 if (i % 2 == 1) ... else ... 更简洁。符号交替 = 一个每次取反的变量。

18.4 数位与映射

有一类题要求把每一位数字「翻译」成别的东西，比如中文拼音。

int d = n % 10;
if (d == 0) printf("ling");
else if (d == 1) printf("yi");
// ...

这种「数字 → 字符串」的映射，最直接的写法就是 if 链或者数组：

const char* name[] = {"ling", "yi", "er", "san", "si",
                      "wu", "liu", "qi", "ba", "jiu"};
printf("%s", name[d]);

数组下标直接就是数字本身，不用判断。这个写法第 22 章学数组后会非常常用，现在先看一眼。

18.5 分数递推

19. 组合计数（选学）

19.1 乘法原理：分步做的事，数量相乘

一件事分几步完成，每步有若干种选择，总方案数就是各步选择的乘积。

有 3 件上衣、4 条裤子，一共有多少种搭配？→ 3 × 4 = 12

代码上就是两个嵌套循环，或者直接相乘：

int ans = 1;
for (int i = 1; i <= k; i++) ans *= choices[i];

「可重排列」（每步选择互不影响）就是纯乘法；「不可重」（选过的不能再选）要递减：

// 从 n 个里依次取 k 个，不能重复
int ans = 1;
for (int i = 0; i < k; i++) ans *= (n - i);

19.2 组合与分配

组合数 C(n, m) 表示从 n 个里选 m 个（不计顺序）。算法是：

C(n,m) = n×(n-1)×…×(n-m+1) / (m×(m-1)×…×1)

long long comb(int n, int m) {
    long long r = 1;
    for (int i = 1; i <= m; i++) {
        r = r * (n - i + 1) / i;    // 边乘边除，防止溢出
    }
    return r;
}

r = r * (n-i+1) / i 这个「边乘边除」的写法很重要：每一步都保证能整除，且中间结果不会太大。如果先算完分子的阶乘再除，20! 早就溢出了。

19.3 直线上的整点

20. 生活模拟

这一章是「模拟题」——题目描述一个过程，你照着演一遍。

模拟题不需要技巧，只需要耐心。 把题目读三遍，把每个步骤写成一行代码，就完了。

20.1 按规则一步步走

角谷猜想：奇数乘 3 加 1，偶数除以 2，问几步变成 1。

int n, cnt = 0;
scanf("%d", &n);
while (n != 1) {
    if (n % 2 == 1) n = n * 3 + 1;
    else n = n / 2;
    cnt++;
}
printf("%d\n", cnt);

这段代码几乎就是题目描述的直接翻译。模拟题就该这么写——不要试图找规律、不要试图优化，除非它超时。

20.2 逐项判断与计数

int cnt = 0;
for (int i = 1; i <= n; i++) {
    int x;
    scanf("%d", &x);
    if (满足条件(x)) cnt++;
}

这个模式前面见过很多次了。模拟类题目里，条件往往比较长，建议把条件写成独立的函数（第 27 章会讲），主循环会干净很多。

20.3 连续状态

「连续多少天正常」「最长的一段连续……」——这类题目需要维护两个东西：当前长度 和 最大长度。

int cur = 0, best = 0;
for (int i = 1; i <= n; i++) {
    if (满足条件) {
        cur++;
        if (cur > best) best = cur;
    } else {
        cur = 0;              // 断了，重新开始
    }
}

else { cur = 0; } 这一行是关键。忘了它，cur 会一直累加，得到的就不是「连续」的长度了。

20.4 日期累计

「一年中的第几天」这类题，思路是把前面各月的天数加起来：

int days[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int sum = 0;
for (int i = 1; i < m; i++) sum += days[i];
sum += d;
if (isLeap(y) && m > 2) sum++;    // 闰年 2 月多一天

注意 days[0] = 0 这个占位——让下标从 1 开始对应月份，能省掉一堆 -1。

m > 2 这个条件也别漏：闰年只影响 3 月及以后的日期。

21. 循环综合

这一章是循环板块的收尾，题目都是前面套路的组合。

21.1 边读边更新最优

int best = -1e9, pos = 0;
for (int i = 1; i <= n; i++) {
    int x;
    scanf("%d", &x);
    if (x > best) {
        best = x;
        pos = i;              // 记住位置
    }
}

「记住位置」只要多一个变量。注意用 > 而不是 >=——用 > 时，相同值会保留第一次出现的位置；用 >= 会保留最后一次。题目要哪个，看清。

21.2 枚举找最优解

有些题的最优解没法直接算，只能把所有可能试一遍：

int bestCost = 1e9;
for (int k = 1; k <= 最大值; k++) {
    int cost = 计算方案k的花费();
    if (cost < bestCost) bestCost = cost;
}

这种「枚举所有方案取最优」的写法，只要枚举范围不大就能过。不要觉得暴力很low——能过的暴力就是好算法。

21.3 模拟过程

21.4 状态翻转

「开关灯」这类题：每个操作把一段区间的状态翻转一次。

bool on[1005] = {false};
for (int k = 1; k <= m; k++) {
    for (int i = k; i <= n; i += k) {
        on[i] = !on[i];       // 翻转
    }
}

!on[i] 就是取反。用 bool 数组比用 0/1 的 int 数组更清楚，也省内存。

注意 for (int i = k; i <= n; i += k) 这个写法——它枚举的是 k 的所有倍数，用来做「每隔 k 个操作一次」正合适。

21.5 连续段与双指针

「和为 m 的连续段」是双指针的入门题：

int l = 1, r = 0, sum = 0, cnt = 0;
while (r < n) {
    r++;
    sum += a[r];              // 右端点右移，加入新元素
    while (sum > m && l <= r) {
        sum -= a[l];          // 左端点右移，移除旧元素
        l++;
    }
    if (sum == m) cnt++;
}

思路是：右端点一直往右走，当和超过 m 时，左端点也跟着往右走，直到和不超过 m。两个指针都只往右走，所以总共只扫一遍。

这是第一个「不是简单两重循环」的算法。 如果看不懂，先写个暴力版本（枚举左右端点，两重循环），再回来看这段。

延伸阅读

服务器上有一整套 OI-Wiki（621 页），是给竞赛选手写的参考手册。下面几页跟这一页相关，但不是每一页都该现在看——标了「现在跳过」的，等以后再说。

• 学完这一页再看：抽屉原理 —— 同上，选学。读完能解释「为什么 13 个人里必有两个同月生」
• 学完这一页再看：排列组合 —— 这章是选学，想看就看。组合数的公式推导比结果有用
• 学完这一页再看：斐波那契数列 —— 递推关系的经典例子。看完你写的 f[i] = f[i-1] + f[i-2] 才叫「有根据」
• 学完这一页再看：模拟 —— 「按题目说的步骤一步步走」这个思路的正式名字，以及为什么它容易写错