C語言實現(xiàn)24點問題詳解
更新時間：2021年12月30日 09:09:24 作者：小輝_Super
24點問題就是在屏幕上輸入1?10范圍內(nèi)的4個整數(shù)（可以有重復），對它們進行加、減、乘、除四則運算后（可以任意的加括號限定計算的優(yōu)先級），尋找計算結果等于24的表達式。本文將通過C語言實現(xiàn)24點問題的求解，需要的可以參考一下
題目描述
在屏幕上輸入1?10范圍內(nèi)的4個整數(shù)（可以有重復），對它們進行加、減、乘、除四則運算后（可以任意的加括號限定計算的優(yōu)先級），尋找計算結果等于24的表達式。
例如輸入4個整數(shù)4、5、6、7，可得到表達式：4*((5-6)+7)=24。這只是一個解，要求輸出全部的解。要求表達式中數(shù)字的順序不能改變。
問題分析
這道題理解起來很簡單，就是拼湊加減乘除，使4個數(shù)的運算結果等于24。
由于四則運算中，乘除的優(yōu)先級高于加減，所以必須“加括號”來限定4個數(shù)之間運算優(yōu)先級。
例如：A+B*C-D 這個式子，通過增加括號，可以產(chǎn)生多種結果，比如 (A+B)*(C-D) 和 A+(B*C-D)。
那么總共有幾種加括號的方法呢，該如何分類呢？
一開始我在想是不是能按照括號對數(shù)進行分類，但后來發(fā)現(xiàn)，要想將4個數(shù)字的運算優(yōu)先級細分，必須使用兩對括號。
可以這么理解：我們的目的是將4個數(shù)的運算轉換成兩個“數(shù)”的運算（這里的“數(shù)”包括括號表達式），而每兩個數(shù)運算，就能得出一個結果，即每對括號可以減少一個要計算的數(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)先級+從左往右的順序進行運算，最后返回計算結果。
每個表達式中有3個'#'號，它們是四則運算符（+、-、*、/），可以定義一個全局字符數(shù)組，存放4這四個字符。
char my_oprator[4] = {'+', '-', '*', '/'};
主函數(shù)使用窮舉法，對表達式的每個#符號進行遍歷（4種運算符），使用3層 for循環(huán)實現(xiàn)（層數(shù)對應3個#符號，每層循環(huán)4次，對應4種運算符），最后將符合條件的表達式輸出。
【注意】：由于式子中存在除法，所以不能用整型數(shù)據(jù)進行計算（比如(int)(2/4) = 0），應該使用float或double類型。
浮點數(shù)的表示是不精確的，所以運算結果不能直接和 24 比較。它們可能只是在某個范圍內(nèi)相等，如float變量的精度為小數(shù)點后六位，所以我們只要保證小數(shù)點后 6 位和 24 相等（全為0）即可。
可以使用如下語句進行判斷：
if(ret - 24 <= 0.000001 && ret - 24 >= -0.000001)
ret為運算結果，這個 if 語句的作用是判斷運算結果 ret 和 24 之間的差值是否超過±0.000001。
【以上言論僅供參考，未必全對】
代碼實現(xiàn)
#include <stdio.h>
#define TARGET_POINT 24 //目標點數(shù)
//算術操作符
char my_oprator[4] = {'+', '-', '*', '/'};
/******************************************************************************
* @brief 四則運算
* @param x 浮點變量1
* @param y 浮點變量2
* @param op 運算符
* @return 運算結果: 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 運算結果 #表示運算符
******************************************************************************/
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 的結果
ret = Calculate(ret, c, op2); //求出 ret#C 的結果
ret = Calculate(ret, d, op3); //求出 ret#D 的結果
return ret;
}
/******************************************************************************
* @brief Expression_2
* @param a b c d 浮點變量
* @param op1 op2 op3 運算符
* @return (A#(B#C))#D 運算結果 #表示運算符
******************************************************************************/
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 的結果
ret = Calculate(a, ret, op1); //求出 A#ret 的結果
ret = Calculate(ret, d, op3); //求出 ret#D 的結果
return ret;
}
/******************************************************************************
* @brief Expression_3
* @param a b c d 浮點變量
* @param op1 op2 op3 運算符
* @return A#((B#C)#D) 運算結果 #表示運算符
******************************************************************************/
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 的結果
ret = Calculate(ret, d, op3); //求出 ret#D 的結果
ret = Calculate(a, ret, op1); //求出 A#ret 的結果
return ret;
}
/******************************************************************************
* @brief Expression_4
* @param a b c d 浮點變量
* @param op1 op2 op3 運算符
* @return A#(B#(C#D)) 運算結果 #表示運算符
******************************************************************************/
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 的結果
ret = Calculate(b, ret, op2); //求出 B#ret 的結果
ret = Calculate(a, ret, op1); //求出 A#ret 的結果
return ret;
}
/******************************************************************************
* @brief Expression_5
* @param a b c d 浮點變量
* @param op1 op2 op3 運算符
* @return (A#B)#(C#D) 運算結果 #表示運算符
******************************************************************************/
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 的結果
ret2 = Calculate(c, d, op3); //求出 C#D 的結果
ret2 = Calculate(ret1, ret2, op2); //求出 ret1#ret2 的結果
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; //是否有匹配結果，1：有結果
printf("請輸入4個整數(shù)，數(shù)字范圍：1~10，可重復\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]);
//判斷結果是否為目標點數(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]);
//判斷結果是否為目標點數(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]);
//判斷結果是否為目標點數(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]);
//判斷結果是否為目標點數(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]);
//判斷結果是否為目標點數(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;
}
運行結果
由于是根據(jù)括號位置分類的，所以有些式子在某種意義上是相同的，比如1*((2*3)*4) ， 1*(2*(3*4)) 和 (1*2)*(3*4)，但是如果要對這個進行優(yōu)化（去掉無效括號），感覺還挺復雜的。
到此這篇關于C語言實現(xiàn)24點問題詳解的文章就介紹到這了,更多相關C語言24點內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
這篇文章主要介紹了C++ 設置透明背景圖片的相關資料,需要的朋友可以參考下2015-06-06
本文給大家分享的是一個經(jīng)典的算法（百元百雞）的C語言版的解決方法，使用的是比較偷懶的窮舉法，有需要的小伙伴可以參考下。2016-02-02
C++線性表深度解析之動態(tài)數(shù)組與單鏈表和棧及隊列的實現(xiàn)
這篇文章主要為大家詳細介紹了C++實現(xiàn)動態(tài)數(shù)組、單鏈表、棧、隊列，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-05-05
本文主要介紹了C語言命令行參數(shù)的使用詳解，文中通過示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-07-07
這篇文中主要為大家詳細介紹了如何利用C語言實現(xiàn)經(jīng)典的掃雷小游戲。掃雷小游戲主要是利用字符數(shù)組、循環(huán)語句和函數(shù)實現(xiàn)，感興趣的小伙伴可以了解一下2022-10-10
這篇文章主要為大家介紹了C++ LeetCode300最長遞增子序列示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2022-12-12
這篇文章主要為大家詳細介紹了C語言實現(xiàn)簡易掃雷程序，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-07-07
在Ubuntu中安裝VSCode并配置C/C++開發(fā)環(huán)境的方法步驟
這篇文章主要介紹了在Ubuntu中安裝VSCode并配置C/C++開發(fā)環(huán)境的方法步驟，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2020-05-05
cin是C++編程語言中的標準輸入流對象，即stream類的對象。cin主要用于從標準輸入讀取數(shù)據(jù)，這里的標準輸入，指的是終端的鍵盤。接下來通過本文給大家分享C++ cin輸入的幾種方式，一起看看吧2021-09-09
這篇文章主要為大家詳細介紹了C語言版猜數(shù)字小游戲，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-07-07