C語(yǔ)言實(shí)現(xiàn)24點(diǎn)問題詳解

更新時(shí)間：2021年12月30日 09:09:24 作者：小輝_Super

24點(diǎn)問題就是在屏幕上輸入1?10范圍內(nèi)的4個(gè)整數(shù)（可以有重復(fù)），對(duì)它們進(jìn)行加、減、乘、除四則運(yùn)算后（可以任意的加括號(hào)限定計(jì)算的優(yōu)先級(jí)），尋找計(jì)算結(jié)果等于24的表達(dá)式。本文將通過C語(yǔ)言實(shí)現(xiàn)24點(diǎn)問題的求解，需要的可以參考一下

題目描述

在屏幕上輸入1?10范圍內(nèi)的4個(gè)整數(shù)（可以有重復(fù)），對(duì)它們進(jìn)行加、減、乘、除四則運(yùn)算后（可以任意的加括號(hào)限定計(jì)算的優(yōu)先級(jí)），尋找計(jì)算結(jié)果等于24的表達(dá)式。

例如輸入4個(gè)整數(shù)4、5、6、7，可得到表達(dá)式：4*((5-6)+7)=24。這只是一個(gè)解，要求輸出全部的解。要求表達(dá)式中數(shù)字的順序不能改變。

問題分析

這道題理解起來很簡(jiǎn)單，就是拼湊加減乘除，使4個(gè)數(shù)的運(yùn)算結(jié)果等于24。

由于四則運(yùn)算中，乘除的優(yōu)先級(jí)高于加減，所以必須“加括號(hào)”來限定4個(gè)數(shù)之間運(yùn)算優(yōu)先級(jí)。

例如：A+B*C-D 這個(gè)式子，通過增加括號(hào)，可以產(chǎn)生多種結(jié)果，比如 (A+B)*(C-D) 和 A+(B*C-D)。

那么總共有幾種加括號(hào)的方法呢，該如何分類呢？

一開始我在想是不是能按照括號(hào)對(duì)數(shù)進(jìn)行分類，但后來發(fā)現(xiàn)，要想將4個(gè)數(shù)字的運(yùn)算優(yōu)先級(jí)細(xì)分，必須使用兩對(duì)括號(hào)。

可以這么理解：我們的目的是將4個(gè)數(shù)的運(yùn)算轉(zhuǎn)換成兩個(gè)“數(shù)”的運(yùn)算（這里的“數(shù)”包括括號(hào)表達(dá)式），而每?jī)蓚€(gè)數(shù)運(yùn)算，就能得出一個(gè)結(jié)果，即每對(duì)括號(hào)可以減少一個(gè)要計(jì)算的數(shù)字（如(A+B)*(C+D)中，A和B運(yùn)算，使式子變成了3個(gè)數(shù)，C接著和D運(yùn)算，使式子剩下兩個(gè)數(shù)字）。4-2=2即為需要的括號(hào)數(shù)。

下面列舉所有可能的括號(hào)表達(dá)式：（#表示四則運(yùn)算符）

