遞歸--練習4--noi666放蘋果

遞歸--練習4--noi666放蘋果

一、心得

寫出狀态後勇敢假設

二、題目

666:放蘋果

總時間限制: 

1000ms 記憶體限制: 

65536kB

描述

把M個同樣的蘋果放在N個同樣的盤子裡，允許有的盤子空着不放，問共有多少種不同的分法？（用K表示）5，1，1和1，5，1 是同一種分法。

輸入

第一行是測試資料的數目t（0 <= t <= 20）。以下每行均包含二個整數M和N，以空格分開。1<=M，N<=10。

輸出

對輸入的每組資料M和N，用一行輸出相應的K。

樣例輸入

1
7 3      

樣例輸出

8      

三、AC代碼

1 /*
 2 noi666放蘋果
 3 這m個蘋果一定要放 
 4 相當于在m這個隊列裡面分0-n-1刀
 5 對執行個體
 6 0刀：1一種
 7 1刀：
 8 
 9 遞推關系式是什麼樣的呢
10 f(m,n)表示不同的放法 
11 有籃子空：
12 f(m,n)=f(m,n-1)
13 一個籃子都不空：
14 f(m,n)=f(m-n,n)
15 故 f(m,n)= f(m,n-1)+ f(m-n,n)
16 邊界條件：
17 n==1 1
18 m==1 1
19 m<n f(m,m) 
20   
21 */
22 #include <iostream>
23 using namespace std;
24 int f(int m,int n){
25     if(n<=1||m<=1) return 1;
26     if(m<n) return f(m,m);
27     else return f(m,n-1)+ f(m-n,n);
28 }
29 int main(){
30     int a,m,n;
31     cin>>a;
32     for(int i=1;i<=a;i++){
33         cin>>m>>n;
34         int ans=f(m,n);
35         cout<<ans<<endl;
36     }
37     return 0;
38 }      

 ​