題目:http://poj.org/problem?id=1664

 

很經典的recursive題目,學長在上課時教的範例

基本上要分成兩種情況

首先假設全部的盤子都有擺蘋果

考慮完後將盤子數-1,原因是要將其視為"其中一個盤子沒擺東西"

然後依此類推求出解

  1. /******************************************
    Problem: 1664           User: bruce30262
    Memory: 728K            Time: 0MS
    Language: G++           Result: Accepted
    *******************************************/
  2. #include <iostream>
  3.  
  4. using namespace std;
  5.  
  6. int foo(int apple, int plate)
  7. {
  8.     if(apple<0) return 0; //蘋果數小於0時return 0 (0種放法)
  9.     if(apple == 0 || plate == 1) return 1; //蘋果數=0或盤子數=1時return 1 (一種放法)
  10.     return foo(apple - plate, plate) + foo(apple, plate - 1);//第一個是每個盤子至少放一個,第二個是多一個盤子是空的的情況
  11. }
  12.  
  13. int main()
  14. {
  15.     int cases, apples, plates;
  16.  
  17.     while(cin>>cases)
  18.     {
  19.         while(cases--)
  20.         {
  21.             cin>>apples>>plates;
  22.             cout<<foo(apples, plates)<<endl;
  23.         }
  24.     }
  25.     return 0;
  26. }

 

這題很重要,要多想想為啥要這樣做

 

是說心血來潮想說用C++寫一下

結果上傳時忘記設定說要用C++寫

吞了個CE = =

arrow
arrow
    文章標籤
    ACM POJ 程式 recursive
    全站熱搜

    Tube 發表在 痞客邦 留言(0) 人氣()