Created by potrace 1.14, written by Peter Selinger 2001-2017 Zorch's Blog

24点游戏回溯算法与8个8组成1000问题c++,java代码

 
Category： DSA
  • zorchp
  • 2022年 12月30日

写在前面

前阶段LeetCode出了一个很棒的活动, 叫做1024游戏, 就是通过综合数字卡和符号卡来得到1024这个数字, 符号可以是十进制运算符号或者位运算符号, 这就不得不让我想起来24点游戏, 就是通过加减乘除加括号的方式构造24这个数字, 其中蕴含的思路都是一样的, 在算法实现中, 要用到回溯的方法, 其实就是深度优先搜索, 不满足条件的话就返回中节点继续找, 下面来看一下具体思路.

679. 24 点游戏 - 力扣（LeetCode）;

思路

解法上有点像N皇后问题, 需要进行两层循环遍历找满足条件的解, 相当于遍历二叉树的层, 然后递归回溯, 相当于向树的叶子结点方向遍历.

比较麻烦的点是符号的计算, 这里可以通过Switch-case语句来做, 然后就是三个步骤

  1. 递归跳出条件: 列表中只剩下一个数, 且这个数为24(最终结果), 由于存在实数除法, 实现时候要通过与24作差绝对值小于某eps来判断
  2. 循环(层遍历): 先枚举左操作数和右操作数, 然后遍历符号, 这里虽然有加减乘除, 但是减和除可以有两种可能, 这就导致了运算符遍历时候会有6种可能, 然后将每次计算的结果添加到card(实际使用临时变量列表)之后, 完成计算之后递归.
  3. 回溯, 进行pop()操作.

这里给出之前写的Python代码:(配合注释还是比较好理解的)

class Solution:
    def judgePoint24(self, cards: List[int]) -> bool:
        def calc(op, lhs, rhs):
            match op:
                case 0:
                    return lhs + rhs
                case 1:
                    return lhs - rhs
                case 2:
                    return rhs - lhs
                case 3:
                    return lhs * rhs
                case 4:  # 判断被除数不为零
                    return rhs and lhs / rhs
                case _:
                    return lhs and rhs / lhs

        def bt(tmp):
            if (n := len(tmp)) == 1:
                return abs(24 - tmp[0]) < 1e-4
            for i in range(n - 1):  # 遍历左操作数
                for j in range(i + 1, n):  # 遍历右操作数
                    restmp = []  # 存剩余的数
                    for k in range(n):
                        if k == j or k == i:
                            continue
                        # 如果两个数未被取过, 添加到剩余的数列表中
                        restmp.append(tmp[k])
                    for op in range(6):  # 遍历操作符
                        # 计算中间结果并存入剩余的数列表等待下一次计算
                        restmp.append(calc(op, tmp[i], tmp[j]))
                        # 如果回溯结果为真返回
                        if bt(restmp):
                            return True
                        # 去掉中间结果, 重新找新的两个数计算
                        restmp.pop()
            return False

        return bt(cards)

当然还有C++代码:

class Solution {
public:
    static double calc(double a, double b, int op) {
        switch (op) {
            case 0:
                return a + b;
            case 1:
                return a - b;
            case 2:
                return a * b;
            case 3:
                return a / b; // 可以不考虑除数为 0 情况
            case 4:
                return b - a;
            default:
                return b / a;
        }
    }
    bool judgePoint24(vector<int>& cards) {
        function<bool(vector<double>&)> f = [&](vector<double>& v) {
            int n = v.size();
            if (n == 1) return abs(v[0] - 24) < 1e-4;
            for (int i{}; i < n - 1; ++i) {
                for (int j{i + 1}; j < n; ++j) {
                    vector<double> res;
                    res.reserve(4);
                    for (int k{}; k < n; ++k)
                        if (k != i && k != j)
                            res.emplace_back(v[k]); // 剩下的值

                    for (int op{}; op < 6; ++op) {
                        res.emplace_back(calc(v[i], v[j], op));
                        if (f(res)) return true;
                        res.pop_back();
                    }
                }
            }
            return false;
        };
        vector<double> dc(cards.begin(), cards.end());
        return f(dc);
    }
};

推广: 8个8通过加减乘除合并得到1000问题

有了上面的思路, 其实就不难将算法推广到任意个运算符和任意数字的匹配了.

这里借鉴了csdn两位大佬的代码, 做了自己的改动, 得到了相同的结果.

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <cmath>

using namespace std;
#define NUMBER 8
const int TARGET = 1000;
const double EPS = 1e-6;
const int N = 8;
struct item {
    double num; // 数字
    string cal; // 数字对应的字符形式
    bool flag;  // 表示是否用过该数字
};

item a[N];
// 交换结构体中两数
void swap(int i, int j) {
    item t;
    t = a[i];
    a[i] = a[j];
    a[j] = t;
}

template <typename T1, typename T2>
ostream &operator<<(ostream &os, const map<T1, T2> &mp) {
    os << "{";
    for (auto &p : mp) os << "<" << p.first << ": " << p.second << ">, ";
    return os << "}" << endl;
}

set<string> ans{};

