算法与8个8组成1000问题的C++,java实现"/>
24点游戏回溯算法与8个8组成1000问题的C++,java实现
tags: DSA LeetCode C++ Python Java
写在前面
前阶段LeetCode出了一个很棒的活动, 叫做1024游戏, 就是通过综合数字卡和符号卡来得到1024这个数字, 符号可以是十进制运算符号或者位运算符号, 这就不得不让我想起来24点游戏, 就是通过加减乘除加括号的方式构造24这个数字, 其中蕴含的思路都是一样的, 在算法实现中, 要用到回溯的方法, 其实就是深度优先搜索, 不满足条件的话就返回中节点继续找, 下面来看一下具体思路.
679. 24 点游戏 - 力扣（LeetCode）;
思路
解法上有点像N皇后问题, 需要进行两层循环遍历找满足条件的解, 相当于遍历二叉树的层, 然后递归回溯, 相当于向树的叶子结点方向遍历.
比较麻烦的点是符号的计算, 这里可以通过Switch-case语句来做, 然后就是三个步骤
- 递归跳出条件: 列表中只剩下一个数, 且这个数为24(最终结果), 由于存在实数除法, 实现时候要通过与24作差绝对值小于某eps来判断
- 循环(层遍历): 先枚举左操作数和右操作数, 然后遍历符号, 这里虽然有加减乘除, 但是减和除可以有两种可能, 这就导致了运算符遍历时候会有6种可能, 然后将每次计算的结果添加到card(实际使用临时变量列表)之后, 完成计算之后递归.
- 回溯, 进行
pop()操作.
这里给出之前写的Python代码:(配合注释还是比较好理解的)
class Solution:def judgePoint24(self, cards: List[int]) -> bool:def calc(op, lhs, rhs):match op:case 0:return lhs+rhscase 1:return lhs-rhscase 2:return rhs-lhscase 3:return lhs*rhscase 4: # 判断被除数不为零return rhs and lhs/rhscase _:return lhs and rhs/lhsdef bt(tmp):if (n:=len(tmp))==1:return abs(24-tmp[0])<1e-4for 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 Falsereturn bt(cards)
当然还有C++代码:
class Solution {
public:bool judgePoint24(vector<int>& nums) {vector<double> digits;for (int num : nums) digits.emplace_back(num);return bt(digits);}bool bt(vector<double>& digits) {int n = digits.size();if (n == 1) { return abs(digits[0] - 24) < 0.001; }for (int i = 0; i < n - 1; ++i) {for (int j = i + 1; j < n; ++j) {vector<double> restmp;for (int k = 0; k < n; ++k) {if (k == i || k == j) continue;restmp.emplace_back(digits[k]);}for (int op = 0; op < 6; ++op) {restmp.emplace_back(calc(op, digits[i], digits[j]));if (bt(restmp)) return true;restmp.pop_back();}}}return false;}double calc(int op, double a, double b) {switch (op) {case 0:return a + b;case 1:return a - b;case 2:return b - a;case 3:return a * b;case 4:return a / b;default:return b / a;}}
};
推广: 8个8通过加减乘除合并得到1000问题
有了上面的思路, 其实就不难将算法推广到任意个运算符和任意数字的匹配了.
这里借鉴了csdn两位大佬的代码, 做了自己的改动, 得到了相同的结果.
- 使用8个8进行任意拼接和四则运算，算出1000的计算步骤_jpbirdy的博客-CSDN博客;
- 8个8通过加减乘除得到1000 深搜+剪枝 算法实现_JetMuffin的博客-CSDN博客_编程使用8个8进行任意拼接和四则运算,算出1000的计算步骤;
#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;//-1a[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;//-2a[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;// /1if (a[dep - 1].num != 0) { //&& a[i].num % a[dep - 1].num == 0a[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;}// /2if (a[i].num != 0) { //&& a[dep - 1].num % a[i].num == 0a[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==NUMBERif (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;}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");}
}
/*
* /opt/homebrew/Cellar/openjdk/18.0.1.1/libexec/openjdk.jdk/Contents/Home/bin/java -javaagent:/Applications/IntelliJ IDEA.app/Contents/lib/idea_rt.jar=59155:/Applications/IntelliJ IDEA.app/Contents/bin -Dfile.encoding=UTF-8 -Dsun.stdout.encoding=UTF-8 -Dsun.stderr.encoding=UTF-8 -classpath /Users/hep/code/java_code/test/out/production/test Main
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 msProcess finished with exit code 0* */
题外话
有兴趣的朋友可以看看fourfours, 这个游戏就是上述问题的原始问题, 就是4个4通过各种运算得到某一个确定的目标值的方法. 参考 1,2.
上面的代码, 一开始我运行java程序竟然要比C++快很多, 真的是离谱, 后来我在clang编译时候加上了-O2参数, 好吧, C++还是能打的.
The Definitive Four Fours Answer Key (by David A. Wheeler) (dwheeler); ↩︎
4个4 - 维基百科，自由的百科全书 (wikipedia); ↩︎
更多推荐
24点游戏回溯算法与8个8组成1000问题的C++,java实现
发布评论