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

Description

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

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

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

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

又比如，對(duì)于1，1，4，2，我們?cè)趺炊疾荒艿玫?4。

Input

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

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

Output

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

Sample Input

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

Sample Output

YES
NO

---

算法思想：

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

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

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

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

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

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

---

代碼邏輯：

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

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

   代碼如下：

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

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

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

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

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

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

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

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

---

代碼整合：

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

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

#define ESP 1e-6 //

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

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

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

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

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

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

            //此時(shí)問(wèn)題規(guī)模減一，即將b數(shù)組中的n-1個(gè)數(shù)，進(jìn)行算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海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

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

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

廣告

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