NOIP 普及 2017 第一轮 第 24 题：递归函数 g 计算非降分拆方案数

题目

```
#include<iostream>
using namespace std;
int g(int m, int n, int x)
{
    int ans = 0;
    int i;
    if (n == 1)
        return 1;
    for (i = x; i <= m / n; i++)
        ans += g(m - i, n - 1, i);
    return ans;
}
int main()
{
    int t, m, n;
    cin >> m >> n;
    cout << g(m, n, 0) << endl;
    return 0;
}

```
输入：7 3    
输出：_________

阅读程序写结果：

答案

8

题解

考点定位

非递减非负整数拆分。

解题过程

实际输入为 7 3，调用 g(7,3,0)。参数 x 限制下一项不小于上一项，因此程序计数的是把 7 拆成 3 个非递减非负整数的方案。

首项只可能为 0、1、2，逐项列出：

• 首项 0：(0,0,7)、(0,1,6)、(0,2,5)、(0,3,4)，共 4 种。
• 首项 1：(1,1,5)、(1,2,4)、(1,3,3)，共 3 种。
• 首项 2：(2,2,3)，共 1 种。

当 n=1 时，剩余总和唯一确定最后一项，因此返回 1。合计 4+3+1=8。

答案：8。

易错提醒

初始下界是 0，允许出现 0；递归传入 i，允许相邻项相等。不要把输入换成 8 4。