C語言實現(xiàn)24點問題詳解
更新時間：2021年12月30日 09:09:24 作者：小輝_Super
24點問題就是在屏幕上輸入1?10范圍內(nèi)的4個整數(shù)（可以有重復(fù)），對它們進行加、減、乘、除四則運算后（可以任意的加括號限定計算的優(yōu)先級），尋找計算結(jié)果等于24的表達式。本文將通過C語言實現(xiàn)24點問題的求解，需要的可以參考一下
題目描述
在屏幕上輸入1?10范圍內(nèi)的4個整數(shù)（可以有重復(fù)），對它們進行加、減、乘、除四則運算后（可以任意的加括號限定計算的優(yōu)先級），尋找計算結(jié)果等于24的表達式。
例如輸入4個整數(shù)4、5、6、7，可得到表達式：4*((5-6)+7)=24。這只是一個解，要求輸出全部的解。要求表達式中數(shù)字的順序不能改變。
問題分析
這道題理解起來很簡單，就是拼湊加減乘除，使4個數(shù)的運算結(jié)果等于24。
由于四則運算中，乘除的優(yōu)先級高于加減，所以必須“加括號”來限定4個數(shù)之間運算優(yōu)先級。
例如：A+B*C-D 這個式子，通過增加括號，可以產(chǎn)生多種結(jié)果，比如 (A+B)*(C-D) 和 A+(B*C-D)。
那么總共有幾種加括號的方法呢，該如何分類呢？
一開始我在想是不是能按照括號對數(shù)進行分類，但后來發(fā)現(xiàn)，要想將4個數(shù)字的運算優(yōu)先級細分，必須使用兩對括號。
可以這么理解：我們的目的是將4個數(shù)的運算轉(zhuǎn)換成兩個“數(shù)”的運算（這里的“數(shù)”包括括號表達式），而每兩個數(shù)運算，就能得出一個結(jié)果，即每對括號可以減少一個要計算的數(shù)字（如(A+B)*(C+D)中，A和B運算，使式子變成了3個數(shù)，C接著和D運算，使式子剩下兩個數(shù)字）。4-2=2即為需要的括號數(shù)。
下面列舉所有可能的括號表達式：（#表示四則運算符）
- ((A#B)#C)#D
- (A#(B#C))#D
- A#((B#C)#D)
- A#(B#(C#D))
- (A#B)#(C#D)
具體思路：
上面5種括號表達式都可以單獨寫成函數(shù)，函數(shù)內(nèi)部按照括號的優(yōu)先級+從左往右的順序進行運算，最后返回計算結(jié)果。
每個表達式中有3個'#'號，它們是四則運算符（+、-、*、/），可以定義一個全局字符數(shù)組，存放4這四個字符。
char my_oprator[4] = {'+', '-', '*', '/'};
主函數(shù)使用窮舉法，對表達式的每個#符號進行遍歷（4種運算符），使用3層 for循環(huán)實現(xiàn)（層數(shù)對應(yīng)3個#符號，每層循環(huán)4次，對應(yīng)4種運算符），最后將符合條件的表達式輸出。
【注意】：由于式子中存在除法，所以不能用整型數(shù)據(jù)進行計算（比如(int)(2/4) = 0），應(yīng)該使用float或double類型。
浮點數(shù)的表示是不精確的，所以運算結(jié)果不能直接和 24 比較。它們可能只是在某個范圍內(nèi)相等，如float變量的精度為小數(shù)點后六位，所以我們只要保證小數(shù)點后 6 位和 24 相等（全為0）即可。
可以使用如下語句進行判斷：
if(ret - 24 <= 0.000001 && ret - 24 >= -0.000001)
ret為運算結(jié)果，這個 if 語句的作用是判斷運算結(jié)果 ret 和 24 之間的差值是否超過±0.000001。
【以上言論僅供參考，未必全對】
代碼實現(xiàn)
#include <stdio.h>
#define TARGET_POINT 24 //目標點數(shù)
//算術(shù)操作符
char my_oprator[4] = {'+', '-', '*', '/'};
/******************************************************************************
* @brief 四則運算
* @param x 浮點變量1
* @param y 浮點變量2
* @param op 運算符
* @return 運算結(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("非法運算符\n");
}
return 0;
}
/******************************************************************************
* @brief Expression_1
* @param a b c d 浮點變量
* @param op1 op2 op3 運算符
* @return ((A#B)#C)#D 運算結(jié)果 #表示運算符
******************************************************************************/
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 浮點變量
* @param op1 op2 op3 運算符
* @return (A#(B#C))#D 運算結(jié)果 #表示運算符
******************************************************************************/
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 浮點變量
* @param op1 op2 op3 運算符
* @return A#((B#C)#D) 運算結(jié)果 #表示運算符
******************************************************************************/
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 浮點變量
* @param op1 op2 op3 運算符
* @return A#(B#(C#D)) 運算結(jié)果 #表示運算符
******************************************************************************/
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 浮點變量
* @param op1 op2 op3 運算符
* @return (A#B)#(C#D) 運算結(jié)果 #表示運算符
******************************************************************************/
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("請輸入4個整數(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++)
{
//表達式1：((A#B)#C)#D
ret = Expression_1(a, b, c, d,\
my_oprator[i],\
my_oprator[j],\
my_oprator[k]);
//判斷結(jié)果是否為目標點數(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; //成功匹配
}
//表達式2：(A#(B#C))#D
ret = Expression_2(a, b, c, d,\
my_oprator[i],\
my_oprator[j],\
my_oprator[k]);
//判斷結(jié)果是否為目標點數(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; //成功匹配
}
//表達式3：A#((B#C)#D)
ret = Expression_3(a, b, c, d,\
my_oprator[i],\
my_oprator[j],\
my_oprator[k]);
//判斷結(jié)果是否為目標點數(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; //成功匹配
}
//表達式4：A#(B#(C#D))
ret = Expression_4(a, b, c, d,\
my_oprator[i],\
my_oprator[j],\
my_oprator[k]);
//判斷結(jié)果是否為目標點數(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; //成功匹配
}
//表達式5：(A#B)#(C#D)
ret = Expression_5(a, b, c, d,\
my_oprator[i],\
my_oprator[j],\
my_oprator[k]);
//判斷結(jié)果是否為目標點數(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("沒有滿足條件的表達式\n");
return 0;
}
運行結(jié)果
由于是根據(jù)括號位置分類的，所以有些式子在某種意義上是相同的，比如1*((2*3)*4) ， 1*(2*(3*4)) 和 (1*2)*(3*4)，但是如果要對這個進行優(yōu)化（去掉無效括號），感覺還挺復(fù)雜的。
到此這篇關(guān)于C語言實現(xiàn)24點問題詳解的文章就介紹到這了,更多相關(guān)C語言24點內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章主要介紹了C++歸并排序算法實例,本文先是介紹了什么是歸并排序,然后給出了實現(xiàn)代碼,需要的朋友可以參考下2014-10-10
這篇文章主要介紹了C語言程序的預(yù)處理,小編覺得這篇文章寫的還不錯,需要的朋友可以參考下，希望能夠給你帶來幫助2021-11-11
C語言中,結(jié)構(gòu)體類型屬于一種構(gòu)造類型(其他的構(gòu)造類型還有：數(shù)組類型,聯(lián)合類型),下面這篇文章主要給大家介紹了關(guān)于C語言結(jié)構(gòu)體(struct)的相關(guān)資料,文中通過示例代碼介紹的非常詳細,需要的朋友可以參考下2022-03-03
C++11 std::shared_ptr總結(jié)與使用示例代碼詳解
這篇文章主要介紹了C++11 std::shared_ptr總結(jié)與使用,本文通過示例代碼給大家介紹的非常詳細，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下2020-06-06
C++ Vector應(yīng)用方式是比較特殊的，我們將會在這篇文章中針對于它的應(yīng)用方式進行一個詳細的介紹，希望大家能充分掌握這一應(yīng)用技巧2014-08-08
C語言中fgetgrent()函數(shù)和fgetpwent()函數(shù)的用法對比
這篇文章主要介紹了C語言中fgetgrent()函數(shù)和fgetpwent()函數(shù)的用法對比,分別用于讀取組格式函數(shù)和讀取密碼格式,需要的朋友可以參考下2015-08-08
背包問題是一個經(jīng)典的動態(tài)規(guī)劃問題,而貪心算法是一種常用的解決背包問題的方法,這篇文章主要給大家介紹了關(guān)于C語言背包問題求解(貪心方法)的相關(guān)資料,文中通過代碼介紹的非常詳細,需要的朋友可以參考下2024-06-06
相信大家知道虛表指針和虛函數(shù)存儲的位置，但對于虛函數(shù)表的存儲位置一時無法確定。本文就來和大家詳細聊聊相關(guān)內(nèi)容，希望對大家有所幫助2023-04-04
當你對C越來越熟悉時,你會發(fā)現(xiàn)把與指針攪和在一起的"類型"這個概念分成"指針的類型"和"指針所指向的類型"兩個概念,是精通指針的關(guān)鍵點之一,這篇文章主要給大家介紹了關(guān)于c/c++中指針的相關(guān)資料,需要的朋友可以參考下2021-10-10
C++深入探索內(nèi)聯(lián)函數(shù)inline與auto關(guān)鍵字的使用
本篇文章主要包括內(nèi)聯(lián)函數(shù)和auto關(guān)鍵字。其中，內(nèi)斂函數(shù)包括概念，特性等；auto關(guān)鍵字的使用規(guī)則，使用場景等，接下來讓我們深入了解2022-05-05