1222 放苹果

这个题是在搜索与回溯中的，但我也没有想到用搜索，用了递归。

其实递归我并不是很会用，只是通过这个题更深刻了解递归。

函数：

1 int f(int m,int n)
2 {
3     if(m==0||n==1)
4         return 1;
5     if(n>m)
6         return f(m,m);
7     else
8         return f(m,n-1)+f(m-n,n);
9 }

先分为两种情况。

第一种是盘子数目大于苹果数目（n>m），这种情况无论怎么放，都会有(n-m)个盘子空着，所以直接把这（n-m）个盘子去掉，在调用f（m,m）就可以。

第二种是苹果数目大于盘子数目（m>=n），这样有分为两种情况，一种是最后有空盘子，另一种是最后没有空盘子。最后再将这两种情况加起来就可以。有空盘子在依次分有几个空盘子。

完整代码：

 1 #include<iostream>
 2 using namespace std;
 3 int a[30];
 4 int f(int m,int n)
 5 {
 6     if(m==0||n==1)
 7         return 1;
 8     if(n>m)
 9         return f(m,m);
10     else
11         return f(m,n-1)+f(m-n,n);
12 }
13 int main()
14 {
15     int k=0,t,m,n;
16     cin>>t;
17     while(t>0)
18     {
19         cin>>m>>n;
20         k++;
21         a[k]=f(m,n);
22         t--;
23     }
24     for(int i=1;i<=k;++i)
25     {
26         cout<<a[i]<<endl;
27     }
28     return 0;
29 }