第九章 · 算法设计技术基础¶

本页最后更新于，内容可能过时

《C语言程序设计（第3版）》第 9 章课后习题，共 9 题。

1 · 二分法求方程的根¶

二分法也是方程求根的常用方法之一。其基本原理是：假定连续方程 f(x)=0 在区间 (a, b) 上因 f(a) 和 f(b) 异号，则在区间 (a,b) 上有根。

具体方法是取区间的中点 x₀=(a+b)/2 将区间分成两半，然后检查 f(x₀) 与 f(a) 是否同号：如果同号，则根位于 x₀ 的右侧；否则，根位于 x₀ 的左侧，由此得到新的有根的区间。如此重复，直至有根的区间达到精度要求时，得到方程根的近似解。

试写出二分法算法的结构，并用二分法求方程 x²-x-1=0 的正根，要求精确到小数点后第 5 位。

答案

二分法算法的结构：

取有根区间 [a, b]，要求两端函数值异号（f(a)·f(b) < 0）。本题取 a = 1、b = 2：f(1) = -1、f(2) = 1。
取中点 x = (a + b) / 2。
比较 f(x) 与 f(a) 的符号：同号说明根在 x 的右侧，令 a = x；异号说明根在 x 的左侧，令 b = x。新区间的长度是原来的一半。
重复第 2、3 步，直到区间长度 b - a 小于给定精度 ε。
输出 (a + b) / 2 作为根的近似解。

程序（精度取 1e-6，比要求的小数点后 5 位再严一档）：

#include <stdio.h>

double f(double x) { return x * x - x - 1; }

int main(void)
{
    double a = 1.0, b = 2.0, x, eps = 1e-6;
    int n = 0;

    while (b - a > eps) {
        x = (a + b) / 2;
        if (f(x) * f(a) > 0)
            a = x;                  /* f(x) 与 f(a) 同号：根在右半区间 */
        else
            b = x;                  /* 异号：根在左半区间 */
        n++;
    }
    printf("迭代次数 %d\n", n);
    printf("x = %.5f\n", (a + b) / 2);
    printf("f(x) = %.3e\n", f((a + b) / 2));
    return 0;
}

输出：

迭代次数 20
x = 1.61803
f(x) = -2.299e-07

解析

f(x) = x² - x - 1 在 [1, 2] 上连续，f'(x) = 2x - 1 在 x ≥ 1 上恒大于 0，所以这个区间内函数单调、正根只有一个。f(1) = -1 与 f(2) = 1 异号，二分法满足收敛条件。

每迭代一次区间长度减半，起始长度是 1，要收到 1e-6 需要 log₂ 10⁶ ≈ 20 次。

几个中间状态（a、b 是每一步更新后的有根区间）：

第 1 次：x = 1.5，f(1.5) = -0.25 与 f(1) = -1 同号，取 a = 1.5。
第 8 次：x = 1.62109375，异号，取 b = 1.62109375，区间收到 [1.61718750, 1.62109375]。
第 20 次：区间收到 [1.61803341, 1.61803436]，长度 9.5e-7，已经小于 1e-6，循环结束。

真机实测（gcc 15.2.0，-O2 -std=gnu23 -Wall）：迭代 20 次，中点打 5 位小数是 1.61803，此时 f(x) = -2.299e-07。

最后一次的区间 [1.61803341, 1.61803436] 整个落在 1.618035 以下，所以不论取区间里哪个点，保留 5 位小数都是 1.61803，这正是"精确到小数点后第 5 位"的保证。

这个根就是黄金分割比 (1 + √5) / 2 = 1.6180339887…，它满足 x = 1 + 1/x，同一次运行里 1/x 是 0.6180340280，x - 1/x 是 0.9999998579。

精度要求用区间长度，不用函数值

改用 |f(x)| < ε 收尾也能算，但对"小数点后第几位"这件事说不清楚：f 在根附近斜率约 2.24，|f(x)| < 1e-6 对应 |x - r| < 4.5e-7；若换成斜率很小的方程，|f(x)| 很小而 x 离根很远。用 b - a 收尾，直接给出根所在区间的长度，与题面的精度提法对得上。

易错：

用 f(x) == 0 当终止条件（浮点数几乎不会恰好为 0，循环停不下来）

把"精确到小数点后第 5 位"当成"迭代 5 次"

循环结束后直接拿循环里最后一次算出的 x 当根（它不一定等于最后的 (a + b) / 2）

同号时该更新哪一端写反（与 f(a) 同号就该更新 a，把根留在新区间里）

2 · 三种迭代格式的收敛性¶

为求方程 x³-x²-1=0 在 1.5 附近的一个根，假定将方程写成下列等价形式，并按等价形式建立相应的迭代公式：

（1）x=1+1/x²；（2）x³=1+x²；（3）x²=1/(x-1)。

试分析每种格式的收敛性，并选取一种等式求出有 4 位有效数字的近似根。

答案

等价形式	迭代公式	收敛性
（1）	`x = 1 + 1/x²`	收敛
（2）	`x = (1 + x²)^(1/3)`	收敛，最快
（3）	`x = 1/sqrt(x-1)`	发散

取格式（2），从 x₀ = 1.5 出发迭代：

迭代次数	`x`
1	`1.4812480342`
2	`1.4727057296`
3	`1.4688173137`
4	`1.4670479732`
5	`1.4662430101`
6	`1.4658768202`

迭代 6 次后误差已经小于 5e-4，取 4 位有效数字得 1.466。

解析

迭代格式 x₁ = φ(x₀)、x₂ = φ(x₁)……是否收敛，看 φ 在根 r 附近的一阶导数：|φ'(r)| < 1 就局部收敛，|φ'(r)| 越小收敛越快；|φ'(r)| > 1 则迭代发散。

先定出根的位置。方程 x³ - x² - 1 = 0 的正根是 r = 1.4655712319…，它让两个等式同时成立，后面的分析都要用：

r³ = 1 + r²（原方程移项），所以 1 + r² = 3.1478990357；
r²(r - 1) = 1（原方程两边除 r），所以 (r - 1)⁻¹ = r² = 2.1478990357。

三种格式的 φ 与导数：

等价形式	`φ(x)`	`φ'(x)`	`φ'(r)`	结论
（1）	`1 + x⁻²`	`-2x⁻³`	`-2/r³ = -0.635344`	绝对值小于 1，收敛
（2）	`(1 + x²)^(1/3)`	`2x / (3(1 + x²)^(2/3))`	`2/(3r) = 0.454885`	绝对值小于 1，收敛最快
（3）	`(x - 1)^(-1/2)`	`-½(x - 1)^(-3/2)`	`-r³/2 = -1.573950`	绝对值大于 1，发散

逐条说明：

