24点题目，求助大佬，要写程序！
本帖最后由 zhangjinxuan 于 2022-12-1 18:15 编辑这一次直接给题目，我不说废话了，因为，这一次我真的绝望了{:10_266:}
给定两个数字 n (3 <= n <= 8), m (-10000000 <= m <= 10000000)，接下来输入 n 个数 (设数字为 i，那么 -1000000 <= i <= 1000000)，最后输出这些数字可不可以通过加减乘除凑成 m，可以则输出算式，算式中可以出现括号
样例：
4 24
1 2 3 4
(1+2+3)*4=24
输出其一解即可
由于8个数字可能很跑起来很吃力，时间限制5秒
就这么一道30秒不到就可以读完的题，我前前后后想了3个月，到底怎么做啊{:10_266:}
@人造人 ，我这种定义新运算的方法还是不靠谱，5 5 5 5 算不出来，您说的先枚举算式再枚举括号的方法我也写不出来，到底怎么办啊
@tommyyu 这回儿我谁的意见都听，那么，您说的打表到底打的是什么？
求助各位大佬，选为最佳答案再额外赏10鱼币10荣誉！
本帖最后由 高山 于 2022-12-4 19:11 编辑
这个要求对算法太有难度了，我曾经研究一段时间24点算法，也写过一些程度，但的确没有找到完美的算法，难度有两点
1、算法里面可能会出现浮点，如对4个数算24，3 3 8 8 唯一的解是((3/8-3)/8)，因为C++不支持分数运算，所以3/8要用浮点，这个会影响程序执行效率。
2、运算优先级，这个我没有完全解决，如我的程序，对3 3 8 8算24，结果为(((3/8)-3)/8),我也曾经写过专门优化（）的程序，但过于复杂。
以下是我写的参考，只是对8个数，5秒我的程序做不到。（希望能一起探讨下）
#include <cmath>
#include <iostream>
#include <string>
using namespace std;
//因为有除，所以要用浮点
#define PRECISION 1E-6
//最多8个数
#define MAX_COUNT_OF_NUMBER 8
double number;
string expression;
int Search(int n, int r)
{
int i, j;
double a, b;
string expa, expb;
if (n == 1)
{
if (fabs(number - r) < PRECISION)
{
cout << expression << endl;
return 1;
}
else
return 0;
}
for (i = 0; i < n; i++)
{
for (j = i + 1; j < n; j++)
{
a = number;
b = number;
number = number;
expa = expression;
expb = expression;
expression = expression;
expression = "(" + expa + "+" + expb + ")";
number = a + b;
if (Search(n - 1, r))
return 1;
expression = "(" + expa + "-" + expb + ")";
number = a - b;
if (Search(n - 1, r))
return 1;
expression = "(" + expa + "-" + expb + ")";
number = b - a;
if (Search(n - 1, r))
return 1;
expression = "(" + expa + "*" + expb + ")";
number = a * b;
if (Search(n - 1, r))
return 1;
if (b != 0)
{
expression = "(" + expa + "/" + expb + ")";
number = a / b;
if (Search(n - 1, r))
return 1;
}
if (a != 0)
{
expression = "(" + expa + "/" + expb + ")";
number = b / a;
if (Search(n - 1, r))
return 1;
}
number = a;
number = b;
expression = expa;
expression = expb;
}
}
return 0;
}
int main()
{
int i, x;
int n, m;
cin >> n >> m;
for (i = 0; i < n; i++)
{
cin >> x;
number = x;
expression = to_string(x);
}
if (!Search(n, m))
cout << "No" << endl;
}
你知道本程序来自哪里
高小山不容易，望设最佳 打表：如果四个数的数据范围确定，可以先预处理出每一种输入所输出的算式，存储到一个文件中，然后在用户输入的时候读文件就可以了
或者你可以使用二叉树这个数据结构枚举去找到正确的运算顺序，然后用这个运算顺序推出算式，这一步或许可以使用逆波兰表达式 tommyyu 发表于 2022-12-1 18:29
打表：如果四个数的数据范围确定，可以先预处理出每一种输入所输出的算式，存储到一个文件中，然后在用户输 ...
8个数啊，再加上数值范围大，怎么办{:10_266:} tommyyu 发表于 2022-12-1 18:29
打表：如果四个数的数据范围确定，可以先预处理出每一种输入所输出的算式，存储到一个文件中，然后在用户输 ...
打表可能不靠谱，除非你把表发给我，可能只有搜索才能做出来，但是想了很多办法都不靠谱，可能已经赶上省选甚至NOI的难度了{:10_277:} 本帖最后由 tommyyu 于 2022-12-1 18:46 编辑
zhangjinxuan 发表于 2022-12-1 18:40
8个数啊，再加上数值范围大，怎么办
用二叉树枚举的话，对于一组数据，最多只有660602880的运算方式，应该不会超时，就看代码可不可以实现了 本帖最后由 tommyyu 于 2022-12-1 18:47 编辑
zhangjinxuan 发表于 2022-12-1 18:43
打表可能不靠谱，除非你把表发给我，可能只有搜索才能做出来，但是想了很多办法都不靠谱，可能已经赶上省 ...
那就用我说的第二种试试或者你可以使用二叉树这个数据结构枚举去找到正确的运算顺序，然后用这个运算顺序推出算式，这一步或许可以使用逆波兰表达式刚刚说的660602880也是说的这个方法 tommyyu 发表于 2022-12-1 18:29
打表：如果四个数的数据范围确定，可以先预处理出每一种输入所输出的算式，存储到一个文件中，然后在用户输 ...
怎么枚举？就是枚举每个运算符的运算顺序？
比如 5*5-5/5，先枚举第一个先算的符号，再枚举第二个...以此类推？ tommyyu 发表于 2022-12-1 18:46
那就用我说的第二种试试刚刚说的660602880也是说的这个方法
但也不对啊，找没有括号的算式都找不出来，怎么找正确的运算顺序？ zhangjinxuan 发表于 2022-12-1 18:48
怎么枚举？就是枚举每个运算符的运算顺序？
比如 5*5-5/5，先枚举第一个先算的符号，再枚举第二个... ...
比如 5 5 5 5，此时可以构建一个表，其中有（也可以建树）
从其中选两个元素，进行运算，比如选5和5，进行相加，变成，把这个结果再次进行枚举（开始递归）
可以将运算的过程使用逆波兰表达式记录，如果出现了正解，就可以将逆波兰表达式变成正常的表达式，然后输出 本帖最后由 tommyyu 于 2022-12-1 18:58 编辑
zhangjinxuan 发表于 2022-12-1 18:54
但也不对啊，找没有括号的算式都找不出来，怎么找正确的运算顺序？
逆波兰表达式变正常算式的时候就是加括号的时候，运算顺序可以用逆波兰描述，逆波兰是没有括号的 tommyyu 发表于 2022-12-1 18:55
比如 5 5 5 5，此时可以构建一个表，其中有（也可以建树）
从其中选两个元素，进行运算，比 ...
这思路好像有点道理，我开始也想到了，但是还不知道怎么写，用vector记吗？ tommyyu 发表于 2022-12-1 18:56
逆波兰表达式变正常算式的时候就是加括号的时候，运算顺序可以用逆波兰描述，逆波兰是没有括号的
对哦{:10_257:} 你的上一个问题我还没写完呢，^_^
主要是表达式求值花了太多的时间
我先研究研究你的上一个问题吧
人造人 发表于 2022-12-1 18:58
你的上一个问题我还没写完呢，^_^
主要是表达式求值花了太多的时间
我先研究研究你的上一个问题吧
难道这个程序就要陨落于此了吗？不！！！！！！！！！！！！！ zhangjinxuan 发表于 2022-12-1 18:58
这思路好像有点道理，我开始也想到了，但是还不知道怎么写，用vector记吗？
用堆或许可以 人造人 发表于 2022-12-1 18:58
你的上一个问题我还没写完呢，^_^
主要是表达式求值花了太多的时间
我先研究研究你的上一个问题吧
不是，找您说的，分为两步，对吧，但是我这个程序就第一步不能过去，是这个意思{:10_266:} 本帖最后由 zhangjinxuan 于 2022-12-2 08:29 编辑
tommyyu 发表于 2022-12-1 18:44
用二叉树枚举的话，对于一组数据，最多只有660602880的运算方式，应该不会超时，就看代码可不可以实现 ...
不过我算了算，好像超过了 660602880，你想一想，数字的排列有40320种，每一个运算符位置都有4种可能七个位置，也就是说不带括号的算式有47*40320=660602880，不过这只是不带括号的算式，之后还要枚举每个运算符的先算还是后算，也就是说我们还要生成一个长度为7的全排列，再依次计算………这个枚举量惊人
经过我的不准确计算，时间复杂度高达 O(n! * 4n-1 * (n-1)!) zhangjinxuan 发表于 2022-12-2 08:26
不过我算了算，好像超过了 660602880，你想一想，数字的排列有40320种，每一个运算符位置都有4种可能七个 ...
我又算了一下，也就大概444426393600次，4千亿{:10_282:} tommyyu 发表于 2022-12-2 08:45
我又算了一下，也就大概444426393600次，4千亿
这肯定不行啊{:10_266:}