C语言24点问题
问题描述
在屏幕上输入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 | / |
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<stdio.h>
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