（1）把 x = 1 + 1/x² 写成 φ₁(x) = 1 + x⁻²，φ₁'(x) = -2x⁻³，在根处是 -2/r³ = -2/(1 + r²) = -0.635。导数取负说明迭代值在根的两侧来回跳（交替逼近），但绝对值小于 1，仍然收敛。
（2）由 x³ = 1 + x² 得 x = (1 + x²)^(1/3)。求导是 φ₂'(x) = 2x / (3(1 + x²)^(2/3))，在根处 (1 + r²)^(2/3) = (r³)^(2/3) = r²，于是 φ₂'(r) = 2r / (3r²) = 2/(3r) = 0.455。它是三种里最小的，收敛最快。
（3）由 x² = 1/(x - 1) 得 x = 1/sqrt(x - 1)。φ₃'(x) = -½(x - 1)^(-3/2)，在根处 (r - 1)^(-3/2) = ((r - 1)⁻¹)^(3/2) = (r²)^(3/2) = r³，所以 φ₃'(r) = -r³/2 = -1.574，绝对值大于 1，迭代发散。
（1）和（2）都收敛，但（2）的收敛因子更小，所以选（2）求根。从 1.5 出发，第 6 次迭代得 1.4658768202，与根的差是 3.06e-04，已经小于 5e-04，取 4 位有效数字就是 1.466。再迭代到第 12 次是 1.465574，与根 1.4655712319 只差 2.7e-06。

三种格式的迭代序列（程序里就是三行，x 的初值都取 1.5）：

x = 1 + 1 / (x * x);        /* （1） */
x = cbrt(1 + x * x);        /* （2） */
x = 1 / sqrt(x - 1);        /* （3） */

真机实测（gcc 15.2.0，-O2 -std=gnu23 -Wall）：三种格式各迭代若干次，值与根的差分别是——（1）迭代 10 次 x = 1.4659324391，差 3.6e-04；（2）迭代 8 次 x = 1.4656344652，差 6.3e-05；（3）迭代到第 7 次落到 x = 0.8802042510，再下一步 x - 1 < 0，1/sqrt(x - 1) 取不到实值，迭代中断。

格式（3）发散的过程如下：1.5 → 1.4142135624 → 1.5537739740 → 1.3437971925 → 1.7054886638 → 1.1905701238 → 2.2907230820 → 0.8802042510，离根时远时近、摆幅越来越大，最后越过 x = 1 这条界线。

判据里的绝对值不能省

三个导数值 0.455、-0.635、-1.574 都比 1 小，只看"是否小于 1"会把格式（3）也判成收敛。判据是 |φ'(r)| < 1：前两个的绝对值小于 1，收敛；格式（3）的绝对值是 1.574，发散。

cbrt 与 pow 都行，但都要链接数学库

开立方可以直接用 cbrt（C99 起就在数学库里），也可以写 pow(1 + x * x, 1.0 / 3)。两个函数都在 math.h 里，编译时要把 -lm 放在源文件之后。格式（1）只用乘除，不需要数学库。

易错：

只算 φ'(r) 的符号就下结论（要看绝对值）

用 x₀ = 1.5 直接套格式（3）跑下去，序列早就不在实值范围内了

把"4 位有效数字"当成"小数点后 4 位"（1.4656 是 5 位有效数字，1.466 才是 4 位）

迭代次数按"算到误差小于 1e-6"来定——题目只要求 4 位有效数字，第 6 次就够了

3 · 德布鲁因串的回溯生成¶

试用回溯算法产生由 0 和 1 组成 2ᵐ 个二进制位的串，使该串满足以下要求：视串为首尾相连的环，则由 m 位二进制数字组成的 2ᵐ 个子序列，每个可能的子序列都互不相同。

例如，m=3，在串 11101000 首尾相连构成的环中，每 3 位二进制数字组成的每个可能的子序列都在环中出现一次，它们依次是 111、110、101、010、100、000、001、011。

答案

环上共有 2ᵐ 个窗口，而 m 位二进制串总共也只有 2ᵐ 个，所以"窗口两两不同"就等于"每个 m 位串恰好出现一次"。

回溯时逐位定串：每一位先试 1、再试 0，新窗口一凑满就查重，全部 2ᵐ 位定完后再检查首尾相接处的那 m-1 个窗口。

写法一：逐位回溯写法二：德布鲁因图上的欧拉回路

#include <stdio.h>
#include <string.h>

#define MAXM 6
#define MAXN (1 << MAXM)

static int m, N;
static int bits[MAXN];
static int seen[1 << MAXM];

/* 环上从 i 起的 m 位窗口的值 */
static int win(int i)
{
    int j, v = 0;
    for (j = 0; j < m; j++)
        v = (v << 1) | bits[(i + j) % N];
    return v;
}

/* 全部 2^m 位都填好后，检查环绕的那 m-1 个窗口也不重复 */
static int wrap_ok(void)
{
    int i, w;
    for (i = N - m + 1; i < N; i++) {
        if (seen[win(i)]) return 0;
        for (w = N - m + 1; w < i; w++)
            if (win(w) == win(i)) return 0;
    }
    return 1;
}

/* 逐位回溯：第 len 位填 1 优先，0 其次；窗口一完整就登记 */
static int dfs(int len)
{
    int b;
    if (len == N) return wrap_ok();
    for (b = 1; b >= 0; b--) {
        bits[len] = b;
        if (len >= m - 1) {
            int v = win(len - m + 1);
            if (seen[v]) continue;
            seen[v] = 1;
            if (dfs(len + 1)) return 1;
            seen[v] = 0;
        } else {
            if (dfs(len + 1)) return 1;
        }
    }
    return 0;
}

int main(void)
{
    m = 3;
    N = 1 << m;
    memset(seen, 0, sizeof(seen));
    memset(bits, 0, sizeof(bits));
    if (!dfs(0)) { printf("no solution\n"); return 1; }
    for (int i = 0; i < N; i++) printf("%d", bits[i]);
    printf("\n");
    return 0;
}

输出（m=3）：

11101000

把每个 m 位窗口看成一个顶点、每对相邻窗口看成一条边，求串就等价于在图上走一条欧拉回路。这里按 m-1 位结点建图：结点是 m-1 位串，标号为 b 的边从结点 v 指向 (v << 1 | b) 的后 m-1 位，走完所有边就得到一条德布鲁因串。

#include <stdio.h>
#include <string.h>

#define MAXM 7
#define MAXN (1 << MAXM)

static int m, N;
static int used[MAXN][2];      /* 结点 v 上标号为 0/1 的边是否走过 */
static int circuit[MAXN + 2];  /* 欧拉回路经过的结点序列（后序） */
static int clen;
static int bits[MAXN];

/* Hierholzer：优先走标号 1 的边，走出欧拉回路 */
static void hier(int v, int mask)
{
    int b;
    for (b = 1; b >= 0; b--) {
        if (!used[v][b]) {
            used[v][b] = 1;
            hier(((v << 1) | b) & mask, mask);
        }
    }
    circuit[clen++] = v;
}

