C語言實現(xiàn)24點問題詳解

第C語言實現(xiàn)24點問題詳解目錄題目描述問題分析代碼實現(xiàn)運行結(jié)果

題目描述

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

例如輸入4個整數(shù)4、5、6、7，可得到表達(dá)式：4*((5-6)+7)=24。這只是一個解，要求輸出全部的解。要求表達(dá)式中數(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ù)進(jìn)行分類，但后來發(fā)現(xiàn)，要想將4個數(shù)字的運算優(yōu)先級細(xì)分，必須使用兩對括號。

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

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

((A#B)#C)#D

(A#(B#C))#D

A#((B#C)#D)

A#(B#(C#D))

(A#B)#(C#D)

具體思路：

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

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

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

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

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

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

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

if(ret-24=0.000001ret-24=-0.000001)

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

【以上言論僅供參考，未必全對】

代碼實現(xiàn)

#includestdio.h

#defineTARGET_POINT24//目標(biāo)點數(shù)

//算術(shù)操作符

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

/******************************************************************************

*@brief四則運算

*@paramx浮點變量1

*@paramy浮點變量2

*@paramop運算符

*@return運算結(jié)果:xopy

******************************************************************************/

floatCalculate(floatx,floaty,charop)

switch(op)

case'+':returnx+y;

case'-':returnx-y;

case'*':returnx*y;

case'/':returnx/y;

default:printf("非法運算符\n");

return0;

/******************************************************************************

*@briefExpression_1

*@paramabcd浮點變量

*@paramop1op2op3運算符

*@return((A#B)#C)#D運算結(jié)果#表示運算符

******************************************************************************/

floatExpression_1(floata,floatb,floatc,floatd,charop1,charop2,charop3)

floatret=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é)果

returnret;

/******************************************************************************

*@briefExpression_2

*@paramabcd浮點變量

*@paramop1op2op3運算符

*@return(A#(B#C))#D運算結(jié)果#表示運算符

******************************************************************************/

floatExpression_2(floata,floatb,floatc,floatd,charop1,charop2,charop3)

floatret=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é)果

returnret;

/******************************************************************************

*@briefExpression_3

*@paramabcd浮點變量

*@paramop1op2op3運算符

*@returnA#((B#C)#D)運算結(jié)果#表示運算符

******************************************************************************/

floatExpression_3(floata,floatb,floatc,floatd,charop1,charop2,charop3)

floatret=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é)果

returnret;

/******************************************************************************

*@briefExpression_4

*@paramabcd浮點變量

*@paramop1op2op3運算符

*@returnA#(B#(C#D))運算結(jié)果#表示運算符

******************************************************************************/

floatExpression_4(floata,floatb,floatc,floatd,charop1,charop2,charop3)

floatret=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é)果

returnret;

/******************************************************************************

*@briefExpression_5

*@paramabcd浮點變量

*@paramop1op2op3運算符

*@return(A#B)#(C#D)運算結(jié)果#表示運算符

******************************************************************************/

floatExpression_5(floata,floatb,floatc,floatd,charop1,charop2,charop3)

floatret1=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é)果

returnret2;

intmain()

floata=0,b=0,c=0,d=0;

inti=0,j=0,k=0;

floatret=0;

intflag=0;//是否有匹配結(jié)果，1：有結(jié)果

printf("請輸入4個整數(shù)，數(shù)字范圍：1~10，可重復(fù)\n");

scanf("%f%f%f%f",a,b,c,

for(i=0;ii++)

for(j=0;jj++)

for(k=0;kk++)

//表達(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)點數(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)點數(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)點數(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)點數(shù)，精度0.000001

if(ret-TARGET_POINT=0.000001\

ret-TARGET_POINT=-0.000001)