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，分别表示加、减、乘，除四种运算，如下表所示。

这样通过一个三重循环就可以枚举出不考虑括号情况的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<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;
}

运行结果：