int main(void)
{
    int i, j, v, ok, nm, mask;

    m = 3;
    N = 1 << m;
    nm = 1 << (m - 1);
    mask = nm - 1;
    memset(used, 0, sizeof(used));
    clen = 0;
    hier(nm - 1, mask);          /* 从全 1 结点出发 */

    /* 后序序列是回路倒序；第 i 条边的标号 = 到达结点的低 1 位 */
    for (i = 0; i < N; i++)
        bits[i] = circuit[N - 1 - i] & 1;

    for (i = 0; i < N; i++) printf("%d", bits[i]);
    printf("\n");

    memset(used, 0, sizeof(used));
    ok = 1;
    for (i = 0; i < N; i++) {
        v = 0;
        for (j = 0; j < m; j++) v = (v << 1) | bits[(i + j) % N];
        if (used[v][0]) ok = 0;
        used[v][0] = 1;
    }
    printf("all %d windows distinct and complete: %s\n", N, ok ? "yes" : "no");
    return 0;
}

输出（m=3）：

10100011
all 8 windows distinct and complete: yes

解析

这道题要的串就是德布鲁因串 B(2, m)：长度 2ᵐ 的 01 串，首尾相接成环后，每个 m 位子序列恰好出现一次。

先把判定条件理清。环上共有 2ᵐ 个窗口（从第 0 位到第 2ᵐ - 1 位各起一个），m 位二进制串的总数也正好是 2ᵐ 个，所以"每个可能的子序列都互不相同"与"每个可能的子序列都出现"是同一件事，回溯时只要保证窗口不重复即可。

写法一的回溯过程：

从第 0 位开始逐位定，每位先试 1、再试 0。第 len 位定下来后，如果 len >= m - 1，说明"从 len - m + 1 位起"的这个窗口已经凑满，查一次重；重复就换下一个候选值。
试到 len == N 时，前面 N - m + 1 个窗口都已查过，还剩环上首尾相接处 m - 1 个窗口（它们的下标跨过了末尾），要单独检查一遍，这一步容易漏掉。
m=3 时第一位到第三位都试 1，凑出窗口 111；第四位试 1 会重复，改试 0 得 110，如此下去正好走到 11101000，与题干的样例串一致。

写法二换个角度看同一个问题：把 m-1 位的串当结点，结点 v 上标号为 b 的边走一步就得到 m 位窗口 v 接上 b。一条"每条边恰好走一次"的回路（欧拉回路）就对应一个德布鲁因串，于是用 Hierholzer 算法求回路，边标号按走过的顺序排出来就是答案。

同样从 m=3 出发，它给出 10100011——也是合法的德布鲁因串，环上 8 个窗口依次是 101、010、100、000、001、011、111、110，同样不重不漏。德布鲁因串本来就不唯一，两种写法各得一个。

真机实测（gcc 15.2.0，-O2 -std=gnu23 -Wall）：两条路线的程序都跑过。写法一在 m=3 得 11101000、窗口序列与题干样例逐项一致，在 m=4 得 16 位串 1111011001010000、在 m=5、m=6 也都走出解且窗口不重不漏；写法二在 m=3 得 10100011，逐窗口核对同样覆盖全部 8 个 m 位串。

窗口总数正好等于串的总数，是两个 2ᵐ

长度是 2ᵐ，环上的窗口也是 2ᵐ 个，m 位串总共 2ᵐ 个——三个数一样，所以"互不相同"与"全部出现一次"等价。写程序时如果把串长误写成 2ᵐ - 1，窗口数就比串的总数少一个，怎么搜都搜不出解。

易错：

只查了不跨末尾的窗口，漏掉环上首尾相接处的 m - 1 个（m=3 时正好会漏掉 001、011 这类窗口）

回溯时不记录"哪些窗口已经用过"，只在最后检查一遍（那等于穷举 2^(2ᵐ) 种串）

取窗口时忘了对 2ᵐ 取模（环上的下标要绕回开头）

把"2ᵐ 个二进制位"读成"2ᵐ 个 m 位窗口"之外的别的量，串长写错

4 · 整数分解成不多于 m 个和数¶

编写将一个整数 n（n<100）分解成不多于 m（m<10）个整数之和的程序。设和数取于数组 d[]，d[] 中的整数互不相等，且自大至小存储，d[] 中共有 c 个整数。

例如，设数组中存储以下整数：d[]={100, 81, 64, 49, 36, 25, 16, 9, 4, 1}。则：

100=100
13=9+4
14=9+4+1
56=36+16+4
71=49+9+9+4

答案

#include <stdio.h>

#define C 10
#define M 9

static int d[C] = {100, 81, 64, 49, 36, 25, 16, 9, 4, 1};
static int pick[M + 1];
static int nterms;

/* 在 limit 个数的上限内搜索 remain 的分解；同一个 d[i] 允许重复取 */
static int search(int remain, int start, int cnt, int limit)
{
    int i;
    if (remain == 0) { nterms = cnt; return 1; }
    if (cnt == limit) return 0;
    for (i = start; i < C; i++) {
        if (d[i] > remain) continue;
        pick[cnt] = d[i];
        if (search(remain - d[i], i, cnt + 1, limit)) return 1;
    }
    return 0;
}

int main(void)
{
    int tests[] = {100, 13, 14, 56, 71};
    int t, n, k, cnt, sum;

    for (t = 0; t < 5; t++) {
        n = tests[t];
        for (cnt = 1; cnt <= M; cnt++)
            if (search(n, 0, 0, cnt)) break;
        sum = 0;
        printf("%d=", n);
        for (k = 0; k < nterms; k++) {
            printf("%s%d", k ? "+" : "", pick[k]);
            sum += pick[k];
        }
        printf("\n");
    }
    return 0;
}

输出：

100=100
13=9+4
14=9+4+1
56=36+16+4
71=49+9+9+4

解析

搜索的办法是回溯，但要按"和数个数从少到多"逐层放宽上限，每一层里都从大数往小数试：

外层让 limit 从 1 增到 m，limit 就是这一轮允许的最大个数。第一个搜到解的那一轮，limit 就是最少个数。
内层从数组开头（最大的 d[0]）往后试，d[i] > remain 的跳过；选走 d[i] 后把余数交给下一层。

为什么必须按个数最少来搜，而不是只卡"不多于 m 个"这个上界：题目给的 5 个等式里，71=49+9+9+4 用了 4 个数，而从最大数开始试会先得到 64+4+1+1+1（5 个数，也没有超过 m = 9 的上界）。

按"个数从少到多、同个数下大数优先"来搜，5 个等式全部能复现，所以答案按这个口径给。

关键点：

递归参数是 (余数, 试到哪个下标, 已用个数, 个数上限)，四样缺一不可：cnt 与 limit 用来卡个数，start 用来说明"从哪儿接着试"。
同一个和数允许重复取——样例 71=49+9+9+4 里 9 就出现了两次。所以下一层传的下标还是 i，不是 i + 1。题干说"d[] 中的整数互不相等"，说的是数组里的元素各不相同，不是"每个元素最多用一次"。
找到解就逐层返回，返回前记下用掉的个数 nterms，主程序照着 pick[0] 到 pick[nterms - 1] 打印等式。
cnt == limit 是这一层能往下走的边界，写成 cnt > limit 会多搜一层，写成 cnt >= limit 则连最后一个数都放不进去。

