poj1664-放蘋果(遞歸)，poj1664-放蘋果遞歸

poj1664-放蘋果(遞歸)，poj1664-放蘋果遞歸

一，題意：
　　M個蘋果放在N個盤子裡，允許有盤子空著，問共有多少種不同的分法。
二，思路：
　　遞歸的思想求解：
　　　　1，有反復執行的過程(調用本身)
　　　　　　第一種情況n>m : 必定有 n-m 個盤子空著，去掉不影響。
　　　　　　第二種情況n<=m :
　　　　　　　　i，有至少一個盤子空著;
　　　　　　　　ii，每個盤子都有蘋果;
　　　　　　　　總的放蘋果的方法數為兩者之和：
2，有跳出反復執行過程的條件(遞歸出口)
　　當蘋果放完或者只有一個盤子的時候
　　　*遞歸兩條路：
　　　　i，n會逐漸減少，最終到達出口 n==1 ；
　　　　ii，m逐漸減少，因為n>m時，return work(m,m),所以終會到達出口 m==0;
三，步驟：
　　1,if(n>m) work(m,n) = work(m,m) ;
　　　else
　　　　i,work(m,n) = work(m,n-1);
　　　　ii,work(m,n) = work(m-n,n);
　　　work(m,n) = work(m,n-1) + work(m-n,n);
　　2,if(m==0||n==1) return 1;

1 #include<iostream> 2 using namespace std; 3 4 int work(int m , int n){ 5 if(m==0||n==1) 6 return 1; 7 if(n>m) 8 return work(m,m); 9 else 10 return work(m,n-1)+work(m-n,n); 11 } 12 13 int main(){ 14 int t , m , n ; 15 cin>>t; 16 while(t--){ 17 cin>>m>>n; 18 cout<<work(m,n)<<endl; 19 } 20 return 0; 21 } View Code

注意：
　　1，遞歸就是在過程或函數裡調用自身
　　2，在使用遞歸策略時，必須有一個明確的遞歸結束條件，稱為遞歸出口。
　　3，遞歸算法解題通常顯得很簡潔，但遞歸算法解題的運行效率較低。所以一般不提倡用遞歸算法設計程序。
　　4， 在遞歸調用的過程當中系統為每一層的返回點、局部量等開辟了棧來存儲。遞歸次數過多容易造成棧溢出等。所以一般不提倡用遞歸算法設計程序。
要求：
　　1，每次調用在規模上都有所縮小(通常是減半)；
　　2，相鄰兩次重復之間有緊密的聯系，前一次要為後一次做准備(通常前一次的輸出就作為後一次的輸入)；
　　3，在問題的規模極小時必須用直接給出解答而不再進行遞歸調用，因而每次遞歸調用都是有條件的(以規模未達到直接解答的大小為條件)，無條件遞歸調用將會成為死循環而不能正常結束。

版權聲明：本文為博主原創文章，未經博主允許不得轉載。