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

下面程序的输出为（ ）。

#include <iostream>
#define N 10
using namespace std;
int h[N];
int main() {
    h[0] = h[1] = 1;
    for (int n = 2; n < N; n++)
        for (int j = 0; j < n; j++)
            h[n] += h[j] * h[n - j - 1];
    cout << h[6] << endl;
    return 0;
}

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

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

【考点】递推关系｜动态规划｜循环边界

本题考查《GESP 大纲》动态规划模块，命题人卡住的是"看到嵌套循环就慌"的弱点，其实它只是用递推定义 Catalan 数。

核心观察：外层 n 从 2 到 N-1（即 9），内层 j 遍历 0..n-1，h[n] 累加 h[j]*h[n-j-1]。这是 Catalan 数标准递推，只需手动算到 h[6]：

• n=2: h[2]=h[0]h[1]+h[1]h[0]=2
• n=3: h[3]=h[0]h[2]+h[1]h[1]+h[2]h[0]=5
• n=4: h[4]=h[0]h[3]+h[1]h[2]+h[2]h[1]+h[3]h[0]=14
• n=5: h[5]=h[0]h[4]+h[1]h[3]+h[2]h[2]+h[3]h[1]+h[4]h[0]=42
• n=6: h[6]=h[0]h[5]+h[1]h[4]+h[2]h[3]+h[3]h[2]+h[4]h[1]+h[5]h[0]=132

故输出 132。

选项 D(随机)是纯干扰，代码无随机函数；B(1430)是 h[8]，C(16796)是 h[9]，命题人利用"循环次数与输出下标"的偷换概念，只背"递推"而不看 n 与 j 的范围，就会把 h[6] 误算成更大值或选错。

若把 N 改为 7，循环只到 n=6，输出仍是 h[6]；若初始化 h[0]=2，整个序列翻倍，答案变 264。