真机实测（gcc 15.2.0，-O2 -std=gnu23 -Wall）：5 个整数跑下来，等式与题干给的 5 行逐字一致，100、13、14、56、71 用掉的和数个数依次是 1、2、3、3、4，每行都做了求和校验。再把 n = 1 到 99 全部跑一遍，每个数都能分解，最少个数最多是 4 个，远在 m < 10 的上界之内。

n 本身就在 d[] 里时只有一个数

100 恰好在 d[] 里，limit = 1 那一轮就搜到了，等式是 100=100。搜索从 d[0] = 100 开始试，remain - d[i] 一次就减到 0，不会再往下分。

易错：

以为每个和数只能用一次，写 start = i + 1（那 71 就得不到题干的 4 个数等式）

只按"不多于 m 个"搜，从最大数开始试，得到的是 5 个数的解

外层不限个数、一次搜到底（71 会先搜到数更多的组合）

输出等式时把 pick[] 里没用到的旧值也打出来（只打到 nterms - 1）

5 · 从 n 个数中取 r 个的组合¶

找出从自然数 1，2，…，n 中任意取 r 个数的所有组合。例如 n=5，r=3，所有组合为：

1 2 3    1 3 4    2 3 4    3 4 5
1 2 4    1 3 5    2 3 5
1 2 5    1 4 5    2 4 5

提示：采用回溯法找问题的解，将找到的组合按从小到大顺序存于 a[0]，a[1]，…，a[r-1] 中，组合的元素满足以下性质：

（1）a[i+1]>a[i]，后一个数字比前一个大。

（2）a[i]-i<=n-r+1。

按回溯算法思想，寻找解的过程可以叙述如下：

首先放弃组合数个数为 r 的条件，候选组合从只有一个数字 1 开始。因该候选解满足除问题规模之外的全部条件，扩大其规模，并使其满足上述条件（1）。继续这一过程，直至得到候选解满足包括问题规模在内的全部要求，因而是一个解。

在该解的基础上，进行回溯调整寻找下一个解。

答案

#include <stdio.h>

static int n = 5, r = 3;
static int a[8];
static int cnt;

/* 回溯法求组合：a[k] 的取值范围由 a[i]-i<=n-r+1 得到 */
static void comb(int k, int start)
{
    int i, j;
    if (k == r) {
        cnt++;
        for (j = 0; j < r; j++)
            printf("%s%d", j ? " " : "", a[j]);
        printf("\n");
        return;
    }
    for (i = start; i <= n - r + k + 1; i++) {
        a[k] = i;
        comb(k + 1, i + 1);
    }
}

int main(void)
{
    comb(0, 1);
    printf("共 %d 个组合\n", cnt);
    return 0;
}

输出：

解析

a[0] 到 a[r-1] 存当前候选组合，从 k = 0 开始往右定：a[k] 在允许的范围内从小到大试，试一个就递归去定 a[k+1]，定满 r 个就输出。这正是题干说的"从规模为 1 的候选解开始，逐步扩大规模"。

逐条落实：

条件（1）a[i+1] > a[i] 靠"下一层从 a[k] + 1 开始试"实现，同一个数字不会被取两次，组合内部自然是从小到大。
条件（2）a[i]-i <= n-r+1 是下标从 1 起的写法，换成 a[k]（下标从 0 起）就是 a[k] <= n-r+k+1，程序里直接当循环上界用：a[k] 至多取到 n-r+k+1，再往后取，剩下 r-k-1 个位置就放不下比它更大的数了。
k == r 就是"候选解满足包括问题规模在内的全部要求"，此时打印并返回，上一层接着试下一个 a[k]，这就是回溯调整。

输出顺序是按 a[0]、a[1] 从小到大排的：123、124、125，然后 134、135、145，234、235、245，最后一个 345。

题干里把 10 个组合排成 4 列，按列从上往下读，得到的顺序和程序输出完全一致。

真机实测（gcc 15.2.0，-O2 -std=gnu23 -Wall）：程序输出 10 行，与题干样张按列读下来的顺序逐行一致，计数 10 等于 C(5,3)。

循环上界剪掉的是死分支，不是解

a[k] 的上界换成 n 也能得到同样的 10 个组合——因为再往大取，下一层的候选区间会空掉，递归自己就返回了。区别只在白跑多少分支：上界按 n-r+k+1 卡，a[0] 最多试到 3，a[0] = 4、a[0] = 5 这类注定凑不满 r 个的分支根本不进。题干把这条性质单独列出来，就是要这个剪枝。

易错：

下一层传 start 时写成 i 而不是 i + 1（会打印 1 1 1 这种带重复数字的候选）

循环上界写成 n-r+1（漏掉 +k，a[1]、a[2] 的取值被卡得太小，少解）

把组合当成排列，输出前先排序或多打印一遍

n、r 写死在循环层数里，换个规模就得重写程序

6 · 奇数阶魔方阵¶

按以下算法编写生成奇数阶魔方阵的函数。奇数 n 阶魔方阵是指将从 m 开始的连续 n² 个整数 m、m+1、…、n²+m-1 填入到方阵中，使方阵每行、每列以及主、副对角线上各 n 个元素之和都相等。

生成奇数阶魔方阵的过程是：从 m 开始，依次插入各整数，直至填满方阵为止。填数位置的选择方法如下：

（1）第一个位置在最右列的正中。

（2）新位置应当处于最近填数位置的右下方，但如果右下方位置已超出方阵的右边界，则新位置应选行的最左列位置；如果右下方位置已超出方阵的下边界，则新位置应选列的最上一行位置。

（3）另外，在采用以上方法每连续填入 n 个整数后，则新位置是同一行的前一列位置。

图 9-3 是 m=1，n=3 情况下的一个示例。

 4  3  8
 9  5  1
 2  7  5
图 9-3  习题 6

答案

#include <stdio.h>
#include <string.h>

#define MAXN 16

static int a[MAXN][MAXN];

/* 按题给算法生成奇数阶魔方阵：m 是起始数 */
static void odd_magic(int n, int m)
{
    int i, j, cnt;

    memset(a, 0, sizeof(a));
    i = n / 2;              /* （1）第一个位置在最右列的正中 */
    j = n - 1;
    for (cnt = 1; cnt <= n * n; cnt++) {
        a[i][j] = m + cnt - 1;
        if (cnt % n == 0) {                  /* （3）每连续填 n 个数，改到同一行的前一列 */
            j = (j - 1 + n) % n;
        } else {                             /* （2）否则取右下方的位置，越界就绕回 */
            i = (i + 1) % n;
            j = (j + 1) % n;
        }
    }
}

