标题：24点
出处：Felix021
时间：Wed, 20 May 2009 02:08:09 +0000
作者：felix021
地址：https://www.felix021.com/blog/read.php?1602

内容：
本文包含一个很挫的算法和一个很赞的算法
-----------------------
24点是一个足够古老的游戏了：
给出四个一位数（可能重复），使用加减乘除和括号将这四个数字整合成一个算式，使得算式的结果等于24。
当然，不是所有的四个一位数都可以组合成24的，比如1,1,1,1显然就不能。
有两个经典的组合是 1, 5, 5, 5 和 3, 3, 8, 8 —— 你可以找出有效解吗？

对于任意给出的四个一位数，如果不考虑重复的情况（比如1，5，5，5，把三个5当成不同的数字）
那么可以算出，可能的算式有 (4*3*2*1) * (1*2+1*1+2*1) * (4 * 4 * 4)  = 7680种。
这么大的数字用人脑去算是很不合理的，所以应该写一个程序来处理，嗯。
（中间的 1 * 2 + 1 * 1 + 2 * 1是什么？——下面再说）

这个程序的实现我大一的时候曾经想过，但是那时候对语言掌握都很差，更别说写出具体的回溯等算法来实现。
昨天又想到这个问题，于是拖了这么久，终于在今天把代码写出来了（一题两年出，一跑就郁闷）。

昨天想到了一个思路。

一个算式可以看成一棵树，这棵树的特点是：分支节点包含一个操作符，执行相应运算操作，它必然包含左子树和右子树；叶子节点是操作数，它没有子树。这个算式的运算从根节点开始，递归地计算左、右子树的值，然后将二者的结果根据根节点的操作符求出进行运算，得出的结果就是算式的值。

从这点出发，我们可以把四个整数进行处理，把它们放到这样的一棵树中（这样的树有5种，为什么？——下述），只要修改分支节点的操作符，然后运算得出结果看是否等于24即可。

于是得出一个算法：把所有个整数分成两个不为空的部分，一部分作为根节点的左子树，一部分作为根节点的右子树，递归地建树。当建好了树以后再计算结果，看看是否符合要求。这个算法实现起来似乎不很困难，但是写好以后发现运行不太对劲，调试了很久突然意识到，原来这样的递归存在很ooxx的问题：怎么判断左子树已经建好了？建立好以后如何立即建立右子树？事实上递归建立左子树的这个过程是把所有可能的左子树都建立好了（遍历），当建立左子树的函数返回以后，左子树是最后一个可能的情形。

所以这个算法是错误的，至于如何修正，我实在想不出来（是否有大牛可以给出建议？）。

不过从中我们可以推出4个整数可能构成的算式树总共有5种，分别是分成(1, 3)的2种，(2, 2)的1种，和(3, 1)的2种（因为3个整数的情形是2种）。具体的树结构很容易就能画出来，这里就不展开了（其实是我懒得画图再贴出来=.=，见下面代码的注释，嗯）。

这样的话，其实就可以枚举4个数字的所有排列，然后通过对5棵树的3个符号枚举再计算结果的方式来判断是否有效。

注意，这样的代码可扩展性极差：只适合4个数字个情形。

虽然这样的做法很挫，但是我还是把代码写出来了(见文末)

然后突然想起大一的时候在网上搜了很多的解法还保存在硬盘里面，于是去翻了一下，发现了一个很赞的算法：

(1) 将4个整数放入数组中，
(2) 在数组中取两个数字的排列，共有 P(4,2) 种排列。对每一个排列，
  (2.1) 对 + - * / 每一个运算符，
    (2.1.1) 根据此排列的两个数字和运算符，计算结果，
    (2.1.2) 改表数组：将此排列的变两个数字从数组中去除掉，将 2.1.1 计算的结果放入数组中，
    (2.1.3) 对新的数组，重复步骤 2，
    (2.1.4) 恢复数组：将此排列的两个数字加入数组中，将 2.1.1 计算的结果从数组中去除掉。

可以看出，步骤2是一个递归函数。当数组中只剩下一个数字的时候，这就是表达式的最终结果，此时递归结束。这个算法使用回溯来实现，事实上它可以非常容易地推广到N个数字。(代码见文末)

----------------

扩展内容：

1, 3, 4, 5, 6, 7, 8, 9 随意加括号和加减乘除，但是不能改变顺序，要求结果等于1000。

在最后的那个算法的基础上，写这个程序应该蛮简单了，反正我很快就得出结果了～

-------------

//挫算法
#include <iostream>
#include <cmath>
using namespace std;

#define N (4)
#define BAD_NUM (-1e10)
#define EPS (1e-9)
#define INVALID(t)  (cmp(t, BAD_NUM) == 0)
int data[4] = {1, 2, 3, 4};
int d[4];
int v[4] = {0, 0, 0, 0};

void dfs(int i);
int cmp(const double &a, const double &b);
double op(double a, double b, int t);
char ops[] = "+-*/";

