HJ61 放苹果

参考 https://blog.nowcoder.net/n/c9bc6821b3cd469b9cdb56469809e946

设f(m,n)为m个苹果，n个盘子的放法数目，则先对n作讨论，

当m<n：必定有n-m个盘子永远空着，去掉它们对摆放苹果方法数目不产生影响，即if(n>m) f(m,n) = f(m,m) 问题变成m个苹果，m个盘子的问题。也就是下面的m>=n的情况

当m>=n：不同的放法可以分成两类：

1、有至少一个盘子空着，原则上相当于f(m,n) = f(m,n-1) + f(m,n-2) + f(m,n-3)... 但是考虑到f(m,n-2)包含在f(m,n-1)中（这里思考下！），避免重复统计，则f(m,n) = f(m,n-1)

2、所有盘子都有苹果，相当于可以从每个盘子中拿掉一个苹果，不影响不同放法的数目，即f(m,n) = f(m-n,n).

则总的放苹果的放法数目等于两者的和，即 f(m,n) =f(m,n-1)+f(m-n,n)

递归出口条件说明： 当n=1时，所有苹果都必须放在一个盘子里，所以返回１； 当m=0时，没有苹果可以放置，返回１种放法； 递归的两条路，第一条n会逐渐减少，终会到达出口n==1; 第二条m会逐渐减少，因为n>m时，我们会return f(m,m)　所以终会到达出口m==0．

代码拷贝参考的

#include <stdio.h>

int fun(int m, int n)
{
    if(m==0||n==1)
    {
        return 1;
    }
    else if(m<n)
    {
        return fun(m,m);
    }
    else
    {
        return fun(m-n,n)+fun(m,n-1);
    }
}
int main()
{
    int a,b,num;
    while(~scanf("%d%d",&a,&b))
    {
        num = fun(a,b);
        printf("%d\n",num);
    }
}

参考 https://www.nowcoder.com/profile/683457556/codeBookDetail?submissionId=80908688