/* 检查每行、每列、两条对角线之和是否都相等 */
static int check(int n, int m)
{
    int i, j, s = 0, t = 0, want = n * (2 * m + n * n - 1) / 2;

    for (i = 0; i < n; i++) {
        int rs = 0, cs = 0;
        for (j = 0; j < n; j++) { rs += a[i][j]; cs += a[j][i]; }
        if (rs != want || cs != want) return 0;
    }
    for (i = 0; i < n; i++) { s += a[i][i]; t += a[i][n - 1 - i]; }
    return s == want && t == want;
}

int main(void)
{
    int i, j, n = 3, m = 1;

    odd_magic(n, m);
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) printf("%4d", a[i][j]);
        printf("\n");
    }
    printf("各行、各列、两条对角线之和都等于 %d：%s\n",
           n * (2 * m + n * n - 1) / 2, check(n, m) ? "是" : "否");

    n = 5;
    odd_magic(n, m);
    printf("n=%d, m=%d 也通过校验：%s\n", n, m, check(n, m) ? "是" : "否");
    return 0;
}

输出（n = 3、m = 1）：

   4   3   8
   9   5   1
   2   7   6
各行、各列、两条对角线之和都等于 15：是
n=5, m=1 也通过校验：是

解析

三条规定的落实办法：

起点 (n / 2, n - 1)，即行号取正中、列号取最右。题目说"最右列的正中"，对奇数阶来说正中就是第 n/2 行（下标从 0 起）。
右下方就是 (i + 1, j + 1)。行、列都用 % n 取模，越出右边界或下边界自动回到最左列、最上一行，正好对上题目里"超出右边界选最左列、超出下边界选最上一行"；两个方向同时越界（右下角）时两个模同时绕回。
"每连续填入 n 个整数后，新位置是同一行的前一列"就是 j = (j - 1 + n) % n，行号不变。判断"连续填了 n 个"用已填个数 cnt 对 n 取模。

第（3）条不能省。以 n = 3 为例，1 填在 (1, 2)、2 填在 (2, 0)、3 填在 (0, 1)；若接下来还按右下方走，第 4 个数的位置正好是 (1, 2)，已经被 1 占了。

改成"同一行的前一列"落到 (0, 0)，后面 5、6 顺次填在 (1, 1)、(2, 2)；填满 6 个数以后再左移一列，得 (2, 1)，7、8、9 依次落在 (2, 1)、(0, 2)、(1, 0)。每一步都不撞格。

校验的口径是"各 n 个元素之和都相等"，相等的那条数对从 m 开始填的方阵是 n(2m + n² - 1) / 2：n = 3、m = 1 时是 15，n = 5、m = 1 时是 65。

真机实测（gcc 15.2.0，-O2 -std=gnu23 -Wall）：n = 3、m = 1 填出的方阵是 4 3 8、9 5 1、2 7 6，三行、三列、两条对角线之和都是 15；换成 n = 5、m = 1 再跑一遍，五行五列两条对角线之和都是 65。

题干图 9-3 的转写与算法结果

题干里图 9-3 转写下来是 4 3 8、9 5 1、2 7 5：三行之和依次是 15、15、14，三列之和依次是 15、15、14，主对角线 14、副对角线 15。按题给算法逐个数推下去，第 9 个数写在末行末格，方阵是 4 3 8、9 5 1、2 7 6，其余 8 格与转写一致，此时三行、三列、两条对角线之和都是 15。上面答案里的方阵和输出都按算法给。

易错：

漏掉第（3）条（n = 3 时第 4 个数就会撞上第 1 个数占的格子）

起点写成 (0, n-1) 或 (n/2, 0)（题目要的是"最右列的正中"）

"同一行的前一列"写成后一列

越界后不取模、直接用 i + 1、j + 1 当下标（数组越界）

7 · 单偶数阶魔方阵¶

按以下给定的算法编写生成单偶数阶魔方阵。整数 n 是单偶数是指 n 是偶数，而 n/2 是奇数。生成单偶阶魔方阵的算法如下：

（1）将单偶阶 n×n 的魔方阵分为 4 个奇数阶的 (n/2) × (n/2) 小方阵，并令这 4 个小方阵按图 9-4 所示编号。

（2）按小方阵的编号的顺序将自然数 1、2、3、……、n² 填入这 4 个奇数阶方阵中；

（0） （3）
（2） （1）
图 9-4  习题 7

（3）对这 4 个小方阵中的部分元素进行互相交换（令 k=(n/2-1)/2）：

① 块（0）中的前 k 行元素与块（3）中的对应元素互换，但其中块（0）与块（3）中的第一行的中间元素不交换。
② 块（0）与块（3）的中心元素互换。
③ 块（2）中最下面的 n/2-k-2 行元素与块（1）中对应元素互换。

答案

#include <stdio.h>
#include <string.h>

#define MAXN 16

static int a[MAXN][MAXN];

/* 把 n×n 的奇数阶魔方阵填到全局方阵的 (r0,c0) 处，起始数为 start */
static void odd_fill(int n, int start, int r0, int c0)
{
    int i = n / 2, j = n - 1, cnt;

    for (cnt = 1; cnt <= n * n; cnt++) {
        a[r0 + i][c0 + j] = start + cnt - 1;
        if (cnt % n == 0)
            j = (j - 1 + n) % n;
        else {
            i = (i + 1) % n;
            j = (j + 1) % n;
        }
    }
}

void singly_even(int n)
{
    int half = n / 2, k = (half - 1) / 2, i, j, t;

    memset(a, 0, sizeof(a));
    /* （2）按小方阵编号 0、1、2、3 的顺序填入 n² 个连续整数 */
    odd_fill(half, 1, 0, 0);                        /* 块（0）左上 */
    odd_fill(half, 1 + half * half, half, half);    /* 块（1）右下 */
    odd_fill(half, 1 + 2 * half * half, half, 0);   /* 块（2）左下 */
    odd_fill(half, 1 + 3 * half * half, 0, half);   /* 块（3）右上 */

    /* ① 块（0）的前 k 行与块（3）的对应元素互换，第一行的中间元素不换 */
    for (i = 0; i < k; i++)
        for (j = 0; j < half; j++) {
            if (i == 0 && j == half / 2) continue;
            t = a[i][j]; a[i][j] = a[i][half + j]; a[i][half + j] = t;
        }

    /* ② 块（0）与块（3）的中心元素互换 */
    i = half / 2;
    t = a[i][i]; a[i][i] = a[i][half + i]; a[i][half + i] = t;

    /* ③ 块（2）最下面的 half-k-2 行与块（1）的对应元素互换 */
    for (i = n - (half - k - 2); i < n; i++)
        for (j = 0; j < half; j++) {
            t = a[i][j]; a[i][j] = a[i][half + j]; a[i][half + j] = t;
        }
}

static int check(int n)
{
    int i, j, s = 0, t = 0, want = n * (1 + n * n) / 2;

    for (i = 0; i < n; i++) {
        int rs = 0, cs = 0;
        for (j = 0; j < n; j++) { rs += a[i][j]; cs += a[j][i]; }
        if (rs != want || cs != want) return 0;
    }
    for (i = 0; i < n; i++) { s += a[i][i]; t += a[i][n - 1 - i]; }
    return s == want && t == want;
}

