C語言實(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á)式），而每兩個(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）即可。
可以使用如下語句進(jìn)行判斷：
if(ret - 24 <= 0.000001 && ret - 24 >= -0.000001)
ret為運(yùn)算結(jié)果，這個(gè) if 語句的作用是判斷運(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;
}
運(yùn)行結(jié)果
由于是根據(jù)括號(hào)位置分類的，所以有些式子在某種意義上是相同的，比如1*((2*3)*4) ， 1*(2*(3*4)) 和 (1*2)*(3*4)，但是如果要對(duì)這個(gè)進(jìn)行優(yōu)化（去掉無效括號(hào)），感覺還挺復(fù)雜的。
到此這篇關(guān)于C語言實(shí)現(xiàn)24點(diǎn)問題詳解的文章就介紹到這了,更多相關(guān)C語言24點(diǎn)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章主要介紹了C++ 設(shè)置透明背景圖片的相關(guān)資料,需要的朋友可以參考下2015-06-06
本文給大家分享的是一個(gè)經(jīng)典的算法（百元百雞）的C語言版的解決方法，使用的是比較偷懶的窮舉法，有需要的小伙伴可以參考下。2016-02-02
C++線性表深度解析之動(dòng)態(tài)數(shù)組與單鏈表和棧及隊(duì)列的實(shí)現(xiàn)
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)動(dòng)態(tài)數(shù)組、單鏈表、棧、隊(duì)列，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-05-05
本文主要介紹了C語言命令行參數(shù)的使用詳解，文中通過示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-07-07
這篇文中主要為大家詳細(xì)介紹了如何利用C語言實(shí)現(xiàn)經(jīng)典的掃雷小游戲。掃雷小游戲主要是利用字符數(shù)組、循環(huán)語句和函數(shù)實(shí)現(xiàn)，感興趣的小伙伴可以了解一下2022-10-10
這篇文章主要為大家介紹了C++ LeetCode300最長遞增子序列示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2022-12-12
這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)簡(jiǎn)易掃雷程序，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-07-07
在Ubuntu中安裝VSCode并配置C/C++開發(fā)環(huán)境的方法步驟
這篇文章主要介紹了在Ubuntu中安裝VSCode并配置C/C++開發(fā)環(huán)境的方法步驟，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-05-05
cin是C++編程語言中的標(biāo)準(zhǔn)輸入流對(duì)象，即stream類的對(duì)象。cin主要用于從標(biāo)準(zhǔn)輸入讀取數(shù)據(jù)，這里的標(biāo)準(zhǔn)輸入，指的是終端的鍵盤。接下來通過本文給大家分享C++ cin輸入的幾種方式，一起看看吧2021-09-09
這篇文章主要為大家詳細(xì)介紹了C語言版猜數(shù)字小游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-07-07