题解 | 华为HJ61#放苹果#

7 3

8

#include <stdio.h>
//以下是Senky的代码
//设f(m,n)为m个苹果，n个盘子的放法数目，则先对n作讨论:
//当n>m：则必定有n-m个盘子永远空着，去掉它们对摆放苹果方法数目不产生影响。即 if(n>m) f(m,n) = f(m,m)
//当n <= m:不同的放法可以分成两类：含有空盘的方案数，不含有空盘的方案数
//含有空盘的方案数，即有至少一个盘子空着，即相当于 f(m,n)=f(m,n-1);
//不含有空盘的方案数，即所有的盘子都有苹果，相当于先每个盘子放一个苹果，再从n个盘子放入m-n个苹果
//不影响不同放法的数目，即 f(m,n)=f(m-n,n).而总的放苹果的放法数目等于两者的和，即 f(m,n)=f(m,n-1)+f(m-n,n)
//递归出口条件说明：
//当n=1时（只有一个盘子），所有苹果都必须放在一个盘子里，所以返回1；
//当m==0(没有苹果可放)时，定义为1种放法；
//用递归解法
int fun(int m, int n) {
    if (n>m) {//盘子比苹果多
        return fun(m,m);//m个苹果放m个盘子
        //以下是盘子小于等于苹果
    } else if (m == 0 || n == 1) {//苹果没有或者盘子只有一个就是一种方法
        return 1;
    } else {
        return fun(m, n - 1) + fun(m - n, n);
    }
}
int main() {
    int m, n;
    while (scanf("%d %d", &m, &n) != EOF) {
        printf("%d\n", fun(m, n));
    }
    return 0;//编辑于2022/10/08
}