NOIP 普及 2011 第一轮 第 26 题：递归函数计算组合数量

题目

```
#include<iostream>
using namespace std;

int solve(int n,int m)
{
    int i,sum;
    if(m==1) return 1;
    sum=0;
    for(i=1;i<n;i++)
       sum+= solve(i,m-1);
    return sum;
}

int main()
{
    int n,m;
    cin>>n>>m;
    cout<<solve(n,m)<<endl;
    return 0;
}
```

输入：7 4

阅读程序写结果

答案

20

题解

考点定位

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

解题过程

solve(n,m)：m=1 返回 1；否则 Σ_{i=1}^{n−1} solve(i,m−1)。递推即「组合数」：

$$solve(n,m)=\binom{n-1}{m-1}$$

（Pascal 恒等式逐层展开。）原卷输入 7 4：solve(7,4)=C(6,3)=20。

验证：solve(1..6,3) = C(0,2)+C(1,2)+…+C(5,2) = 0+0+1+3+6+10 = 20 ✓。

答案：20。

易错提醒

① 识别递归 = 组合数（杨辉三角求和）可秒算；② 别逐层硬展开，代恒等式 Σ_{i=m-1}^{n-1}C(i,m−1)=C(n,m)。