CSP-S 2025 第一轮 第17题：程序阅读第 1 题 · 第 2 小题

题目

#include <algorithm>
#include <cstdio>
#include <cstring>
bool flag[27];
int n;
int p[27];
int ans = 0;
void dfs(int k) {
    if (k == n + 1) {
        ++ans;
        return;
    }
    for (int i = 1; i <= n; ++i) {
        if (flag[i]) continue;
        if (k > 1 && i == p[k - 1] + 1) continue;
        p[k] = i;
        flag[i] = true;
        dfs(k + 1);
        flag[i] = false;
    }
    return;
}
int main() {
    scanf("%d", &n);
    dfs(1);
    printf("%d\n", ans);
    return 0;
}

在 dfs 函数运行过程中，$k$ 的取值会满足 $1 \leq k \leq n+1$。

选项

• T. 正确
• F. 错误

答案

T

题解

参考答案是 T（正确）。按这组程序题通常使用的非负 $n$，看递归参数 k 怎样变化：

• 一开始调用 dfs(1)，所以 k 最小为 1。
• 每深入一层，调用 dfs(k + 1)。
• 到 k == n + 1 时立即 return，不会再进入下一层。

因此运行中的 k 满足 $1\le k\le n+1$。k=n+1 表示前 $n$ 个位置都已填好，正好是计数并返回的那一层。

题面没有单独写出 $n$ 的下界。如果允许输入负数，dfs(1) 就不满足所说范围；参考答案显然按通常的非负输入前提作答。