题解 | #放苹果#C++递归一共18行代码
放苹果
http://www.nowcoder.com/practice/bfd8234bb5e84be0b493656e390bdebf
递归做多了就跟找规律一样。
先假设盘子>苹果，那一定有n-m个盘子空着，所以此时fun(m,n) = f(m,m)
当盘子<=苹果时，分成含0和不含0两种
含0：至少一个盘子空着f(m,n) = f(m,n-1)
不含0：所有盘子都有苹果，从每个盘子都拿掉一个苹果不会影响结果，此时f(m,n) = f(m-n,n)，但最后结果要算上这部分 所以f(m,n) = f(m,n-1)+f(m-n,n)
#include <iostream>
using namespace std;
int fun(int m, int n) {
if(m==0 || n==1)
return 1;
if(n>m)
return fun(m,m);
else
return fun(m,n-1)+fun(m-n,n);
}
int main()
{
int m,n;
while(cin>>m>>n)
{
cout<<fun(m,n)<<endl;;
}
}
