C语言实现经典24点算法

什么是24点算法

24点算法是一种数学游戏，通过将四个数字进行加、减、乘、除的运算，得出结果为24的算法。例如，给出4个数字6、6、2、1，可以通过计算得到 $6/(1-2/6)=24$，满足24点算法的要求。

实现步骤

1. 读入四个数字 a、b、c、d，存入数组 num[] 中。
2. 枚举 num[] 中的每一个数字，将其作为算式的第一个数字，计算剩下的三个数的24点算式。
3. 在剩下的三个数中，按照加减乘除的四种运算分别枚举两个数，计算得到结果，并将结果作为新的一项加入到剩下未处理的两个数中。
4. 当剩下未处理的数字只剩下一个时，判断其是否等于24，如果是则输出整个算式，程序结束。

代码实现

以下是C语言实现24点算法的代码示例：

#include <stdio.h>

double num[4];

int dfs(int step) {
    if (step == 1) {
        if (fabs(num[0] - 24) < 1e-6 ) {
            printf("%.0lf", num[0]);
            return 1;
        }
        return 0;
    }
    for (int i = 0; i < step; i++) {
        for (int j = i + 1; j < step; j++) {
            double a = num[i], b = num[j];
            num[j] = num[step - 1];
            num[i] = a + b;
            if (dfs(step - 1)) {
               printf(" + ");
               printf("%.0lf", b);
               return 1;
            }
            num[i] = a - b;
            if (dfs(step - 1)) {
               printf(" - ");
               printf("%.0lf", b);
               return 1;
            }
            num[i] = b - a;
            if (dfs(step - 1)) {
               printf(" - ");
               printf("%.0lf", a);
               return 1;
            }
            num[i] = a * b;
            if (dfs(step - 1)) {
               printf(" * ");
               printf("%.0lf", b);
               return 1;
            }
            if (fabs(b) > 1e-6) {
                num[i] = a / b;
                if (dfs(step - 1)) {
                    printf(" / ");
                    printf("%.0lf", b);
                    return 1;
                }
            }
            if (fabs(a) > 1e-6) {
                num[i] = b / a;
                if (dfs(step -1)) {
                    printf(" / ");
                    printf("%.0lf", a);
                    return 1;
                }
            }
            num[i] = a;
            num[j] = b;
        }
    }
    return 0;
}

int main() {
    for (int i = 0; i < 4; i++) scanf("%lf", &num[i]);
    if (!dfs(4)) printf("no sulution.\n");
    return 0;
}

以上代码实现了一个递归的深度遍历算法，至多用时4! * 6 ^ 3次，时间复杂度为O($n^6$)。

示例说明

下面给出两组输入和输出例子，以说明程序的使用方法和输出结果：

示例1

输入：6 6 3 4

输出：$(6 + 6) * (4 - 3) = 24$

程序先将4个数读入并存入num[]数组中，然后先将两个6相加得到12，剩下{12, 3, 4}，接着将12和4做乘法得到48，剩下{48, 3}，最后将48加上3得到51，与24不相等，程序输出“no solution”。

示例2

输入：2 5 6 8

输出：$((6/2)5)8 = 240$

程序同样先将4个数读入并存入num[]数组中，然后先将6和2做除法得到3，再将3和5做乘法得到15，剩下{15，8}。接着将15和8做乘法得到120，剩下{120}，最后120和8做乘法得到240，与24相等，程序输出“((6/2)5)8 = 240”。