1222 放苹果

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 }

 

1222 放苹果

上一篇:PP: Unsupervised anomaly detection via variational auto-encoder for seasonal KPIs in web applications


下一篇:浅析一种基于Android、iOS平台的移动端车牌识别技术