int main(void)
{
    int i, j, n = 6;

    singly_even(n);
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) printf("%5d", a[i][j]);
        printf("\n");
    }
    printf("n=%d 每行/每列/两条对角线之和都等于 %d：%s\n",
           n, n * (1 + n * n) / 2, check(n) ? "是" : "否");

    n = 10;
    singly_even(n);
    printf("n=%d 同样通过校验：%s\n", n, check(n) ? "是" : "否");
    return 0;
}

输出（n = 6）：

   31    3   35    4   30    8
    9   32    1   36    5   28
    2    7    6   29   34   33
   22   21   26   13   12   17
   27   23   19   18   14   10
   20   25   24   11   16   15
n=6 每行/每列/两条对角线之和都等于 111：是
n=10 同样通过校验：是

解析

单偶数阶（n 是偶数、n/2 是奇数）的方阵拆成 4 个 n/2 阶的小方阵，每个小方阵的阶数都是奇数，可以套用题 6 的奇数阶算法。图 9-4 的编号对应到方阵里是：（0）左上、（3）右上、（2）左下、（1）右下。

三步落实：

“按小方阵编号的顺序”填数，就是 0、1、2、3 依次填：块（0）得 1 到 h²，块（1）得 h²+1 到 2h²，块（2）得 2h²+1 到 3h²，块（3）得 3h²+1 到 4h²（记 h = n/2）。每个小块内部都用题 6 那套奇数阶算法。
k = (h - 1) / 2。第 ① 条在块（0）与块（3）之间按行对换：块（0）的第 i 行（i 从 0 到 k-1）与块（3）的第 i 行逐个元素互换，但第一行（i = 0）的中间那个元素（列号 h/2）保持不动。n = 6 时 k = 1，只换第一行，(0, 1) 和 (0, 4) 两个格子留在原处。
第 ② 条单独换中心元素：块（0）的中心是 (h/2, h/2)，块（3）的中心是 (h/2, h/2 + h)，两个格子直接互换。
第 ③ 条在块（2）与块（1）之间按行对换，换的是块（2）最下面 h - k - 2 行：行号从 n - (h - k - 2) 到 n - 1。n = 6 时这个行数是 0，也就是说第 ③ 条这次不做任何交换；n = 10 时要换 1 行，n = 14 时要换 2 行。

校验口径同样是每行、每列、两条对角线之和都等于 n(1 + n²)/2：n = 6 时是 111，n = 10 时是 505，n = 14 时是 1379。

真机实测（gcc 15.2.0，-O2 -std=gnu23 -Wall）：n = 6 填出的方阵见答案块，六行、六列、两条对角线之和都是 111；n = 10、n = 14 各跑一遍也都通过同一套校验（n = 14 那一次第 ③ 条要换 2 行）。

交换只改变位置，不增删

三条规则都只是把两个格子里的数对调，每个数在方阵里仍然只出现一次。第 ① 条留下的中间元素看得最直接：n = 6 时块（0）第一行是 4 3 8、块（3）第一行是 31 30 35，换完之后这一行是 31 3 35 4 30 8，其中 3 和 30 没参与互换，其余 4 个格子两两对调。

易错：

三个交换的块号配错（①、② 在块（0）与块（3）之间，③ 在块（2）与块（1）之间，③ 不是和块（3）换）

第 ③ 条的行数写成 n/2 - k - 1 或 k + 1（应当是 n/2 - k - 2，n = 6 时正好是 0）

k 按 (n - 1) / 2 算（应当是 (n/2 - 1) / 2）

4 个小块都用同一个起始数，忘了按编号顺序累加（相邻小块之间要差 h²）

8 · 工程雇工的最低费用¶

有一个工程承包人需要确定每月的工人人数，工程承包人知道工程需要工作的月数，每个月需要的最少工人数以及每一个工人的雇用手续费、解雇手续费和每月工资。

试为工程承包人确定工程的最低费用和每月实际雇用的工人数。

答案

设工程要做 n 个月，第 i 个月至少需要 need[i] 名工人；雇用一名工人的手续费是 h、解雇一名的手续费是 r、每名工人每月的工资是 w。第 i 个月实际雇 j 人，且 j ≥ need[i]。

记 f(i, j) 为前 i 个月的最低累计费用、且第 i 个月雇 j 人；设第 i - 1 个月的人数是 k，则

f(i, j) = min{ f(i - 1, k) + c(k, j) } + j·w，

其中 c(k, j) 是把人数从 k 调整到 j 的手续费：j ≥ k 时是 (j - k)·h，j < k 时是 (k - j)·r。

边界：f(0, 0) = 0；第 1 个月没有上一个月可比，f(1, j) = j·h + j·w。

答案：最低费用是 min f(n, j)；每月实际雇用的人数沿取到最小值的那个 k 一层层往回推。j 的上限取 max(need[i]) 就够了——比任何一个月的最少人数还多的工人永远用不上，多雇只会多付工资和手续费。

一组具体数据（题干只给了条件、没有给数，这组是用来演示算法的）：n = 4，need = {4, 6, 5, 3}，雇用手续费 h = 200，解雇手续费 r = 300，月工资 w = 100。

#include <stdio.h>

#define MONTHS 4
#define MAXW 6

static int need[MONTHS + 1] = {0, 4, 6, 5, 3};   /* 每月最少工人数，下标从 1 起 */
static int hire = 200;                            /* 每雇一人 */
static int fire = 300;                            /* 每解雇一人 */
static int wage = 100;                            /* 每人每月工资 */

static int f[MONTHS + 1][MAXW + 1];
static int pre[MONTHS + 1][MAXW + 1];

int main(void)
{
    int i, j, k, best = -1, bestj = -1;

    for (i = 0; i <= MONTHS; i++)
        for (j = 0; j <= MAXW; j++) { f[i][j] = -1; pre[i][j] = -1; }
    f[0][0] = 0;

    for (i = 1; i <= MONTHS; i++)
        for (j = need[i]; j <= MAXW; j++)
            for (k = 0; k <= MAXW; k++) {
                int c;
                if (f[i - 1][k] < 0) continue;
                c = f[i - 1][k] + (k <= j ? (j - k) * hire : (k - j) * fire) + j * wage;
                if (f[i][j] < 0 || c < f[i][j]) { f[i][j] = c; pre[i][j] = k; }
            }

    printf("f(i,j) 表（- 表示该 j 不满足当月最少人数）:\n");
    printf("     j:");
    for (j = 0; j <= MAXW; j++) printf("%7d", j);
    printf("\n");
    for (i = 0; i <= MONTHS; i++) {
        printf("i=%d  :", i);
        for (j = 0; j <= MAXW; j++)
            if (f[i][j] < 0) printf("      -"); else printf("%7d", f[i][j]);
        printf("\n");
    }

    for (j = 0; j <= MAXW; j++)
        if (f[MONTHS][j] >= 0 && (best < 0 || f[MONTHS][j] < best)) { best = f[MONTHS][j]; bestj = j; }
    printf("\n最低费用 = %d，最后一个月人数 = %d\n", best, bestj);

    {
        int plan[MONTHS + 1];
        j = bestj;
        for (i = MONTHS; i >= 1; i--) { plan[i] = j; j = pre[i][j]; }
        printf("每月实际雇用人数：");
        for (i = 1; i <= MONTHS; i++) printf("%s%d", i > 1 ? " " : "", plan[i]);
        printf("\n逐月动作与费用：\n");
        for (i = 1; i <= MONTHS; i++) {
            int prev = (i == 1) ? 0 : plan[i - 1];
            int hc = plan[i] > prev ? (plan[i] - prev) * hire : 0;
            int fc = plan[i] < prev ? (prev - plan[i]) * fire : 0;
            printf("  第 %d 月: 最少 %d 人, 雇用 %d 人, 解雇 %d 人, 月薪合计 %d, 本月支出 %d\n",
                   i, need[i], plan[i] > prev ? plan[i] - prev : 0,
                   plan[i] < prev ? prev - plan[i] : 0, plan[i] * wage, hc + fc + plan[i] * wage);
        }
    }
    return 0;
}

