問題描述

在屏幕上輸入1?10范圍內的4個整數(可以有重復)，對它們進行加、減、乘、除四則運算后(可以任意的加括號限定計算的優先級)，尋找計算結果等于24的表達式。

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

問題分析

本題最簡便的解法是應用窮舉法搜索整個解空間，篩選出符合題目要求的全部解。因此，關鍵的問題是如何確定該題的解空間。

假設輸入的4個整數為A、B、C、D，如果不考慮括號優先級的情況，僅用四則運算符將它們連接起來，即A+B*C/D…，則可以形成43=64種可能的表達式。如果考慮加括號的情況，而暫不考慮運算符，則共有以下5種可能的情況：

① ((A□B)□C)□D；

② (A□(B□C))□D；

③ A□(B□(C□D))；

④ A□((B□C)□D)；

⑤ (A□B)□(C□D)。

其中□代表“+、-、*、/”四種運算符中的任意一種。將上面兩種情況綜合起來考慮，每輸入4個整數，其構成的解空間為64*5=320種表達式。也就是說，每輸入4個整數，無論以什么方式或優先級進行四則運算，其結果都會在這320種答案之中。在這320種表達式中尋找出計算結果為24的表達式。

算法設計

首先將3個不同位置上的運算符設置成不同的變量：op1、op2、op3，并規定op1為整數A與B之間的運算符；op2為整數B與C之間的運算符；op3為整數C與D之間的運算符。

A op1 B op2 C op3 D

又規定變量op1、op2、op3取值范圍為1、2、3、4，分別表示加、減、乘，除四種運算，如下表所示。

op1? op2? op3變量值

表示的運算

1

+

2

-

3

*

4

/

這樣通過一個三重循環就可以枚舉出不考慮括號情況的64種表達式類型。算法如下:

for(op1=1;op1<=4;op1++)

for(op2=1;op2<=4;op2++)

for(op3=1;op3<=4;op3++)

{

//得到一種不含括號的表達式情形：A op1 B op2 C op3 D

}

下面的問題就是考慮如何在表達式中添加括號，以及如何通過每種表達式的狀態計算出對應的表達式的值。

首先，上述算法得到的每一種表達式都可能具有5種添加括號的方式，而這5種添加括號的方式實際上涵蓋了該表達式的所有可能優先級的運算。例如：表達式A+B-C*D的5種添加括號的方式為：

① ((A+B)-C)*D；

② (A+(B-C))*D；

③ A+(B-(C*D))；

④ A+((B-C)*D)；

⑤ (A+B)-(C*D)。

實際上，對表達式A+B-C*D以任何優先級方式運算，都包含在這5種表達式之中。

下面是完整的代碼：

#include

char op[5]={'#', '+', '-', '*', '/',};

float cal(float x, float y, int op)

{

switch(op)

{

case 1: return x+y;

case 2: return x-y;

case 3: return x*y;

case 4: return x/y;

default: return 0.0;

}

}

float calculate_model1(float i, float j, float k, float t, int op1, int op2, int op3)

{

float r1, r2, r3;

r1 = cal(i, j, op1);

r2 = cal(r1, k, op2);

r3 = cal(r2, t, op3);

return r3;

}

float calculate_model2(float i, float j, float k, float t, int op1, int op2, int op3)

{

float r1, r2, r3;

r1 = cal(j, k, op2);

r2 = cal(i, r1, op1);

r3 = cal(r2, t, op3);

return r3;

}

float calculate_model3(float i, float j, float k, float t, int op1, int op2, int op3)

{

float r1, r2, r3 ;

r1 = cal(k, t, op3);

r2 = cal(j, r1, op2);

r3 = cal(i, r2, op1);

return r3;

}

float calculate_model4(float i, float j, float k, float t, int op1, int op2, int op3)

{

float r1, r2, r3;

r1 = cal(j, k, op2);

r2 = cal(r1, t, op3);

r3 = cal(i, r2, op1);

return r3;

}

float calculate_model5(float i,float j,float k,float t,int op1,int op2,int op3)

{

float r1, r2, r3 ;

r1 = cal(i, j, op1);

r2 = cal(k, t, op3);

r3 = cal(r1, r2, op2);

return r3;

}

int get24(int i, int j, int k, int t)

{

int op1, op2, op3;

int flag=0;

for(op1=1; op1<=4; op1++)

for(op2=1; op2<=4; op2++)

for(op3=1; op3<=4; op3++)

{

if(calculate_model1(i, j, k, t, op1, op2, op3)==24)

{

printf("((%d%c%d)%c%d)%c%d=24\n", i, op[op1], j, op[op2], k, op[op3], t);

flag = 1;

}

if(calculate_model2(i, j, k, t, op1, op2, op3)==24)

{

printf("(%d%c(%d%c%d))%c%d=24\n", i, op[op1], j, op[op2], k, op[op3], t);

flag = 1;

}

if(calculate_model3(i, j, k, t, op1, op2, op3)==24)

{

printf("%d%c(%d%c(%d%c%d))=24\n", i, op[op1], j, op[op2], k, op[op3], t);

flag = 1;

}

if(calculate_model4(i, j, k, t, op1, op2, op3)==24)

{

printf("%d%c((%d%c%d)%c%d)=24\n", i, op[op1], j, op[op2], k, op[op3], t);

flag = 1;

}

if(calculate_model5(i, j, k, t, op1, op2, op3)==24)

{

printf("(%d%c%d)%c(%d%c%d)=24\n", i, op[op1], j, op[op2], k, op[op3], t);

flag = 1;

}

}

return flag;

}

int main()

{

int i, j, k, t;

printf("Please input four integer (1~10)\n");

loop: scanf("%d %d %d %d", &i, &j, &k, &t);

if(i<1||i>10 || j<1||j>10 || k<1||k>10 || t<1||t>10)

{

printf("Input illege, Please input again\n");

goto loop;

}

if( get24(i, j, k, t) );

else

printf("Sorry, the four integer cannot be calculated to get 24\n");

return 0;

}

運行結果：

Please input four integer (1~10)

1 2 3 4↙?

((1+2)+3)*4=24

(1+(2+3))*4=24

((1*2)*3)*4=24

(1*(2*3))*4=24

1*(2*(3*4))=24

1*((2*3)*4)=24

(1*2)*(3*4)=24

總結

以上是生活随笔為你收集整理的c语言24点程序,C语言24点问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。