((A#B)#C)#D
(A#(B#C))#D
A#((B#C)#D)
A#(B#(C#D))
(A#B)#(C#D)

具體思路：

上面5種括號(hào)表達(dá)式都可以單獨(dú)寫成函數(shù)，函數(shù)內(nèi)部按照括號(hào)的優(yōu)先級(jí)+從左往右的順序進(jìn)行運(yùn)算，最后返回計(jì)算結(jié)果。

每個(gè)表達(dá)式中有3個(gè)'#'號(hào)，它們是四則運(yùn)算符（+、-、*、/），可以定義一個(gè)全局字符數(shù)組，存放4這四個(gè)字符。

char my_oprator[4] = {'+', '-', '*', '/'};

主函數(shù)使用窮舉法，對(duì)表達(dá)式的每個(gè)#符號(hào)進(jìn)行遍歷（4種運(yùn)算符），使用3層 for循環(huán)實(shí)現(xiàn)（層數(shù)對(duì)應(yīng)3個(gè)#符號(hào)，每層循環(huán)4次，對(duì)應(yīng)4種運(yùn)算符），最后將符合條件的表達(dá)式輸出。

【注意】：由于式子中存在除法，所以不能用整型數(shù)據(jù)進(jìn)行計(jì)算（比如(int)(2/4) = 0），應(yīng)該使用float或double類型。

浮點(diǎn)數(shù)的表示是不精確的，所以運(yùn)算結(jié)果不能直接和 24 比較。它們可能只是在某個(gè)范圍內(nèi)相等，如float變量的精度為小數(shù)點(diǎn)后六位，所以我們只要保證小數(shù)點(diǎn)后 6 位和 24 相等（全為0）即可。

可以使用如下語(yǔ)句進(jìn)行判斷：

if(ret - 24 <= 0.000001 && ret - 24 >= -0.000001)

ret為運(yùn)算結(jié)果，這個(gè) if 語(yǔ)句的作用是判斷運(yùn)算結(jié)果 ret 和 24 之間的差值是否超過±0.000001。

【以上言論僅供參考，未必全對(duì)】

代碼實(shí)現(xiàn)

#include <stdio.h>

#define TARGET_POINT  24    //目標(biāo)點(diǎn)數(shù)

//算術(shù)操作符
char my_oprator[4] = {'+', '-', '*', '/'};

/******************************************************************************
 * @brief 四則運(yùn)算
 * @param x 浮點(diǎn)變量1
 * @param y 浮點(diǎn)變量2
 * @param op 運(yùn)算符
 * @return 運(yùn)算結(jié)果: x op y
 ******************************************************************************/
float Calculate(float x, float y, char op)
{
    switch(op)
    {
        case '+': return x + y;
        case '-': return x - y;
        case '*': return x * y;
        case '/':return x / y;
        default: printf("非法運(yùn)算符\n");
    }
    return 0;
}

/******************************************************************************
 * @brief Expression_1
 * @param a b c d     浮點(diǎn)變量
 * @param op1 op2 op3 運(yùn)算符
 * @return ((A#B)#C)#D 運(yùn)算結(jié)果  #表示運(yùn)算符
 ******************************************************************************/
float Expression_1(float a, float b, float c, float d, char op1, char op2, char op3)
{
    float ret = 0;
    ret = Calculate(a, b, op1);   //求出 A#B 的結(jié)果
    ret = Calculate(ret, c, op2); //求出 ret#C 的結(jié)果
    ret = Calculate(ret, d, op3); //求出 ret#D 的結(jié)果
    return ret;
}

/******************************************************************************
 * @brief Expression_2
 * @param a b c d     浮點(diǎn)變量
 * @param op1 op2 op3 運(yùn)算符
 * @return (A#(B#C))#D 運(yùn)算結(jié)果  #表示運(yùn)算符
 ******************************************************************************/
float Expression_2(float a, float b, float c, float d, char op1, char op2, char op3)
{
    float ret = 0;
    ret = Calculate(b, c, op2);   //求出 B#C 的結(jié)果
    ret = Calculate(a, ret, op1); //求出 A#ret 的結(jié)果
    ret = Calculate(ret, d, op3); //求出 ret#D 的結(jié)果
    return ret;
}

/******************************************************************************
 * @brief Expression_3
 * @param a b c d     浮點(diǎn)變量
 * @param op1 op2 op3 運(yùn)算符
 * @return A#((B#C)#D) 運(yùn)算結(jié)果  #表示運(yùn)算符
 ******************************************************************************/
float Expression_3(float a, float b, float c, float d, char op1, char op2, char op3)
{
    float ret = 0;
    ret = Calculate(b, c, op2);   //求出 B#C 的結(jié)果
    ret = Calculate(ret, d, op3); //求出 ret#D 的結(jié)果
    ret = Calculate(a, ret, op1); //求出 A#ret 的結(jié)果
    return ret;
}

/******************************************************************************
 * @brief Expression_4
 * @param a b c d     浮點(diǎn)變量
 * @param op1 op2 op3 運(yùn)算符
 * @return A#(B#(C#D)) 運(yùn)算結(jié)果  #表示運(yùn)算符
 ******************************************************************************/
float Expression_4(float a, float b, float c, float d, char op1, char op2, char op3)
{
    float ret = 0;
    ret = Calculate(c, d, op3);   //求出 C#D 的結(jié)果
    ret = Calculate(b, ret, op2); //求出 B#ret 的結(jié)果
    ret = Calculate(a, ret, op1); //求出 A#ret 的結(jié)果
    return ret;
}

/******************************************************************************
 * @brief Expression_5
 * @param a b c d     浮點(diǎn)變量
 * @param op1 op2 op3 運(yùn)算符
 * @return (A#B)#(C#D) 運(yùn)算結(jié)果  #表示運(yùn)算符
 ******************************************************************************/
float Expression_5(float a, float b, float c, float d, char op1, char op2, char op3)
{
    float ret1 = 0, ret2 = 0;
    ret1 = Calculate(a, b, op1);   //求出 A#B 的結(jié)果
    ret2 = Calculate(c, d, op3);   //求出 C#D 的結(jié)果
    ret2 = Calculate(ret1, ret2, op2); //求出 ret1#ret2 的結(jié)果
    return ret2;
}

int main()
{
    float a = 0, b = 0, c = 0, d = 0;
    int i = 0, j = 0, k = 0;
    float ret = 0;
    int flag = 0;  //是否有匹配結(jié)果，1：有結(jié)果

    printf("請(qǐng)輸入4個(gè)整數(shù)，數(shù)字范圍：1~10，可重復(fù)\n");
    scanf("%f%f%f%f", &a, &b, &c, &d);

    for(i = 0; i < 4; i++)
        for(j = 0; j < 4; j++)
            for(k = 0; k < 4; k++)
            {
                //表達(dá)式1：((A#B)#C)#D
                ret = Expression_1(a, b, c, d,\
                                   my_oprator[i],\
                                   my_oprator[j],\
                                   my_oprator[k]);
                //判斷結(jié)果是否為目標(biāo)點(diǎn)數(shù)，精度0.000001
                if(ret - TARGET_POINT <= 0.000001 &&\
                        ret - TARGET_POINT >= -0.000001)
                {
                    printf("((%.0f%c%.0f)%c%.0f)%c%.0f=%.0f\n",\
                           a, my_oprator[i],\
                           b, my_oprator[j],\
                           c, my_oprator[k], d, ret);
                    flag = 1; //成功匹配
                }

                //表達(dá)式2：(A#(B#C))#D
                ret = Expression_2(a, b, c, d,\
                                   my_oprator[i],\
                                   my_oprator[j],\
                                   my_oprator[k]);
                //判斷結(jié)果是否為目標(biāo)點(diǎn)數(shù)，精度0.000001
                if(ret - TARGET_POINT <= 0.000001 &&\
                        ret - TARGET_POINT >= -0.000001)
                {
                    printf("(%.0f%c(%.0f%c%.0f))%c%.0f=%.0f\n",\
                           a, my_oprator[i],\
                           b, my_oprator[j],\
                           c, my_oprator[k], d, ret);
                    flag = 1; //成功匹配
                }

                //表達(dá)式3：A#((B#C)#D)
                ret = Expression_3(a, b, c, d,\
                                   my_oprator[i],\
                                   my_oprator[j],\
                                   my_oprator[k]);
                //判斷結(jié)果是否為目標(biāo)點(diǎn)數(shù)，精度0.000001
                if(ret - TARGET_POINT <= 0.000001 &&\
                        ret - TARGET_POINT >= -0.000001)
                {
                    printf("%.0f%c((%.0f%c%.0f)%c%.0f)=%.0f\n",\
                           a, my_oprator[i],\
                           b, my_oprator[j],\
                           c, my_oprator[k], d, ret);
                    flag = 1; //成功匹配
                }

                //表達(dá)式4：A#(B#(C#D))
                ret = Expression_4(a, b, c, d,\
                                   my_oprator[i],\
                                   my_oprator[j],\
                                   my_oprator[k]);
                //判斷結(jié)果是否為目標(biāo)點(diǎn)數(shù)，精度0.000001
                if(ret - TARGET_POINT <= 0.000001 &&\
                        ret - TARGET_POINT >= -0.000001)
                {
                    printf("%.0f%c(%.0f%c(%.0f%c%.0f))=%.0f\n",\
                           a, my_oprator[i],\
                           b, my_oprator[j],\
                           c, my_oprator[k], d, ret);
                    flag = 1; //成功匹配
                }

                //表達(dá)式5：(A#B)#(C#D)
                ret = Expression_5(a, b, c, d,\
                                   my_oprator[i],\
                                   my_oprator[j],\
                                   my_oprator[k]);
                //判斷結(jié)果是否為目標(biāo)點(diǎn)數(shù)，精度0.000001
                if(ret - TARGET_POINT <= 0.000001 &&\
                        ret - TARGET_POINT >= -0.000001)
                {
                    printf("(%.0f%c%.0f)%c(%.0f%c%.0f)=%.0f\n",\
                           a, my_oprator[i],\
                           b, my_oprator[j],\
                           c, my_oprator[k], d, ret);
                    flag = 1; //成功匹配
                }
            }
    if(flag == 0)
        printf("沒有滿足條件的表達(dá)式\n");
    return 0;
}