（二） 遞歸 + （三）枚舉 2787 算24

2787 算24

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

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

• ​​坑​​

• ​​abs（）和fabs（）​​
• ​​bool函數的判斷傳回一定要确定​​

• ​​新知識​​

• ​​true false​​
• ​​浮點數的比較​​
• ​​快速的判斷方法​​

AC代碼

/**********************************************************************/
/*                     _   _   __  __    ____   _____                   */
/*                    | | | | |  \/  |  / ___| |  ___|                  */
/*                    | | | | | |\/| | | |     | |___                   */
/*                    | |_| | | |  | | | |___  | |___|                  */
/*                     \___/  |_|  |_|  \____| |_|                      */
/**********************************************************************/
#include <iostream>
#include <cmath>

using namespace std;
double number[4] = {0};
#define

bool isZero(double i)
{
  return  fabs(i) < EPS;
}

bool count(double number[] , int n)
{
  if(n == 1)
  {
    if(isZero(number[0] - 24))
    {
      return true;
    }
    else
    {
      return false;
    }
  }
  for(int i =0;i < n-1;i++)
  {
    for(int j = i+1;j <n;j++ )
    {
      double exnum[4] = {0};
      int m = 0;
      for(int k = 0;k<n;k++)
      {
        if(k != i && k!= j)
        {
          exnum[m++] = number[k]; 
        }
      }
      exnum [m] = number[i] + number[j];
      if(count(exnum,m+1))
      {
        return true;
      }
      exnum [m] = number[i] - number[j];
      if(count(exnum,m+1))
      {
        return true;
      }
      exnum [m] = number[j] - number[i];
      if(count(exnum,m+1))
      {
        return true;
      }
      exnum [m] = number[i] * number[j];
      if(count(exnum,m+1))
      {
        return true;
      }
      if(number[i] != 0)
      {
        exnum [m] = number[j] / number[i];
        if(count(exnum,m+1))
        {
          return true;
        }
      }
      if(number[j] != 0)
      {
        exnum [m] = number[i] / number[j];
        if(count(exnum,m+1))
        {
          return true;
        }
      }
        
    }
  }
  return false;
  
}

int main()
{
  
  while(true)
  {
    for(int i =0;i<4;i++)
    {
      cin >> number[i];
    }
        if(isZero(number[0]) == true && isZero(number[1]) == true && isZero(number[2]) == true && isZero(number[3]) == true )
        {
          break;
    } 
    if(count(number, 4))
    {
      cout << "YES" << endl; 
    }
    else
    {
      cout << "NO" << endl;
    }
    
  }
  
  return 0;
}      

解析

​​參看中國大學慕課郭炜老師課程講解遞歸二​​​ 函數調用自己，遞歸

多重for循環周遊

當m<n時，一定會空出n-m個盤子，是以

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

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

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

分為兩步

找變化的量

分析變量的變化

邊界條件為什麼是

if(m == 0)
  {
    return 1;
  }
  if(n <= 0)
  {
    return 0;
  }      

因為

return apple(m,n-1)+apple(m-n,n);      

中，n不斷變化，每次減一 m不斷變化，每次m-n

m-n隻可能>=0,因為每次一進入，進行了篩選，是以考慮 m==0

n最終也會減到0

坑

abs（）和fabs（）

浮點數使用fabs（），在cmath.h

整型使用abs（），stdio.h

bool函數的判斷傳回一定要确定

if(isZero(number[0] - 24))
    {
      return true;
    }
    else//第一次寫忘記了傳回false   不過在整個count函數後面有false指令
    {
      return false;
    }      

新知識

true false

用true和false而不是1和0

當我們把一個非布爾類型的算術值賦給布爾類型時，初始值為0則結果為false，否則結果為true(不為0即真)。

當我們把一個布爾值賦給非布爾類型時，初始值為false則結果為0，初始值為true則結果為1。

浮點數的比較

浮點數比較是否相等，不能用 ==

利用和某一個數內插補點是否小于 1e-6來判斷是否為該數

#define

bool isZero(double i)
{
//  if( fabs(i) < EPS)
//  {
//    return 1;//true
//  }
//  else
//  {
//    return 0;//false
//  }
  return  fabs(i) < EPS;
}      

快速的判斷方法

return  fabs(i) < EPS;
if(number[i] != 0)      

if(！number[i])