（二） 遞歸 1664 放蘋果

1664 放蘋果

• ​​AC代碼​​
• ​​解析​​

• ​​其實主要是遞歸式和邊界條件的尋找​​
• ​​找變化的量​​
• ​​分析變量的變化​​

• ​​新知識​​

• ​​持續輸入​​

AC代碼

/**********************************************************************/
/*                     _   _   __  __    ____   _____                   */
/*                    | | | | |  \/  |  / ___| |  ___|                  */
/*                    | | | | | |\/| | | |     | |___                   */
/*                    | |_| | | |  | | | |___  | |___|                  */
/*                     \___/  |_|  |_|  \____| |_|                      */
/**********************************************************************/
#include <iostream>
using namespace std;

int apple(int m, int n)//m蘋果，n盤子 1<=M，N<=10。
{                                    // 1<=M<=10   1<=N<=10
  if(m == 0)
  {
    return 1;
  }
  if(n <= 0)
  {
    return 0;
  }
  if(m < n)
  {
    return apple(m,m);
  }
//  if(m == n)
//  {
//    return 1;
//  }
  if(m >= n)
  {
    return apple(m,n-1)+apple(m-n,n);
  }
  
} 

int main()
{
  int t = 0,m = 0 ,n = 0;
  cin >> t;
  while(t--)
  {
    cin >>m >> n;
    cout << apple(m,n)<< endl;
  }
  return 0;
}      

解析

​​參看中國大學慕課郭炜老師課程講解遞歸二​​​ 當m<n時，一定會空出n-m個盤子，是以

``c

``

m>=n時，有空盤子的情況和将m蘋果放滿n-1盤子裡是一樣的，這裡遞歸一下

沒有空盤子的情況，和先每個盤子放一個蘋果，再往剩下n個盤子裡放m-n蘋果

其實主要是遞歸式和邊界條件的尋找

分為兩步

找變化的量

分析變量的變化

新知識

持續輸入

while(t--)//比for少寫幾行
  {
    cin >>m >> n;
    cout << apple(m,n)<< endl;
  }