void search_ans(int dep) {
    if (dep == 1 && fabs(a[0].num - TARGET) < EPS) {
        // cout << a[0].cal << endl;
        ans.insert(a[0].cal);
        return;
    }
    // 用字典存左右操作数, 用于判断是否使用过
    map<int, int> hash;
    hash.clear(); // 每次都需要清空, 从这一组新的数开始计算
    for (int i = 0; i < dep; i++)
        for (int j = i + 1; j < dep; j++) {
            // 如果使用过就跳过
            if (hash[a[i].num] == a[j].num) continue;
            hash[a[i].num] = a[j].num;

            swap(j, dep - 1);
            item temp = a[i];

            //+
            a[i].num = a[i].num + a[dep - 1].num;
            a[i].flag = false; // 表示用过该数字
            a[i].cal = '(' + temp.cal + '+' + a[dep - 1].cal + ')';
            search_ans(dep - 1);
            a[i] = temp;

            //-1
            a[i].num = a[i].num - a[dep - 1].num;
            a[i].flag = false;
            a[i].cal = '(' + temp.cal + '-' + a[dep - 1].cal + ')';
            search_ans(dep - 1);
            a[i] = temp;
            //-2
            a[i].num = a[dep - 1].num - a[i].num;
            a[i].flag = false;
            a[i].cal = '(' + a[dep - 1].cal + '-' + temp.cal + ')';
            search_ans(dep - 1);
            a[i] = temp;

            //*
            a[i].num = a[i].num * a[dep - 1].num;
            a[i].flag = false;
            a[i].cal = '(' + temp.cal + '*' + a[dep - 1].cal + ')';
            search_ans(dep - 1);
            a[i] = temp;

            // /1
            if (a[dep - 1].num != 0) { //&& a[i].num % a[dep - 1].num == 0
                a[i].num = a[i].num / a[dep - 1].num;
                a[i].flag = false;
                a[i].cal = '(' + temp.cal + '/' + a[dep - 1].cal + ')';
                search_ans(dep - 1);
                a[i] = temp;
            }
            // /2
            if (a[i].num != 0) { //&& a[dep - 1].num % a[i].num == 0
                a[i].num = a[dep - 1].num / a[i].num;
                a[i].flag = false;
                a[i].cal = '(' + a[dep - 1].cal + '/' + temp.cal + ')';
                search_ans(dep - 1);
                a[i] = temp;
            }

            // 合并两个数:8 8->88
            // 由于每次操作(赋值)的是a[i],
            // 所以a[i].flag就蕴含了a[i].num==NUMBER
            if (a[i].flag && a[dep - 1].flag && a[dep - 1].num == NUMBER) {
                a[i].num = a[i].num * 10 + a[dep - 1].num;
                a[i].cal = temp.cal + a[dep - 1].cal;
                search_ans(dep - 1);
                a[i] = temp;
            }
            swap(dep - 1, j);
        }
}

int main() {
    freopen("out.txt", "w", stdout);
    mhash.clear();
    for (int i = 0; i < N; i++) {
        a[i].num = NUMBER;
        a[i].cal = to_string(NUMBER);
        a[i].flag = true;
    }
    search_ans(N);
    for (auto s:ans)cout<<s<<endl;
    return 0;
}

这份代码中我删去了剪枝, 因为剪枝会导致结果缺失.

另一种思路不用结构体实现:

#include <iostream>
#include <string>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <map>
#include <set>
using namespace std;

const double EPS = 1e-6;
const int NUM = 8;
const int TARGET = 1000;

double A[NUM];
string res_str[NUM];
set<string> ans;
set<string>::iterator it;
int times = 0;

bool dfs(int n) {
    // 退出条件
    if (n == 1) {
        if (fabs(A[0] - TARGET) < EPS) {
            // cout << res_str[0] << endl;
            ans.insert(res_str[0]);
        }
    }

    double a, b;
    string expa, expb;
    map<int, int> hash;
    hash.clear();

    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++) {
            times++;
            // 保存状态（操作数i,j）
            a = A[i];
            b = A[j];
            expa = res_str[i];
            expb = res_str[j];

            // hash判重
            if (hash[a] == b) continue;
            if (hash[b] == a) continue;
            hash[a] = b;

            // 改变状态
            A[j] = A[n - 1];
            res_str[j] = res_str[n - 1];

            // +
            A[i] = a + b;
            res_str[i] = '(' + expa + '+' + expb + ')';
            if (dfs(n - 1)) return true;

            // -
            A[i] = a - b;
            res_str[i] = '(' + expa + '-' + expb + ')';
            if (dfs(n - 1)) return true;

            // - 反方向
            A[i] = b - a;
            res_str[i] = '(' + expb + '-' + expa + ')';
            if (dfs(n - 1)) return true;

            // *
            A[i] = a * b;
            res_str[i] = '(' + expa + '*' + expb + ')';
            if (dfs(n - 1)) return true;

            // /
            if (b != 0) {
                A[i] = a / b;
                res_str[i] = '(' + expa + '/' + expb + ')';
                if (dfs(n - 1)) return true;
            }

            // /反方向
            if (a != 0) {
                A[i] = b / a;
                res_str[i] = '(' + expb + '/' + expa + ')';
                if (dfs(n - 1)) return true;
            }

            // 合并
            if (expa.find("(") == string::npos &&
                expb.find("(") == string::npos && b == NUM) {
                A[i] = a * 10 + b;
                res_str[i] = expa + expb;
                if (dfs(n - 1)) return true;
            }

            // 恢复状态, 回溯过程
            A[i] = a;
            A[j] = b;
            res_str[i] = expa;
            res_str[j] = expb;
        }
    return false;
}


int main() {
    for (int i = 0; i < NUM; i++) {
        A[i] = 8;
        //char c[10];
        //sprintf(c, "%.0f", A[i]);
        //res_str[i] = c;
        res_str[i] = to_string((int)A[i]);
    }
    cout << "start searching...." << endl;
    clock_t start = clock();
    dfs(NUM);
    for (it = ans.begin(); it != ans.end(); it++) { cout << *it << endl; }
    clock_t duration = clock() - start;
    cout << "found : " << ans.size() << " expressions!" << endl;
    cout << "spend : " << duration / 1000 << " ms" << endl;
}

这里我加上了合并部分的代码, 由于没有了之前结构体中的判重flag, 这里就用字符串中是否含有括号字符来完成了.

得到的结果:

