GESP 八级 · GESP 202506 C++ 八级 第 10 题

下面程序的输出为（ ）。

#include <iostream>
const int N = 10;
int ch[N][N][N];
int main() {
    for (int x = 0; x < N; x++)
        for (int y = 0; y < N; y++)
            for (int z = 0; z < N; z++)
                if (x == 0 && y == 0 && z == 0)
                    ch[x][y][z] = 1;
                else {
                    if (x > 0)
                        ch[x][y][z] += ch[x - 1][y][z];
                    if (y > 0)
                        ch[x][y][z] += ch[x][y - 1][z];
                    if (z > 0)
                        ch[x][y][z] += ch[x][y][z - 1];
                }
    std::cout << ch[1][2][3] << std::endl;
    return 0;
}

位运算：&（与）、|（或）、^（异或）、~（取反）、<<（左移）、>>（右移）。异或性质：a^a=0，a^0=a。

区分逻辑运算(&&,||,!)和位运算(&,|,~,!)。左移右移注意符号位的处理（算术右移vs逻辑右移）。负数的位运算要小心。

【考点】三维数组递推｜组合数计算｜动态规划思想

本题考查三维数组递推与组合数计算，属于 GESP 八级算法模块中「递推与动态规划」的核心题型。命题人将经典的三维组合数公式转化为代码实现，意在考察学生对多维数组索引逻辑的理解，以及能否从循环结构抽象出数学规律——这是八级考生从「会写代码」迈向「会分析算法」的关键分水岭。

核心观察点有三：第一，三维数组 ch[N][N][N] 全局变量初始化为 0，仅 ch[0][0][0] 被赋值为 1，这相当于三维坐标系原点设为单位计数；第二，递推逻辑中 if (x>0) ch[x][y][z] += ch[x-1][y][z] 等三行，本质是累加前驱节点的值，对应组合数学中的「三维路径计数」模型——从原点走到 (x,y,z) 只允许沿正方向移动，每一步贡献 1 条路径；第三，直接代入公式计算：ch[1][2][3] = (1+2+3)! / (1!×2!×3!) = 720 / 12 = 60。通法总结为：将多维递推视为组合数展开，最终答案即 C(x+y+z, x, y, z) 的三阶乘形式。

选项 D(10) 是典型「只看到单次递推」的陷阱，误以为 ch[1][2][3] 只累加一次 ch[0][2][3] 等值，却忽略三重嵌套循环中每一层都在不断累积前驱；选项 B(20) 来自组合数 C(6,3) 的错误联想，命题人故意用「二维组合数」的常见公式混淆「三维路径计数」；选项 C(15) 则是将 ch[1][2][3] 误算为 1×2×3 的乘积，完全脱离递推逻辑。最阴险的细节在于 if (x==0 && y==0 && z==0) ch[x][y][z]=1 这一行——若考生只关注循环体中的 else 部分，会误以为所有点都是累加得到，从而忽略原点作为「种子」的唯一性，导致后续计算全部错位。

反命题视角下，若将 ch[1][2][3] 改为 ch[2][2][2]，答案变为 C(6,2,2,2) = 90；若改为求整个数组元素之和，则需计算 C(0,0,0) + C(1,0,0) + ...，本质是三维组合数求和，复杂度从 O(1) 升至 O(N³)。刷到此类题时，先问自己：「命题人想考我三维递推还是二维组合数？」——这是区分八级与九级的关键分水岭。