void judge(){
    int i, j, k;
    double ans;
    for (i = 0; i < 4; ++i){
        for (j = 0; j < 4; ++j){
            for(k = 0; k < 4; ++k){
                // A~(B~(C~D))
                ans = op(d[0], op(d[1], op(d[2], d[3], k), j), i);
                if(cmp(ans, 24) == 0){
                    printf("%d%c(%d%c(%d%c%d))\n",
                            d[0],ops[i],d[1],ops[j],d[2],ops[k],d[3]);
                }
                // A~((B~C)~D)
                ans = op(d[0], op(op(d[1], d[2], j), d[3], k), i);
                if(cmp(ans, 24) == 0){
                    printf("%d%c((%d%c%d)%c%d)\n",
                            d[0],ops[i],d[1],ops[j],d[2],ops[k],d[3]);
                }
                // (A~B)~(C~D)
                ans = op(op(d[0], d[1], i), op(d[2], d[3], k), j);
                if(cmp(ans, 24) == 0){
                    printf("(%d%c%d)%c(%d%c%d)\n",
                            d[0],ops[i],d[1],ops[j],d[2],ops[k],d[3]);
                }
                // (A~(B~C))~D
                ans = op(op(d[0], op(d[1], d[2], j), i), d[3], k);
                if(cmp(ans, 24) == 0){
                    printf("(%d%c(%d%c%d))%c%d\n",
                            d[0],ops[i],d[1],ops[j],d[2],ops[k],d[3]);
                }
                // ((A~B)~C)~D
                ans = op(op(op(d[0], d[1], i), d[2], j), d[3], k);
                if(cmp(ans, 24) == 0){
                    printf("((%d%c%d)%c%d)%c%d\n",
                            d[0],ops[i],d[1],ops[j],d[2],ops[k],d[3]);
                }
            }
        }
    }
}

int main(){
    dfs(0);
    return 0;
}

void dfs(int i){ //枚举所有的排列
    for (int j = 0; j < N; ++j){
        if (v[j] == 1) continue;
        v[j] = 1;
        d[i] = data[j];
        if (i == N - 1){
            //for (int t = 0; t < N; t++) printf("%d ", d[t]); printf("\n");
            judge(); //计算
        }else{
            dfs(i + 1);
        }
        v[j] = 0;
    }
}

int cmp(const double &a, const double &b){
    if (fabs(a - b) < EPS) return 0;
    if(a - b > 0) return 1;
    return -1;
}

double op(double a, double b, int t){
    if(INVALID(a) || INVALID(b)) return BAD_NUM;
    switch(t){
        case 0: // +
            return (a + b);
        case 1: // -
            return (a - b);
        case 2: // *
            return (a * b);
        case 3: // /
            if(cmp(b, 0.0) == 0) return BAD_NUM;
            return (a / b);
        default:
            return BAD_NUM;
    }
}


//好算法
#include <iostream>
#include <cmath>
using namespace std;

#define N (4)
#define EPS (1e-9)
double d[N] = {3, 3, 8, 8};
string expr[N];

int cmp(const double &a, const double &b){
    if (fabs(a - b) < EPS) return 0;
    if(a - b > 0) return 1;
    return -1;
}

void dfs(int n){
    double a, b;
    string expa, expb;
    if(n == 1){
        if(cmp(d[0], 24) == 0){
            cout << expr[0] << " = " << d[0] << endl;
        }
        return;
    }
    int i, j;
    for (i = 0; i < n; ++i){
        for (j = i + 1; j < n; ++j){
            a = d[i];
            b = d[j];
            d[j] = d[n-1];
            expa = expr[i];
            expb = expr[j];
            expr[j] = expr[n-1];

            //a + b
            d[i] = a + b;
            expr[i] = "(" + expa + "+" + expb + ")";
            dfs(n - 1);

            //a - b
            d[i] = a - b;
            expr[i] = "(" + expa + "-" + expb + ")";
            dfs(n - 1);
            //b - a
            d[i] = b - a;
            expr[i] = "(" + expb + "-" + expa + ")";
            dfs(n - 1);

            //a * b
            d[i] = a * b;
            expr[i] = "(" + expa + "*" + expb + ")";
            dfs(n - 1);

            //a / b
            if(cmp(b, 0) != 0){
                d[i] = a / b;
                expr[i] = "(" + expa + "/" + expb + ")";
                dfs(n - 1);
            }
            //b / a
            if(cmp(a, 0) != 0){
                d[i] = b / a;
                expr[i] = "(" + expb + "/" + expa + ")";
                dfs(n - 1);
            }

            //回溯
            expr[j] = expb;
            expr[i] = expa;
            d[j] = b;
            d[i] = a;
        }
    }
}


int main(){
    for (int i = 0; i < N; ++i){
        expr[i] = (int)d[i] + '0';
    }
    dfs(N);
    return 0;
}



Generated by Bo-blog 2.1.0