((((((8*8)*8)-8)*(8+8))/8)-8)
((((((8*8)*8)-8)/8)*(8+8))-8)
((((((8*8)+(8*8))*8)-8)-8)-8)
((((((8+8)*8)-(8/8))*8)-8)-8)
((((((8/8)+8)+8)*8)*8)-88)
(((((8*8)*8)-8)*((8+8)/8))-8)
(((((8*8)*8)-8)/(8/(8+8)))-8)
(((((8*8)+(8*8))*8)-(8+8))-8)
(((((8*8)+(8*8))*8)-8)-(8+8))
(((((8*8)+(8*8))+8)*8)-88)
(((((8*8)+8)+(8*8))*8)-88)
(((((8+8)*8)*8)+(8*8))-88)
(((((8+8)*8)*8)-88)+(8*8))
(((((8+8)*8)+8)-(88/8))*8)
(((((8+8)*8)+888)-8)-8)
(((((8+8)*8)-((8+8)/8))*8)-8)
(((((8+8)*8)-(8/8))*8)-(8+8))
(((((8+8)*8)-(88/8))+8)*8)
(((((8+8)*8)-8)+888)-8)
(((((8+8)*8)-8)-8)+888)
(((((8+8)+(8/8))*8)*8)-88)
(((((8+8)-(8/(8+8)))*8)*8)+8)
(((((8-(8/(8+8)))+8)*8)*8)+8)
(((((8/8)+(8+8))*8)*8)-88)
(((((8/8)+8)*888)+8)/8)
(((((8/8)+8)+8)*(8*8))-88)
((((8*8)*(8+8))+(8*8))-88)
((((8*8)*(8+8))-88)+(8*8))
((((8*8)+((8*8)+8))*8)-88)
((((8*8)+(8*8))*8)-((8+8)+8))
((((8*8)+(8*8))*8)-(8+(8+8)))
((((8*8)-((8+8)/8))*(8+8))+8)
((((8+8)*(((8*8)*8)-8))/8)-8)
((((8+8)*(8*8))+(8*8))-88)
((((8+8)*(8*8))-88)+(8*8))
((((8+8)*(8-((8/8)/8)))*8)-8)
((((8+8)*(8-(8/(8*8))))*8)-8)
((((8+8)*8)*(8-((8/8)/8)))-8)
((((8+8)*8)*(8-(8/(8*8))))-8)
((((8+8)*8)*8)+((8*8)-88))
((((8+8)*8)*8)-(88-(8*8)))
((((8+8)*8)+(8-(88/8)))*8)
((((8+8)*8)+(888-8))-8)
((((8+8)*8)+888)-(8+8))
((((8+8)*8)-(((8+8)+8)/8))*8)
((((8+8)*8)-((88/8)-8))*8)
((((8+8)*8)-(8+8))+888)
((((8+8)*8)-(8-888))-8)
((((8+8)*8)-8)+(888-8))
((((8+8)*8)-8)-(8-888))
((((8+8)+(8/8))*(8*8))-88)
((((8+8)+8)+88)+888)
((((8+8)+8)+888)+88)
((((8+8)+88)+8)+888)
((((8+8)+88)+888)+8)
((((8+8)+888)+8)+88)
((((8+8)+888)+88)+8)
((((8+8)-(8/(8+8)))*(8*8))+8)
((((8+8)/8)*(((8*8)*8)-8))-8)
((((8-((8/(8+8))-8))*8)*8)+8)
((((8-((8/8)/8))*(8+8))*8)-8)
((((8-((8/8)/8))*8)*(8+8))-8)
((((8-(8/(8*8)))*(8+8))*8)-8)
((((8-(8/(8*8)))*8)*(8+8))-8)
((((8-(8/(8+8)))+8)*(8*8))+8)
((((8/8)+(8+8))*(8*8))-88)
((((88+8)+8)+8)+888)
((((88+8)+8)+888)+8)
((((88+8)+888)+8)+8)
((((888+8)+8)+8)+88)
((((888+8)+8)+88)+8)
((((888+8)+88)+8)+8)
((((888+88)+8)+8)+8)
(((8*(8+8))*8)-(88-(8*8)))
(((8*8)*(((8/8)+8)+8))-88)
(((8*8)*((8+8)+(8/8)))-88)
(((8*8)*((8+8)-(8/(8+8))))+8)
(((8*8)*((8-(8/(8+8)))+8))+8)
(((8*8)*((8/8)+(8+8)))-88)
(((8*8)*(8+8))+((8*8)-88))
(((8*8)*(8+8))-(88-(8*8)))
(((8*8)*(8-((8/(8+8))-8)))+8)
(((8*8)+(((8+8)*8)*8))-88)
(((8*8)+((8*8)*(8+8)))-88)
(((8*8)+((8+8)*(8*8)))-88)
(((8*8)-88)+(((8+8)*8)*8))
(((8*8)-88)+((8*(8+8))*8))
(((8*8)-88)+((8*8)*(8+8)))
(((8*8)-88)+((8+8)*(8*8)))
(((8*8)-88)+(8*((8+8)*8)))
(((8+8)*((((8*8)*8)-8)/8))-8)
(((8+8)*((8*8)-((8+8)/8)))+8)
(((8+8)*((8-((8/8)/8))*8))-8)
(((8+8)*((8-(8/(8*8)))*8))-8)
(((8+8)*(8*8))+((8*8)-88))
(((8+8)*(8*8))-(88-(8*8)))
(((8+8)*(8-(8/8)))+888)
(((8+8)*8)+((888-8)-8))
(((8+8)*8)+(888-(8+8)))
(((8+8)*8)-((8+8)-888))
(((8+8)*8)-((8-888)+8))
(((8+8)*8)-(8-(888-8)))
(((8+8)+(88+8))+888)
(((8+8)+(888+8))+88)
(((8+8)+(888+88))+8)
(((8+8)+8)+(888+88))
(((8+8)+88)+(8+888))
(((8+8)+88)+(888+8))
(((8+8)+888)+(8+88))
(((8+8)+888)+(88+8))
(((8+8)/(8/(((8*8)*8)-8)))-8)
(((8-((8/(8+8))-8))*(8*8))+8)
(((8-((8/8)/8))*((8+8)*8))-8)
(((8-(8/(8*8)))*((8+8)*8))-8)
(((8-(8/8))*(8+8))+888)
(((8-(88/8))+((8+8)*8))*8)
(((88+(8+8))+8)+888)
(((88+(8+8))+888)+8)
(((88+8)+(8+8))+888)
(((88+8)+(888+8))+8)
(((88+8)+8)+(888+8))
(((88+8)+888)+(8+8))
(((88+888)+(8+8))+8)
(((88+888)+8)+(8+8))
(((888*((8/8)+8))+8)/8)
(((888+((8+8)*8))-8)-8)
(((888+(8+8))+8)+88)
(((888+(8+8))+88)+8)
(((888+(88+8))+8)+8)
(((888+8)+(8+8))+88)
(((888+8)+(88+8))+8)
(((888+8)+8)+(88+8))
(((888+8)+88)+(8+8))
(((888+8)/8)+888)
(((888+88)+(8+8))+8)
(((888+88)+8)+(8+8))
(((888-8)+((8+8)*8))-8)
(((888-8)-8)+((8+8)*8))
((8*((8+8)*8))-(88-(8*8)))
((8*(8+8))-((8+8)-888))
((8*8)+((((8+8)*8)*8)-88))
((8*8)+(((8*8)*(8+8))-88))
((8*8)+(((8+8)*(8*8))-88))
((8*8)-(88-(((8+8)*8)*8)))
((8*8)-(88-((8*8)*(8+8))))
((8*8)-(88-((8+8)*(8*8))))
((8+8)+((88+8)+888))
((8+8)+((888+8)+88))
((8+8)+((888+88)+8))
((8+8)+(888+(88+8)))
((8-((88/8)-((8+8)*8)))*8)
((88+((8+8)+8))+888)
((88+(8+8))+(8+888))
((88+(8+8))+(888+8))
((88+(888+(8+8)))+8)
((88+(888+8))+(8+8))
((88+8)+((8+8)+888))
((88+8)+((888+8)+8))
((88+8)+(888+(8+8)))
((88+888)+((8+8)+8))
((88+888)+(8+(8+8)))
((888+(((8+8)*8)-8))-8)
((888+((8+8)*8))-(8+8))
((888+((8+8)+8))+88)
((888+((8+8)+88))+8)
((888+((88+8)+8))+8)
((888+(8+8))+(8+88))
((888+(8+8))+(88+8))
((888+(88+(8+8)))+8)
((888+(88+8))+(8+8))
((888+8)+((8+8)+88))
((888+8)+((88+8)+8))
((888+8)+(88+(8+8)))
((888+88)+((8+8)+8))
((888+88)+(8+(8+8)))
((888-(8+8))+((8+8)*8))
((888-(8+8))+(8*(8+8)))
((888-(8-((8+8)*8)))-8)
((888-8)+(((8+8)*8)-8))
((888-8)-(8-((8+8)*8)))
((8888-888)/8)
(8-(((((8/(8+8))-8)-8)*8)*8))
(8-((((8+8)/8)-(8*8))*(8+8)))
(8-((((8/(8+8))-(8+8))*8)*8))
(8-((((8/(8+8))-8)-8)*(8*8)))
(8-(((8/(8+8))-(8+8))*(8*8)))
(8-((8*8)*(((8/(8+8))-8)-8)))
(8-((8*8)*((8/(8+8))-(8+8))))
(8-((8+8)*(((8+8)/8)-(8*8))))
(88+((888+(8+8))+8))
(88+((888+8)+(8+8)))
(88+(888+((8+8)+8)))
(888+((((8+8)*8)-8)-8))
(888+(((8+8)*8)-(8+8)))
(888+(((8+8)+8)+88))
(888+(((8+8)+88)+8))
(888+(((88+8)+8)+8))
(888+((8+8)*(8-(8/8))))
(888+((8+8)+(88+8)))
(888+((8-(8/8))*(8+8)))
(888+((88+(8+8))+8))
(888+((88+8)+(8+8)))
(888+(88+((8+8)+8)))
(888-(((8/8)-8)*(8+8)))
(888-((8+8)*((8/8)-8)))
(888-((8+8)-((8+8)*8)))
(888-((8-((8+8)*8))+8))
(888-(8-(((8+8)*8)-8)))

