遞歸算法實例應(yīng)用（五） 算24 （POJ 2787）

Description

成都創(chuàng)新互聯(lián)公司是一家業(yè)務(wù)范圍包括IDC托管業(yè)務(wù),雅安服務(wù)器托管、主機租用、主機托管，四川、重慶、廣東電信服務(wù)器租用,四川電信機房托管，成都網(wǎng)通服務(wù)器托管,成都服務(wù)器租用,業(yè)務(wù)范圍遍及中國大陸、港澳臺以及歐美等多個國家及地區(qū)的互聯(lián)網(wǎng)數(shù)據(jù)服務(wù)公司。

給出4個小于10的正整數(shù)，你可以使用加減乘除4種運算以及括號把這4個數(shù)連接起來得到一個表達式?，F(xiàn)在的問題是，是否存在一種方式使得得到的表達式的結(jié)果等于24。

這里加減乘除以及括號的運算結(jié)果和運算的優(yōu)先級跟我們平常的定義一致（這里的除法定義是實數(shù)除法）。

比如，對于5，5，5，1，我們知道5 * (5 – 1 / 5) = 24，因此可以得到24。

又比如，對于1，1，4，2，我們怎么都不能得到24。

Input

輸入數(shù)據(jù)包括多行，每行給出一組測試數(shù)據(jù)，包括4個小于10的正整數(shù)。

最后一組測試數(shù)據(jù)中包括4個0，表示輸入的結(jié)束，這組數(shù)據(jù)不用處理。

Output

對于每一組測試數(shù)據(jù)，輸出一行，如果可以得到24，輸出“YES”；否則，輸出“NO”。

Sample Input

5 5 5 1
1 1 4 2
0 0 0 0

Sample Output

YES
NO

---

算法思想：

同樣拿到題之后呢，首先第一個想法依舊是能否將問題分解為規(guī)模更小的子問題，然后利用遞歸解決。

對于問題解決的第一步而言，普遍想法是，先找兩個數(shù)進行一種加、減、乘、除運算，再將該結(jié)果與剩下的n-2個數(shù)進行運算，那么此時，問題規(guī)模就變?yōu)榱薾-1，因此本題就轉(zhuǎn)變?yōu)橐粋€遞歸問題。

再考慮遞歸的次數(shù)，我們從第一步的初始狀態(tài)開始不斷遞歸判斷是否能滿足題設(shè)要求，當(dāng)以此為初始條件均不能滿足題設(shè)要求時，應(yīng)繼續(xù)判定下一初始條件，所以我們應(yīng)枚舉所有可能的第一步的初始狀態(tài)，即：枚舉所有可能的兩個數(shù)的組合。再以此為初始條件進行遞歸判斷是否為解。

其次考慮遞歸的邊界條件，基于前幾題的求邊界條件思想，本題的邊界情況十分明顯，即當(dāng)問題規(guī)模遞歸減少為1時，僅有一個數(shù)，判斷與24是否相等，若相等則應(yīng)返回true，表明找到一組解，若不相等應(yīng)返回false，表明本次遞歸的初始條件不能滿足題設(shè)要求。

詳細(xì)說明關(guān)于在遞歸時數(shù)據(jù)的處理：

1. 選出兩個數(shù)作為初始條件進行加、減、乘、除運算，選取時應(yīng)取遍所有可能的組合，可通過二重循環(huán)實現(xiàn)。
2. 將這兩個數(shù)（a和b）的運算結(jié)果與余下的n-2個數(shù)存起來，共n-1個數(shù)，存入一個數(shù)組中，作為中間變量，在以該中間變量數(shù)組進行遞歸，依次判斷a+b、a-b、b-a、a*b、a/b、b/a六種情況，在除法運算中，應(yīng)保證除數(shù)不為0；此時的遞歸為將臨時變量b里的n-1個數(shù)來算24,判斷是否可以滿足題設(shè)要求。問題的遞歸主體及關(guān)鍵也在這里。

---

代碼邏輯：

依據(jù)上述算法思想，不難想出應(yīng)設(shè)置一個初始數(shù)組存儲題設(shè)輸入的一組數(shù)據(jù)；因為本題中設(shè)計除法相關(guān)操作，所以數(shù)據(jù)可能為浮點類型，但是由于浮點數(shù)在計算機中存儲采用IEE754標(biāo)準(zhǔn)，存在精度丟失問題，所以對于浮點類型數(shù)據(jù)是否為0的判定不能使用“==”來判定，所以，還應(yīng)定義一個函數(shù)來實現(xiàn)對浮點數(shù)是否為0的一個判斷。

1. 在C語言中，進行浮點數(shù)為0判斷時，一般考慮判斷該數(shù)的絕對值是否小于一個極小值ε，通常ε選10^-6。

   代碼如下：

   #define ESP 1e-6
   
   bool isZero(double num) {return fabs(num)<= ESP;
   }

