这个题是在搜索与回溯中的,但我也没有想到用搜索,用了递归。
其实递归我并不是很会用,只是通过这个题更深刻了解递归。
函数:
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 }