GESP 七级 · GESP 202409 C++ 七级 第 12 题

下面程序的输出为（ ）。

#include <iostream>
#define N 10
using namespace std;
int path[N][N];
int main() {
    for (int i = 1; i < N; i++)
        path[i][0] = i;
    for (int j = 1; j < N; j++)
        path[0][j] = j;
    for (int i = 1; i < N; i++)
        for (int j = 1; j < N; j++)
            path[i][j] = path[i - 1][j] + path[i][j - 1];
    cout << path[8][4] << endl;
    return 0;
}

模拟程序执行过程，逐行跟踪变量变化，特别关注循环边界和递归终止条件。

模拟执行时注意：① 循环变量的起始和终止值；② 递归的边界条件；③ 数据类型转换和精度问题。

【考点】递推关系｜动态规划｜组合数性质

核心观察：第一列和第一行是等差数列，内部按"上+左"规则累加，本质是构造带权帕斯卡三角形。递推本质是网格路径计数，但每条路径的权重由起点决定——第一列的 i 相当于从顶部向下走了 i 步的累积值。命题人故意把边界设为非1，卡住那些只会背"杨辉三角=组合数"的考生。

通法：遇到二维递推且边界非全1时，先手算前3行3列找规律，再验证公式。本题可推导 path[i][j] = C(i+j-1, i-1) × (i+j) / (i·j)（略繁琐），但直接模拟循环更快——N=10 时 O(N²)≈100 次运算，人工也能算。注意循环 i,j 从1到N-1，所以数组下标最大到9，path[8][4] 完全合法。

陷阱：选项A 84 是 8×4，对应最浅层的乘法直觉；选项B 495 是 C(12,8)，对应边界全1的帕斯卡三角形；选项D"随机结果"试图诱导忽视循环确定性——其实数组初始化完全确定，无随机性。命题人把第一列设为 1,2,…,N 而非 1，偷换了组合数的权重。若只背结论不看递推式，必选错。

反命题视角：若把循环改成 i,j 从0开始，或把累加改为乘法，答案会彻底变化。刷到类似题先问：边界条件是否非标准？递推是加法还是乘法？这题的核心就是"非标准边界的加法递推"，记住这个特征，以后遇到就能快速判断。