2. 由上述算法思想中分析，設(shè)遞歸函數(shù)定義為，bool count24(double a[], int n)，即：對有n個元素的a組數(shù)據(jù)進行算24操作。

   • 首先進入遞歸函數(shù)時應(yīng)判斷是否滿足邊界條件，即，當(dāng)問題規(guī)模n=1時，判斷該數(shù)是否等于24。

   • 在遞歸主體中，首先聲明中間變量數(shù)組b，用于存儲剩下的n-1個數(shù)以實現(xiàn)遞歸。

   • 通過枚舉每一種可能的初始條件，以期尋求所有可能的解。

   • 每找到兩個數(shù)后，將其與的n-2個數(shù)存入中間變量數(shù)組b中，再對這兩個數(shù)進行算法思想中第二點所分析的6種情況進行計算。

   • 假設(shè)以a+b為例，其代碼可描述為：

     b[m] = a[i] + a[j];
     if (count24(b, m + 1))
         return true;

   • 假設(shè)以a/b為例，其中b不為0，其代碼可描述為：

     if (!isZero(a[j])) {b[m] = a[i] / a[j];
         if (count24(b, m + 1))
             return true;
     }

3. 本題思想邏輯較前幾題幾乎并無不同，但在代碼實現(xiàn)上有更大的難度，主要是對不同的情況做不同的遞歸處理，同時對于數(shù)據(jù)的處理也應(yīng)考慮遞歸時數(shù)據(jù)作用域的不同對函數(shù)運算結(jié)果過的影響。比如用于存儲題設(shè)輸入元素的數(shù)組a，應(yīng)為全局變量，因為在遞歸處理時，我們以中間變量b來進行運算，但同時也用到了數(shù)組a來為b進行賦值。所以在每一層遞歸中都用到了該變量，與遞歸層級無關(guān)，所以設(shè)置為全局變量能更好的進行代碼的編寫；或者將原始數(shù)組a作為形參傳入遞歸函數(shù)，但是由于遞歸操作本來就對函數(shù)調(diào)用棧有較高的占用率，若再增加沒有必要的形參數(shù)量，無疑是為函數(shù)調(diào)用棧帶來了更大的負(fù)載。

4. 至此，遞歸章節(jié)將告一段落，以上數(shù)題基本涵蓋了遞歸在時間和空間復(fù)雜度要求不高的情況下能僅用遞歸能解決問題的幾種基本問題模型。

---

代碼整合：

//
// Created by Ss1Two on 2023/1/18.
//

#include "stdio.h"
#include "stdbool.h"
#include "math.h"

#define ESP 1e-6 //

//判斷浮點數(shù)num是否為0
bool isZero(double num) {return fabs(num)<= ESP;
}

//存儲題設(shè)輸入的原始數(shù)據(jù)
double a[5];

//把數(shù)組a中的n個元素進行算24判斷
bool count24(double a[], int n) {//遞歸邊界條件判定
    if (n == 1) {if (isZero(a[0] - 24))
            return true;
        else
            return false;
    }

    //遞歸時中間變量數(shù)組
    double b[5];

    //枚舉每一種可能的（先找兩個數(shù)做運算的）初始條件
    for (int i = 0; i< n - 1; i++) {for (int j = i + 1; j< n; j++) {int m = 0;// m作為處理剩下的n-2個數(shù)時的下標(biāo)
            for (int k = 0; k< n; k++) {//將非初始條件之外的n-2個數(shù)據(jù)存入中間變量b數(shù)組中
                if (k != i && k != j)
                    b[m++] = a[k];
            }

            //將初始條件的兩個值做加法運算，并存入中間變量b數(shù)組中
            //其中m+1==n-1
            b[m] = a[i] + a[j];

            //此時問題規(guī)模減一，即將b數(shù)組中的n-1個數(shù)，進行算24判斷。
            //情況1：a + b
            if (count24(b, m + 1))
                return true;

            //情況2：a - b
            b[m] = a[i] - a[j];
            if (count24(b, m + 1))
                return true;

            //情況3：b - a
            b[m] = a[j] - a[i];
            if (count24(b, m + 1))
                return true;


            //情況4：a * b
            b[m] = a[i] * a[j];
            if (count24(b, m + 1))
                return true;


            //情況5：a / b ，其中b!=0
            if (!isZero(a[j])) {b[m] = a[i] / a[j];
                if (count24(b, m + 1))
                    return true;
            }

            //情況6：b / a ，其中a!=0
            if (!isZero(a[i])) {b[m] = a[j] / a[i];
                if (count24(b, m + 1))
                    return true;
            }
        }
    }
    return false;
}

int main() {while (true) {for (int i = 0; i< 4; i++) {scanf("%lf", &a[i]);
        }
        if (isZero(a[0]))break;
        if (count24(a, 4))
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}

C r e a t e d ? b y ? S s 1 T w o ? o n ? 2023 / 01 / 18 Created\cdots by\cdots Ss1Two\cdots on \cdots 2023/01/18 Created?by?Ss1Two?on?2023/01/18

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

網(wǎng)站欄目：遞歸算法實例應(yīng)用（五）-創(chuàng)新互聯(lián)
URL分享：http://jinyejixie.com/article16/giidg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供App設(shè)計、全網(wǎng)營銷推廣、網(wǎng)站策劃、小程序開發(fā)、網(wǎng)站收錄、網(wǎng)站內(nèi)鏈

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)