NOIP 提高 2014 第一轮 第 24 题：递归计算组合数 C(n,m)

题目

```
#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  
输出：________

请写出程序的输出结果。

答案

20

题解

考点定位

本题考「递归组合数」,对应大纲 4.2.3 递归（难度【3】）。

解题过程

fun(n,minNum,maxNum)：从 [minNum,maxNum] 中选 n 个严格递增数的方案数 = C(maxNum−minNum+1? , n)。fun(3,1,6) = C(6,3) = 20。

验证：fun(0,·)=1；fun(1,1,6)=6；fun(2,i,6)=Σ… 组合数解释自洽。

答案：20。

易错提醒

① 递归含义：枚举第一个选的数 i，剩余从 i+1 起选 n−1 个；② 组合数 C(6,3)=20 直接得解。