NOIP 提高组初赛 · NOIP 2014 提高组初赛试题 第 24 题

#include <stdio.h>
int fun( int n, int minNum, int maxNum )
{
	int tot, i;
	if ( n == 0 )
		return(1);
	tot = 0;
	for ( i = minNum; i <= maxNum; i++ )
		tot += fun( n - 1, i + 1, maxNum );
	return(tot);
}


int main()
{
	int n, m;
	scanf( "%d%d ", &n, &m );
	printf( "%d\n", fun( m, 1, n ) );
	return(0);
}

输入： 6 3 输出：________

这题别一上来就套公式，先把 fun 函数拆开看：它是在 [minNum, maxNum] 里选 n 个递增数，本质就是组合数 C(maxNum-minNum+1, n)。输入是 fun(3,1,6)，直接代入算 C(6,3) 就行，手算或画图枚举都能很快得出 20。

很多学生看到递归就慌，要么把参数顺序搞错，把 fun(3,1,6) 当成从 1 到 3 选 6 个数（那根本不可能），要么死记硬背 C(n,m) 公式却忘了这题里 n 和 m 的角色是反过来的——这里的 n 是选几个数，maxNum-minNum+1 才是总数。还有人会试图用递推填表去算，虽然也能出答案，但容易在边界条件上出错，比如 n=0 时返回 1 这个终止条件，很多人会漏掉或者理解成 n=1 时返回 1，导致整棵递归树算偏，最后数字对不上。

考点与概念

这道题核心考的是递归函数的语义理解与组合数的等价转换。函数定义为 fun(n, minNum, maxNum)，参数含义是：从区间 [minNum, maxNum] 中选出 n 个严格递增的整数，问有多少种选法。

在计算机里，选出一组递增数，等价于从总数里挑出几个，顺序自动固定（从小到大），这就是经典的组合数模型。区间里有多少个数？maxNum - minNum + 1。要选几个？n。所以函数返回值就是数学上的组合数 $C(\text{maxNum} - \text{minNum} + 1, n)$。

命题视角：为什么考这个？

命题人喜欢用递归包装组合数，原因有二：一是考察你对递归终止条件和状态转移的敏感度；二是看你是否能透过代码看到数学本质，而不是机械地模拟递归过程。这道题的递归写法非常经典：

case n == 0: return 1;  // 选 0 个，只有一种方案：什么都不选
for i = minNum to maxNum:
    tot += fun(n-1, i+1, maxNum); // 选第一个数是 i，剩下的 n-1 个从 i+1..maxNum 里选

这其实就是组合数的递推公式 $C(N, K) = \sum_{i=1}^{N} C(N-1, K-1)$ 的直接实现。命题人挖的坑往往就在参数对应关系上：很多人看到 fun(3,1,6) 就下意识以为“从 1 到 3 选 6 个数”，完全忽略了第一个参数是选几个，第二个参数是起始位置。这个错位一旦发生，后面所有计算都会跑偏。