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

题目

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

当输入的 $n=4$ 的时候，程序输出的答案为（ ）。

选项

• A. $11$
• B. $12$
• C. $24$
• D. $9$

答案

A

题解

答案是 A．\(11\)。

这段程序用 DFS 枚举 \(1\sim n\) 的排列，有两个限制：

• if (flag[i]) continue;：已经用过的数字不能再选。
• if (k > 1 && i == p[k - 1] + 1) continue;：当前数字不能恰好比前一个数字大 \(1\)。

所以，当 \(n=4\) 时，要统计不包含相邻的 12、23、34 的排列数。注意，21、32、43 是允许的。

按第一个数字分类，所有合法排列如下：

每找到一个完整排列，就执行一次 ++ans，因此输出： \[ 2+3+3+3=\boxed{11}. \]