写一个python脚本来验证其正确性:

with open('out.txt', 'r') as f:
    a=f.readlines()
k=0
for i in a:
    if(eval(i)==1000):
        k+=1
print(k)#208

java版本

import java.util.Map;
import java.util.HashSet;
import java.util.Set;
import java.util.HashMap;

public class Main {
    static final double EPS = 1e-6;
    static final int NUM = 8;
    static final int TARGET = 1000;

    static double[] A = new double[NUM];
    static String[] res_str = new String[NUM];
    static Set<String> ans = new HashSet<String>();
    static int times = 0;

    public static boolean dfs(int n) {
        // 退出条件
        if (n == 1) {
            if (Math.abs(A[0] - TARGET) < EPS) {
                if (!ans.contains(res_str[0])) {
                    ans.add(res_str[0]);
                    System.out.println(res_str[0]);
                }
            }
        }

        double a, b;
        String expa, expb;
        Map<Double, Double> hash = new HashMap<Double, Double>();

        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++) {
                times++;
                // 保存状态（操作数i,j）
                a = A[i];
                b = A[j];
                expa = res_str[i];
                expb = res_str[j];

                // hash判重
                if (hash.containsKey(a) && hash.get(a) == b) continue;
                if (hash.containsKey(b) && hash.get(b) == a) continue;
                hash.put(a, b);

                // 改变状态
                A[j] = A[n - 1];
                res_str[j] = res_str[n - 1];

                // +
                A[i] = a + b;
                res_str[i] = '(' + expa + '+' + expb + ')';
                if (dfs(n - 1)) return true;

                // -
                A[i] = a - b;
                res_str[i] = '(' + expa + '-' + expb + ')';
                if (dfs(n - 1)) return true;

                // - 反方向
                A[i] = b - a;
                res_str[i] = '(' + expb + '-' + expa + ')';
                if (dfs(n - 1)) return true;

                // *
                A[i] = a * b;
                res_str[i] = '(' + expa + '*' + expb + ')';
                if (dfs(n - 1)) return true;

                // /
                if (b != 0) {
                    A[i] = a / b;
                    res_str[i] = '(' + expa + '/' + expb + ')';
                    if (dfs(n - 1)) return true;
                }

                // /反方向
                if (a != 0) {
                    A[i] = b / a;
                    res_str[i] = '(' + expb + '/' + expa + ')';
                    if (dfs(n - 1)) return true;
                }

                // 合并
                if (!expa.contains("(") &&
                        !expb.contains("(") && b == NUM) {
                    A[i] = a * 10 + b;
                    res_str[i] = expa + expb;
                    if (dfs(n - 1)) return true;
                }

                // 恢复状态, 回溯过程
                A[i] = a;
                A[j] = b;
                res_str[i] = expa;
                res_str[j] = expb;
            }
        return false;
    }

    public static void main(String[] args) {
        for (int i = 0; i < NUM; i++) {
            A[i] = 8;
            res_str[i] = String.format("%.0f", A[i]);
        }
        System.out.println("start searching....");
        long start = System.currentTimeMillis();
        dfs(NUM);
        for (String an : ans) {
            System.out.println(an);
        }
        long duration = System.currentTimeMillis() - start;
        System.out.println("found : " + ans.size() + " expressions!");
        System.out.println("spend : " + duration + " ms");
    }
}
/*
* 
start searching....
((((8+8)*8)-(((8+8)+8)/8))*8)
((((8*8)+(8*8))*8)-((8+8)+8))
((((8+8)+8)+88)+888)
((((8+8)+8)+888)+88)
(((8+8)+8)+(888+88))
(((((8+8)*8)+8)-(88/8))*8)
(((((8+8)*8)-8)-8)+888)
(888-(8-(((8+8)*8)-8)))
(((((8+8)*8)-8)+888)-8)
((((8+8)*8)-8)+(888-8))
((((8+8)*8)-8)-(8-888))
(888-((8-((8+8)*8))+8))
((888-(8-((8+8)*8)))-8)
((888-8)-(8-((8+8)*8)))
(((((8+8)*8)*8)+(8*8))-88)
(((((8+8)*8)*8)-88)+(8*8))
((8*8)-(88-(((8+8)*8)*8)))
((((8+8)*8)*8)+((8*8)-88))
((((8+8)*8)*8)-(88-(8*8)))
((((8+8)*8)-(8+8))+888)
(888-((8+8)-((8+8)*8)))
(((((8+8)*8)-((8+8)/8))*8)-8)
(((((8+8)*8)-(8/8))*8)-(8+8))
((((8+8)*8)+888)-(8+8))
(((8+8)*8)-((8+8)-888))
(((8+8)*8)+(888-(8+8)))
((((8+8)*8)*(8-(8/(8*8))))-8)
((((((8+8)*8)-(8/8))*8)-8)-8)
((((8+8)*8)*(8-((8/8)/8)))-8)
(((((8+8)*8)-(88/8))+8)*8)
((8-((88/8)-((8+8)*8)))*8)
((((8+8)*8)-((88/8)-8))*8)
((((8+8)*8)+(8-(88/8)))*8)
(((((8+8)*8)+888)-8)-8)
((((8+8)*8)+(888-8))-8)
(((8+8)*8)+((888-8)-8))
(((8+8)*8)-(8-(888-8)))
((((8+8)*8)-(8-888))-8)
(((8+8)*8)-((8-888)+8))
(8-((((8+8)/8)-(8*8))*(8+8)))
((((8*8)-((8+8)/8))*(8+8))+8)
((((8+8)/8)*(((8*8)*8)-8))-8)
(8-(((((8/(8+8))-8)-8)*8)*8))
(8-((((8/(8+8))-8)-8)*(8*8)))
((((8-((8/(8+8))-8))*8)*8)+8)
(((8-((8/(8+8))-8))*(8*8))+8)
(((((8-(8/(8+8)))+8)*8)*8)+8)
((((8-(8/(8+8)))+8)*(8*8))+8)
(8-((((8/(8+8))-(8+8))*8)*8))
(8-(((8/(8+8))-(8+8))*(8*8)))
(((((8+8)-(8/(8+8)))*8)*8)+8)
((((8+8)-(8/(8+8)))*(8*8))+8)
(((((8*8)*8)-8)/(8/(8+8)))-8)
(8-((8+8)*(((8+8)/8)-(8*8))))
(((8+8)*((8*8)-((8+8)/8)))+8)
((888-(8+8))+((8+8)*8))
((((8+8)*(8*8))+(8*8))-88)
((((8+8)*(8*8))-88)+(8*8))
((8*8)-(88-((8+8)*(8*8))))
(((8+8)*(8*8))+((8*8)-88))
(((8+8)*(8*8))-(88-(8*8)))
((((8+8)*(((8*8)*8)-8))/8)-8)
(((8+8)*((((8*8)*8)-8)/8))-8)
(((8+8)/(8/(((8*8)*8)-8)))-8)
((((8+8)*(8-(8/(8*8))))*8)-8)
(((8+8)*((8-(8/(8*8)))*8))-8)
(((((8*8)+(8*8))*8)-(8+8))-8)
(((((8*8)+(8*8))*8)-8)-(8+8))
((((8+8)+(8/8))*(8*8))-88)
(((((8+8)+(8/8))*8)*8)-88)
(888-((8+8)*((8/8)-8)))
(((8+8)*(8-(8/8)))+888)
((((8+8)*(8-((8/8)/8)))*8)-8)
(((8+8)*((8-((8/8)/8))*8))-8)
((((8+8)+88)+8)+888)
((((8+8)+88)+888)+8)
(((8+8)+88)+(888+8))
(((8+8)+(88+8))+888)
(((8+8)+888)+(88+8))
((8+8)+((88+8)+888))
((((8+8)+888)+8)+88)
((((8+8)+888)+88)+8)
(((8+8)+(888+8))+88)
((8+8)+((888+8)+88))
((8*(8+8))-((8+8)-888))
((888-(8+8))+(8*(8+8)))
(((8+8)+888)+(8+88))
(((8+8)+(888+88))+8)
((8+8)+((888+88)+8))
((8+8)+(888+(88+8)))
(((8+8)+88)+(8+888))
(((((8*8)+8)+(8*8))*8)-88)
((((((8*8)*8)-8)/8)*(8+8))-8)
((((((8*8)*8)-8)*(8+8))/8)-8)
(((((8*8)*8)-8)*((8+8)/8))-8)
((((8-(8/(8*8)))*8)*(8+8))-8)
((((8-(8/(8*8)))*(8+8))*8)-8)
(((8-(8/(8*8)))*((8+8)*8))-8)
((((8*8)*(8+8))+(8*8))-88)
((((8*8)*(8+8))-88)+(8*8))
((8*8)-(88-((8*8)*(8+8))))
(((8*8)*(8+8))+((8*8)-88))
(((8*8)*(8+8))-(88-(8*8)))
(((8*8)+(((8+8)*8)*8))-88)
(((8*8)-88)+(((8+8)*8)*8))
((8*8)+((((8+8)*8)*8)-88))
(8-((8*8)*(((8/(8+8))-8)-8)))
(((8*8)*(8-((8/(8+8))-8)))+8)
(((8*8)*((8-(8/(8+8)))+8))+8)
(8-((8*8)*((8/(8+8))-(8+8))))
(((8*8)*((8+8)-(8/(8+8))))+8)
(((8*8)+((8+8)*(8*8)))-88)
(((8*8)-88)+((8+8)*(8*8)))
((8*8)+(((8+8)*(8*8))-88))
(((8*8)*((8+8)+(8/8)))-88)
(((((8*8)+(8*8))+8)*8)-88)
((((((8*8)+(8*8))*8)-8)-8)-8)
((((8*8)+(8*8))*8)-(8+(8+8)))
(((8*8)+((8*8)*(8+8)))-88)
(((8*8)-88)+((8*8)*(8+8)))
((8*8)+(((8*8)*(8+8))-88))
((((8*8)+((8*8)+8))*8)-88)
(((8*8)*(((8/8)+8)+8))-88)
(((8*8)*((8/8)+(8+8)))-88)
(((8*8)-88)+((8*(8+8))*8))
(((8*8)-88)+(8*((8+8)*8)))
(((8*(8+8))*8)-(88-(8*8)))
((8*((8+8)*8))-(88-(8*8)))
((((((8/8)+8)+8)*8)*8)-88)
(((((8/8)+8)+8)*(8*8))-88)
(((((8/8)+8)*888)+8)/8)
(888-(((8/8)-8)*(8+8)))
(((8-(8/8))*(8+8))+888)
((((8-((8/8)/8))*8)*(8+8))-8)
((((8-((8/8)/8))*(8+8))*8)-8)
(((8-((8/8)/8))*((8+8)*8))-8)
(((((8/8)+(8+8))*8)*8)-88)
((((8/8)+(8+8))*(8*8))-88)
((((88+8)+8)+8)+888)
((((88+8)+8)+888)+8)
(((88+8)+8)+(888+8))
(((88+8)+(8+8))+888)
(((88+8)+888)+(8+8))
((88+8)+((8+8)+888))
((((88+8)+888)+8)+8)
(((88+8)+(888+8))+8)
((88+8)+((888+8)+8))
((88+8)+(888+(8+8)))
(((8-(88/8))+((8+8)*8))*8)
((((888+8)+8)+8)+88)
((((888+8)+8)+88)+8)
(((888+8)+8)+(88+8))
(((888+8)/8)+888)
(((888+8)+(8+8))+88)
(((888+8)+88)+(8+8))
((888+8)+((8+8)+88))
((((888+8)+88)+8)+8)
(((888+8)+(88+8))+8)
((888+8)+((88+8)+8))
((888+8)+(88+(8+8)))
(((888-8)-8)+((8+8)*8))
(((888-8)+((8+8)*8))-8)
((888-8)+(((8+8)*8)-8))
((8888-888)/8)
(((888+(8+8))+8)+88)
(((888+(8+8))+88)+8)
((888+(8+8))+(88+8))
((888+((8+8)+8))+88)
((888+88)+((8+8)+8))
(888+(((8+8)+8)+88))
(((888+((8+8)*8))-8)-8)
((888+((8+8)*8))-(8+8))
((888+(((8+8)*8)-8))-8)
(888+((((8+8)*8)-8)-8))
(888+(((8+8)*8)-(8+8)))
(888+((8+8)*(8-(8/8))))
((888+(8+8))+(8+88))
(((888+88)+(8+8))+8)
(((888+88)+8)+(8+8))
((888+((8+8)+88))+8)
(888+(((8+8)+88)+8))
((888+(88+8))+(8+8))
(888+((8+8)+(88+8)))
(((888*((8/8)+8))+8)/8)
(888+((8-(8/8))*(8+8)))
((((888+88)+8)+8)+8)
(((888+(88+8))+8)+8)
((888+((88+8)+8))+8)
(888+(((88+8)+8)+8))
(888+((88+8)+(8+8)))
((888+88)+(8+(8+8)))
((888+(88+(8+8)))+8)
(888+((88+(8+8))+8))
(888+(88+((8+8)+8)))
(((88+(8+8))+8)+888)
(((88+(8+8))+888)+8)
((88+(8+8))+(888+8))
((88+((8+8)+8))+888)
((88+(8+8))+(8+888))
(((88+888)+8)+(8+8))
(((88+888)+(8+8))+8)
((88+888)+(8+(8+8)))
((88+(888+(8+8)))+8)
(88+((888+(8+8))+8))
((88+(888+8))+(8+8))
(88+((888+8)+(8+8)))
((88+888)+((8+8)+8))
(88+(888+((8+8)+8)))
((((8+8)+88)+8)+888)
(((8-(8/8))*(8+8))+888)
(((((8/8)+8)+8)*(8*8))-88)
(888+((8+8)+(88+8)))
(888-((8+8)*((8/8)-8)))
(((8+8)+88)+(888+8))
(88+((888+(8+8))+8))
(888+((88+8)+(8+8)))
(((888-8)+((8+8)*8))-8)
((88+8)+((888+8)+8))
(888+((8+8)*(8-(8/8))))
((((((8*8)*8)-8)/8)*(8+8))-8)
(((((8*8)+(8*8))+8)*8)-88)
(((((8+8)*8)-8)-8)+888)
(((88+888)+8)+(8+8))
(((888+8)+88)+(8+8))
(8-(((((8/(8+8))-8)-8)*8)*8))
((((8+8)+8)+888)+88)
((888+(88+(8+8)))+8)
((88+(8+8))+(8+888))
(888+(((88+8)+8)+8))
(((8*8)-88)+((8*8)*(8+8)))
((((8+8)+8)+88)+888)
(((((8*8)*8)-8)/(8/(8+8)))-8)
((((8+8)*(8*8))+(8*8))-88)
((((8-((8/8)/8))*8)*(8+8))-8)
((888+(8+8))+(8+88))
((((8+8)*8)-(8+8))+888)
((((888+88)+8)+8)+8)
((((8+8)*8)-(((8+8)+8)/8))*8)
(888+(88+((8+8)+8)))
((88+888)+((8+8)+8))
((888+88)+(8+(8+8)))
((((8+8)-(8/(8+8)))*(8*8))+8)
(((((8-(8/(8+8)))+8)*8)*8)+8)
(((888+((8+8)*8))-8)-8)
((8*8)-(88-((8+8)*(8*8))))
(((((8*8)+(8*8))*8)-8)-(8+8))
((((8+8)*8)*(8-(8/(8*8))))-8)
((((((8+8)*8)-(8/8))*8)-8)-8)
((888-(8-((8+8)*8)))-8)
((((8+8)*8)+888)-(8+8))
(((8+8)*8)-(8-(888-8)))
((888-8)+(((8+8)*8)-8))
(((((8*8)+8)+(8*8))*8)-88)
((888+((8+8)+8))+88)
((888+(88+8))+(8+8))
((8+8)+((88+8)+888))
(88+((888+8)+(8+8)))
((8*8)+(((8*8)*(8+8))-88))
(((888+8)+8)+(88+8))
(8-((8*8)*((8/(8+8))-(8+8))))
((888+((88+8)+8))+8)
(((8-((8/(8+8))-8))*(8*8))+8)
(((8*8)-88)+(8*((8+8)*8)))
(88+(888+((8+8)+8)))
((((8+8)+(8/8))*(8*8))-88)
((88+((8+8)+8))+888)
(((88+8)+(888+8))+8)
(8-((((8/(8+8))-8)-8)*(8*8)))
((((8+8)+888)+8)+88)
((88+888)+(8+(8+8)))
((888+8)+(88+(8+8)))
(8-((((8+8)/8)-(8*8))*(8+8)))
((8+8)+((888+8)+88))
((((8+8)*(((8*8)*8)-8))/8)-8)
((((8*8)+((8*8)+8))*8)-88)
((8*8)-(88-(((8+8)*8)*8)))
((((8+8)*8)+(888-8))-8)
(((8+8)*(8*8))-(88-(8*8)))
((888+((8+8)*8))-(8+8))
((((8+8)*8)*8)-(88-(8*8)))
(((8-(8/(8*8)))*((8+8)*8))-8)
(((((8+8)*8)-(8/8))*8)-(8+8))
(((8+8)*(8-(8/8)))+888)
(((888-8)-8)+((8+8)*8))
((((8+8)*8)*(8-((8/8)/8)))-8)
((((((8*8)*8)-8)*(8+8))/8)-8)
(((88+888)+(8+8))+8)
(((((8+8)*8)-(88/8))+8)*8)
(((((8/8)+(8+8))*8)*8)-88)
(((8*8)-88)+((8+8)*(8*8)))
((8*8)+(((8+8)*(8*8))-88))
(((888+8)/8)+888)
((8888-888)/8)
(((8+8)*8)-((8-888)+8))
(888+(((8+8)+8)+88))
((888+((8+8)+88))+8)
((((8-(8/(8*8)))*8)*(8+8))-8)
(8-((8+8)*(((8+8)/8)-(8*8))))
(((888*((8/8)+8))+8)/8)
(((8*8)+((8+8)*(8*8)))-88)
((888-(8+8))+((8+8)*8))
(((8+8)*(8*8))+((8*8)-88))
(((8*8)*((8+8)+(8/8)))-88)
((((8/8)+(8+8))*(8*8))-88)
(((((8+8)+(8/8))*8)*8)-88)
(((88+(8+8))+8)+888)
(((888+88)+(8+8))+8)
((8-((88/8)-((8+8)*8)))*8)
((((8+8)+88)+888)+8)
((((8+8)*8)-8)-(8-888))
(((888+(88+8))+8)+8)
((((8+8)*(8*8))-88)+(8*8))
(888+(((8+8)*8)-(8+8)))
((((8*8)*(8+8))-88)+(8*8))
((888+8)+((88+8)+8))
(((((8+8)*8)*8)+(8*8))-88)
(888-(8-(((8+8)*8)-8)))
((((888+8)+8)+8)+88)
(((888+8)+(8+8))+88)
((((88+8)+888)+8)+8)
(((((8+8)*8)-8)+888)-8)
(((8+8)+888)+(88+8))
((888-8)-(8-((8+8)*8)))
(((8*8)*(8+8))+((8*8)-88))
(((8+8)+(888+8))+88)
((888+(((8+8)*8)-8))-8)
((((8-((8/(8+8))-8))*8)*8)+8)
(((8+8)*8)-((8+8)-888))
((((8+8)*8)-(8-888))-8)
((888+88)+((8+8)+8))
(((8-((8/8)/8))*((8+8)*8))-8)
((88+(8+8))+(888+8))
((8*8)-(88-((8*8)*(8+8))))
(((88+(8+8))+888)+8)
(((8*8)*(8-((8/(8+8))-8)))+8)
((((88+8)+8)+888)+8)
((((888+8)+8)+88)+8)
(((888+(8+8))+8)+88)
(8-(((8/(8+8))-(8+8))*(8*8)))
(((8*8)*((8-(8/(8+8)))+8))+8)
(((8*8)*(((8/8)+8)+8))-88)
((((8-(8/(8+8)))+8)*(8*8))+8)
(888+((((8+8)*8)-8)-8))
(((8+8)+88)+(8+888))
(((8*8)*(8+8))-(88-(8*8)))
((((((8*8)+(8*8))*8)-8)-8)-8)
(((88+8)+888)+(8+8))
(((((8+8)*8)+888)-8)-8)
(((88+8)+(8+8))+888)
((((8+8)+888)+88)+8)
(((8+8)*8)+(888-(8+8)))
((((888+8)+88)+8)+8)
(((88+8)+8)+(888+8))
((88+(888+(8+8)))+8)
((88+8)+(888+(8+8)))
(888-((8+8)-((8+8)*8)))
(((8+8)+(888+88))+8)
(((((8*8)+(8*8))*8)-(8+8))-8)
(((8+8)*((((8*8)*8)-8)/8))-8)
((((8-((8/8)/8))*(8+8))*8)-8)
((8+8)+(888+(88+8)))
((((8+8)*8)*8)+((8*8)-88))
(8-((((8/(8+8))-(8+8))*8)*8))
(((8*8)-88)+(((8+8)*8)*8))
(((888+(8+8))+88)+8)
((8+8)+((888+88)+8))
(888+((8-(8/8))*(8+8)))
((8*8)+((((8+8)*8)*8)-88))
(((8+8)+8)+(888+88))
(((8+8)*((8*8)-((8+8)/8)))+8)
(((8-(88/8))+((8+8)*8))*8)
(((8*8)*((8+8)-(8/(8+8))))+8)
(888-(((8/8)-8)*(8+8)))
(((8+8)*((8-((8/8)/8))*8))-8)
((((8-(8/(8*8)))*(8+8))*8)-8)
(((8+8)+888)+(8+88))
((888+8)+((8+8)+88))
((8*((8+8)*8))-(88-(8*8)))
((((8*8)+(8*8))*8)-(8+(8+8)))
((88+(888+8))+(8+8))
(((8+8)*8)+((888-8)-8))
(((8+8)*((8-(8/(8*8)))*8))-8)
(((((8+8)*8)+8)-(88/8))*8)
((((8*8)*(8+8))+(8*8))-88)
((((8+8)/8)*(((8*8)*8)-8))-8)
(((888+8)+(88+8))+8)
((((8+8)*(8-(8/(8*8))))*8)-8)
(((8*8)+(((8+8)*8)*8))-88)
(8-((8*8)*(((8/(8+8))-8)-8)))
(((888+88)+8)+(8+8))
((88+8)+((8+8)+888))
(((((8*8)*8)-8)*((8+8)/8))-8)
(((8*(8+8))*8)-(88-(8*8)))
(((((8+8)-(8/(8+8)))*8)*8)+8)
((888-(8+8))+(8*(8+8)))
((888+(8+8))+(88+8))
(888+(((8+8)+88)+8))
(((8*8)*((8/8)+(8+8)))-88)
((((88+8)+8)+8)+888)
((8*(8+8))-((8+8)-888))
(888-((8-((8+8)*8))+8))
(((((8+8)*8)-((8+8)/8))*8)-8)
((((8+8)*8)+(8-(88/8)))*8)
(((((8+8)*8)*8)-88)+(8*8))
((((8+8)*(8-((8/8)/8)))*8)-8)
(((((8/8)+8)*888)+8)/8)
((((8*8)-((8+8)/8))*(8+8))+8)
(((8+8)/(8/(((8*8)*8)-8)))-8)
(((8*8)+((8*8)*(8+8)))-88)
((((8+8)*8)-((88/8)-8))*8)
(((8+8)+(88+8))+888)
((((8*8)+(8*8))*8)-((8+8)+8))
(888+((88+(8+8))+8))
((((8+8)*8)-8)+(888-8))
(((8*8)-88)+((8*(8+8))*8))
((((((8/8)+8)+8)*8)*8)-88)
found : 208 expressions!
spend : 2870 ms

Process finished with exit code 0

* */

题外话

有兴趣的朋友可以看看fourfours, 这个游戏就是上述问题的原始问题, 就是4个4通过各种运算得到某一个确定的目标值的方法. 参考 1,2.

上面的代码, 一开始我运行java程序竟然要比C++快很多, 真的是离谱, 后来我在clang编译时候加上了-O2参数, 好吧, C++还是能打的.

  1. The Definitive Four Fours Answer Key (by David A. Wheeler) (dwheeler.com); ↩

  2. 4个4 - 维基百科，自由的百科全书 (wikipedia.org); ↩

search search_off backspace