输出：

f(i,j) 表（- 表示该 j 不满足当月最少人数）:
     j:      0      1      2      3      4      5      6
i=0  :      0      -      -      -      -      -      -
i=1  :      -      -      -      -   1200   1500   1800
i=2  :      -      -      -      -      -      -   2200
i=3  :      -      -      -      -      -   3000   2800
i=4  :      -      -      -   3900   3700   3500   3400

最低费用 = 3400，最后一个月人数 = 6
每月实际雇用人数：4 6 6 6
逐月动作与费用：
  第 1 月: 最少 4 人, 雇用 4 人, 解雇 0 人, 月薪合计 400, 本月支出 1200
  第 2 月: 最少 6 人, 雇用 2 人, 解雇 0 人, 月薪合计 600, 本月支出 1000
  第 3 月: 最少 5 人, 雇用 0 人, 解雇 0 人, 月薪合计 600, 本月支出 600
  第 4 月: 最少 3 人, 雇用 0 人, 解雇 0 人, 月薪合计 600, 本月支出 600

这组数据下：最低费用 3400，每月实际雇用 4、6、6、6 人。

解析

这是典型的动态规划：按月分阶段，每个阶段的状态就是"这个月雇几个人"。

为什么状态可以只记人数：一个月的支出只由"上个月人数"和"这个月人数"决定——雇或解雇的手续费看两者的差，工资看这个月的人数。再往前的月份花掉多少，都已经折算进 f(i-1, k) 里，与后面的决策无关（无后效性）。所以从第 1 个月顺着推到第 n 个月就行。

递推式逐项看：

f(i-1, k)：前 i-1 个月的最低累计费用，且第 i-1 个月是 k 人。
c(k, j)：从 k 人调整到 j 人的手续费。人数增加要雇 j - k 人，按 h 计；人数减少要解雇 k - j 人，按 r 计。
j·w：这个月的工资，j 人每人 w。
对 k 取最小，是因为上个月的人数有多个可能，要挑总费用最小的那一个；k 的取值同样要满足 k ≥ need[i-1]（表里不满足的格子是 -，循环里用 f[i-1][k] < 0 挡掉）。

拿输出里的表对着算一遍这组数据：

第 1 个月：f(1, 4) = 4 × 200 + 4 × 100 = 1200，f(1, 5) = 1500，f(1, 6) = 1800。
第 2 个月：只有 j = 6 满足"至少 6 人"，且上个月至少 4 人，所以 f(2, 6) = min{ f(1, 4) + 2 × 200, f(1, 5) + 200, f(1, 6) } + 600 = 1200 + 400 + 600 = 2200。
第 3 个月：这个月至少要 5 人。若沿用上个月的 6 人，f(3, 6) = 2200 + 600 = 2800；若降到 5 人，要多付解雇 1 人的 1 × 300，f(3, 5) = 2200 + 300 + 500 = 3000。两者取小，还是 6 人便宜。
第 4 个月：人数不动是 f(4, 6) = 2800 + 600 = 3400；降到当月最少的 3 人，则上一月是 5 人时解雇 2 人付 600、上一月是 6 人时解雇 3 人付 900，取小的得 f(4, 3) = 3000 + 600 + 300 = 3900，比 3400 贵。所以最优解是 4、6、6、6。

从表里能看出这组数据的走向：解雇手续费（300）比一个月的工资（100）贵，所以人数只升不降——第 3、4 个月的最少人数降到 5 和 3，仍然留着 6 个人更划算。

复杂度：人数上限记作 J = max(need[i])，时间 O(n·J²)（每个月、每个 j 都要枚举 k），空间 O(n·J)。要输出每月人数就再存一个前驱表 pre[i][j]，从最后一个月的最优 j 往回推。

真机实测（gcc 15.2.0，-O2 -std=gnu23 -Wall）：上面那组数据跑出来最低费用 3400，每月人数 4、6、6、6，逐项求和也对得上（1200 + 1000 + 600 + 600 = 3400）。把人数上限从 max(need) = 6 放宽到 12 再算一遍，最低费用和每月人数都不变。

人多了不划算，人少了付不起

j 的下界是当月的最少人数（不够就干不了活），上界是 max(need[i])。上界这一步不用证明得很细：任何一个月的人数超过这个数，多出来的人从头到尾都没被需要过，直接不雇他们，雇用费和工资都省下来，费用只会更低。把上限放宽一倍重算的结果不变，也印证了这一点。

易错：

雇用费和解雇费的方向搞反（人数增加乘 h、人数减少乘 r）

忘了加当月的工资 j·w

枚举 k 时没挡住 k < need[i-1] 的格子（会允许某个月人数低于最少人数）

只算出最低费用就交卷（题目还要"每月实际雇用的工人数"，得存前驱再回推）

把"手续费"当成每月都收（它只在人数变动的那一个月收一次）

9 · 机器人清扫足球场¶

一场激烈的足球比赛之后，场地中被一群足球流氓丢了许多杂物。假定南北向的足球场如一个二维数组，被分成若干个行和列，每个行列位置有多少不等的杂物。现在准备用一个清除杂物的机器人清扫足球场。

机器人从足球场的 0 行 0 列位置出发，只能按列或按行增加的方向前进，不能后退，机器人经过位置的杂物将被机器人清除。

试编写程序，在杂物分布给定的情况下，为机器人确定一个行进路线，使机器人清除的杂物最多。

答案

把球场看成 R 行 C 列的数组 a[i][j]（元素是该位置的杂物数）。机器人从 (0, 0) 出发，每一步只能向右或向下，最终走到 (R-1, C-1)。

记 f(i, j) 为从 (0, 0) 走到 (i, j) 能清掉的最多杂物。走进 (i, j) 只能来自上面 (i-1, j) 或左边 (i, j-1)，所以

