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

题目

#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;
}

删除第 19 行的 flag[i]=false;，对答案不会产生影响。

选项

• T. 正确
• F. 错误

答案

F

题解

选 F，错误。

flag[i] 表示数字 i 是否已被当前排列使用。递归返回后，flag[i] = false; 用来回溯，撤销本次选择，让其他分支还能使用这个数字。

用 n = 2 举例：

• 原程序：1 2 不合法，因为后一个数恰好是前一个数加 1；2 1 合法，所以输出 1。
• 删除后：先尝试以 1 开头，没有找到合法排列，但 flag[1] 一直为 true。接着尝试以 2 开头时，无法再选 1，因此也找不到合法排列，输出 0。

答案发生了变化，所以该说法错误。