NOIP 提高组初赛 · NOIP 2008 提高组初赛试题 第 25 题

#include<iostream>
using namespace std;
void f(int a, int b, int c)
{
	cout << a << b << c << ‘/’;
	if(a == 3 && b == 2 && c == 1)
		return;
	if(b < c)
		f(a, c, b);
	else if(a < b)
	{
		if(a < c)
			f(c, a, b);
		else
			f(b, c, a);
	}
}

int main()
{
	int a, b, c;
	cin >> a >> b >> c;
	f(a, b, c);
	cout << endl;
	return 0;
}

输入: 1 3 2 输出： _______

这题考递归全排列生成。拿到题先别急着看代码，先想终止条件：只有到(3,2,1)才停。输入是1,3,2，递归里每次要么交换b,c，要么按大小关系轮转，顺着这个逻辑一步步推，直到撞墙。

最容易栽跟头的是把终止条件看成普通的递归结束，或者在判断分支时把‘<’和‘<=’搞混。比如b<c时直接交换，很多人会忽略else里还要再分a<c还是a>=c，导致漏掉一种轮转。还有就是在追踪时把打印顺序搞反，以为是从大到小排，其实代码里是先打印再递归，所以输出顺序就是递归调用的先后顺序。另外，题目给的输入1 3 2，有人会误以为是1 2 3，把初始状态搞错，后面全乱套。

程序阅读（递归全排列生成）

本题考查递归函数中通过参数重排生成全排列的过程。

#include<iostream>
using namespace std;
void f(int a, int b, int c)
{
    cout << a << b << c << '/';       // 打印当前排列
    if(a == 3 && b == 2 && c == 1)
        return;                       // 终止条件：到达 (3,2,1)
    if(b < c)
        f(a, c, b);                   // 交换 b、c
    else if(a < b)
    {
        if(a < c)
            f(c, a, b);               // 轮转：新顺序 (c,a,b)
        else
            f(b, c, a);               // 轮转：新顺序 (b,c,a)
    }
}
int main()
{
    int a, b, c;
    cin >> a >> b >> c;   // 读入 1 3 2
    f(a, b, c);
    cout << endl;
    return 0;
}

输入： 1 3 2

递归追踪（生成所有排列直到 (3,2,1)）：

输出结果： 132/213/231/312/321/

算法本质：该递归以字典序生成 (1,2,3) 的全排列，每次选择一种重排策略（交换或轮转），直到到达 (3,2,1) 终止。

心算技巧：画状态转移图——每个排列是一个节点，箭头指向下一个排列，直线追踪直到终止条件。

详细解析

考点定位

这道题的核心是递归函数与全排列生成的结合。在信息学竞赛中，递归是高频考点，尤其是像这种通过参数轮换来生成排列的题目，往往用来考察学生对递归调用栈的理解和手动模拟能力。

概念梳理

先说清楚递归是怎么工作的：函数自己调用自己，直到满足某个终止条件才停止。每次调用都会把当前的参数传进去，然后执行一段逻辑，最后可能再调用一次自己，形成一条调用链。在这道题里，函数f(a, b, c)每次先打印当前的三个数，然后判断要不要继续递归。

命题人视角

命题人为什么选这个题？因为代码很短，但逻辑有点绕。它不是简单的swap(a,b)，而是根据大小关系决定是交换还是轮转。轮转又分两种情况：如果a < c，就变成(c, a, b)；否则变成(b, c, a)。这种分支判断很容易让人在手动追踪时出错，特别是当输入不是最普通的1 2 3，而是1 3 2的时候，初始状态就变了，后续的路径也会不同。

思考心法

拿到这种题，第一步是找终止条件。题目里写得很清楚：if(a == 3 && b == 2 && c == 1) return;。这意味着整个递归树的最深节点就是(3,2,1)，而且只有到达这个状态才会停止。所以只要我们在追踪过程中看到这个状态，就可以确定不会再有后续输出了。

第二步是模拟调用过程。从main函数开始，输入是1 3 2，所以首先进入f(1, 3, 2)。在这个函数里，先执行cout << a << b << c << '/'，输出132/。然后判断条件：b < c吗？3 < 2是假的，所以进入else if(a < b)。1 < 3是真的，再进入内部判断：a < c吗？1 < 2是真的，所以调用f(c, a, b)，也就是f(2, 1, 3)。

接下来进入f(2, 1, 3)。先输出213/。判断条件：b < c吗？1 < 3是真的，所以直接调用f(a, c, b)，即f(2, 3, 1)。

进入f(2, 3, 1)。先输出231/。判断条件：b < c吗？3 < 1是假的，进入else if(a < b)。2 < 3是真的，内部判断：a < c吗？2 < 1是假的，所以调用f(b, c, a)，即f(3, 1, 2)。

进入f(3, 1, 2)。先输出312/。判断条件：b < c吗？1 < 2是真的，所以调用f(a, c, b)，即f(3, 2, 1)。

进入f(3, 2, 1)。先输出321/。判断条件：a == 3 && b == 2 && c == 1，完全满足，直接return。递归结束，程序输出换行，结束。

避坑指南

这里最容易掉进的坑有两个：

1. 分支判断顺序：很多人看到else if(a < b)就以为只要a < b就一定会进入轮转，忽略了内部还有if(a < c)和else的区分。如果漏了这个细节，就会错误地认为从f(2,3,1)下一步是f(3,2,1)（直接交换），而实际上应该走轮转变成f(3,1,2)。这个错误会导致输出顺序完全不对。

2. 终止条件理解：题目给的终止条件是a==3 && b==2 && c==1，而不是a==3 && b==2。如果你只检查前两个数，可能会以为在某个中间状态就停了，多输出一堆不该有的排列。比如有人可能误以为f(3,2,1)之后还会再调用一次，其实不会。

3. 输入初始状态：题目输入是1 3 2，不是1 2 3。很多人习惯性地从1 2 3开始推，结果第一层输出就错了。一定要严格按题目给的输入来模拟。

考频与趋势

从题库数据来看，函数与递归是历年必考内容，共出现过67次，覆盖从GESP二级到NOIP提高组初赛等多个级别。其中2023年考了13题，2024年考了18题，2025年考了21题，说明这两年递归相关题目数量激增，命题人明显在加大难度和覆盖面。而在2008年，这类题目已经出现过2次，说明这个考点其实很老，但每年都在以不同形式回归。

预测

基于2023-2025年递归题目数量持续上升的趋势，以及2026年已经有6题的分布，可以合理预测：未来几年（2027-2028）递归与全排列、递归终止条件判断、递归调用栈模拟这类题目仍将保持高频率出现，且可能会结合更复杂的逻辑（比如递归中嵌套循环、递归中涉及数组操作等）来增加区分度。暂无足够依据预测具体年份的题量，但可以肯定的是，这类题目不会降温，反而可能成为压轴常客。