f(i, j) = a[i][j] + max(f(i - 1, j), f(i, j - 1))，

第一行只能从左边来（f(0, j) = f(0, j-1) + a[0][j]），第一列只能从上边来（f(i, 0) = f(i-1, 0) + a[i][0]），起点 f(0, 0) = a[0][0]。

清除杂物最多的路线对应的清除量就是 f(R-1, C-1)。要给出具体路线，就从 (R-1, C-1) 往回走：比较 f(i-1, j) 与 f(i, j-1)，沿着大的那一侧退，退到 (0, 0) 再把顺序倒过来。

下面是程序（题干只说了"杂物分布给定"，没有给具体数据，程序里的分布是示例）：

#include <stdio.h>

#define R 4
#define C 5

/* 示意的杂物分布（题干只说了"分布给定"，没有给具体数据） */
static int a[R][C] = {
    {3, 1, 4, 1, 5},
    {9, 2, 6, 5, 3},
    {5, 8, 9, 7, 9},
    {3, 2, 3, 8, 4}
};

static int f[R][C];        /* f[i][j]：从 (0,0) 走到 (i,j) 能清掉的最多杂物 */
static char from[R][C];    /* 'S' 起点，'U' 从上面来，'L' 从左边来 */

int main(void)
{
    int i, j, k, path[R + C][2];

    for (i = 0; i < R; i++)
        for (j = 0; j < C; j++) {
            if (i == 0 && j == 0) { f[i][j] = a[i][j]; from[i][j] = 'S'; continue; }
            if (i == 0)            { f[i][j] = f[i][j - 1] + a[i][j]; from[i][j] = 'L'; continue; }
            if (j == 0)            { f[i][j] = f[i - 1][j] + a[i][j]; from[i][j] = 'U'; continue; }
            if (f[i - 1][j] >= f[i][j - 1]) { f[i][j] = f[i - 1][j] + a[i][j]; from[i][j] = 'U'; }
            else                            { f[i][j] = f[i][j - 1] + a[i][j]; from[i][j] = 'L'; }
        }

    printf("杂物分布:\n");
    for (i = 0; i < R; i++) {
        printf("  ");
        for (j = 0; j < C; j++) printf("%4d", a[i][j]);
        printf("\n");
    }
    printf("f 表（走到每个位置的最大清除量）:\n");
    for (i = 0; i < R; i++) {
        printf("  ");
        for (j = 0; j < C; j++) printf("%4d", f[i][j]);
        printf("\n");
    }

    i = R - 1; j = C - 1; k = 0;
    while (1) {
        path[k][0] = i; path[k][1] = j; k++;
        if (from[i][j] == 'S') break;
        if (from[i][j] == 'U') i--; else j--;
    }
    printf("最多清除杂物 = %d\n", f[R - 1][C - 1]);
    printf("路线（从终点倒推到起点）: ");
    {
        int t;
        for (t = 0; t < k; t++)
            printf("%s(%d,%d)", t ? " -> " : "", path[t][0], path[t][1]);
        printf("\n");
    }
    printf("路线经过位置的杂物: ");
    {
        int t, sum = 0;
        for (t = k - 1; t >= 0; t--) {
            printf("%s%d", t < k - 1 ? "+" : "", a[path[t][0]][path[t][1]]);
            sum += a[path[t][0]][path[t][1]];
        }
        printf(" = %d\n", sum);
    }
    return 0;
}

输出：

杂物分布:
     3   1   4   1   5
     9   2   6   5   3
     5   8   9   7   9
     3   2   3   8   4
f 表（走到每个位置的最大清除量）:
     3   4   8   9  14
    12  14  20  25  28
    17  25  34  41  50
    20  27  37  49  54
最多清除杂物 = 54
路线（从终点倒推到起点）: (3,4) -> (2,4) -> (2,3) -> (2,2) -> (2,1) -> (2,0) -> (1,0) -> (0,0)
路线经过位置的杂物: 3+9+5+8+9+7+9+4 = 54

把倒推出来的次序正过来，路线是 (0,0) → (1,0) → (2,0) → (2,1) → (2,2) → (2,3) → (2,4) → (3,4)，共清掉 54 处杂物。

解析

题面的"只能按列或按行增加的方向前进"就是每一步只能向右或向下：行号不减、列号不减，并且不回头。所以从起点到终点的任何一条路线都恰好经过 R + C - 1 个位置。

为什么不能一步一步贪心："先往杂物多的邻居走"这种走法只看眼前一格，走进哪条路要到最后才知道。

而"到 (i, j) 能清掉多少"这件事只取决于"到上面那格清掉多少"和"到左边那格清掉多少"，这就是最优子结构，可以按行、列从小到大把 f 表算满。

用手推一遍表里的两个位置：

f(2, 1)：位置 (2, 1) 有 8 处杂物。从上面来是 f(1, 1) = 14，从左边来是 f(2, 0) = 17，取大的 17，得 f(2, 1) = 8 + 17 = 25。
f(3, 4)：终点有 4 处杂物。上面是 f(2, 4) = 50，左边是 f(3, 3) = 49，取 50，得 f(3, 4) = 4 + 50 = 54。

回推路线时，正是靠 f(i-1, j) 与 f(i, j-1) 谁大来判断"这一步是从上面来的还是从左边来的"：终点处 50 > 49，所以最后一格是从上面 (2, 4) 走进来的；(2, 4) 处上面是 28、左边是 41，从左边来；如此一路退到 (0, 0)。

程序里把这个判断记在 from 表里，回推时直接查。

复杂度：每个格子算一次、比较两次，时间 O(R·C)，空间 O(R·C)（要还原路线就得把 f 和 from 都留着；只求最大值的话可以只留一行）。

真机实测（gcc 15.2.0，-O2 -std=gnu23 -Wall）：上面那份示例分布跑出来最大值是 54，路线是 (0,0) → (1,0) → (2,0) → (2,1) → (2,2) → (2,3) → (2,4) → (3,4)，沿途杂物 3+9+5+8+9+7+9+4 相加正好是 54，与 f 表右下角一致。

为什么每一步只能右、下，路线长度就是固定的

行号从 0 涨到 R-1 要走 R-1 次向下，列号从 0 涨到 C-1 要走 C-1 次向右，两次动作的先后可以换，但各自次数不变，所以任何一条路线都经过 (R-1) + (C-1) + 1 = R + C - 1 个位置。示例里是 4 + 5 - 1 = 8 个位置，与输出的路线长度一致。

易错：

把"只能按列或按行增加的方向前进"读成"可以左右横跳，只要最后到终点"（那样问题完全不同）

用贪心代替动态规划（每步挑杂物多的邻居），结果不一定最优

回推路线时拿当前格的杂物数或 f 值去比（要比的是两个前驱的 f 值）

第一行、第一列也去取 max（它们只有一个来向，另一侧要按 0 或按"不存在"处理）

输出路线时忘了把倒推得到的次序反过来（从终点写到起点）

习题自测登记：完成本章习题后在此登记