[已解决]24点题目，求助大佬，要写程序！

zhangjinxuan

这一次直接给题目，我不说废话了，因为，这一次我真的绝望了

给定两个数字 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个月，到底怎么做啊


@人造人 ，我这种定义新运算的方法还是不靠谱，5 5 5 5 算不出来，您说的先枚举算式再枚举括号的方法我也写不出来，到底怎么办啊
@tommyyu 这回儿我谁的意见都听，那么，您说的打表到底打的是什么？


求助各位大佬，选为最佳答案再额外赏10鱼币10荣誉！

最佳答案

月排行榜 / 总排行榜

高山

2022-12-1 18:11:51

这个要求对算法太有难度了，我曾经研究一段时间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[MAX_COUNT_OF_NUMBER];
string expression[MAX_COUNT_OF_NUMBER];
int Search(int n, int r)
{
  int i, j;
  double a, b;
  string expa, expb;
  if (n == 1)
    {
      if (fabs(number[0] - r) < PRECISION)
        {
          cout << expression[0] << endl;
          return 1;
        }
      else
        return 0;
    }
  for (i = 0; i < n; i++)
    {
      for (j = i + 1; j < n; j++)
        {
          a = number[i];
          b = number[j];
          number[j] = number[n - 1];
          expa = expression[i];
          expb = expression[j];
          expression[j] = expression[n - 1];
          expression[i] = "(" + expa + "+" + expb + ")";
          number[i] = a + b;
          if (Search(n - 1, r))
            return 1;
          expression[i] = "(" + expa + "-" + expb + ")";
          number[i] = a - b;
          if (Search(n - 1, r))
            return 1;
          expression[i] = "(" + expa + "-" + expb + ")";
          number[i] = b - a;
          if (Search(n - 1, r))
            return 1;
          expression[i] = "(" + expa + "*" + expb + ")";
          number[i] = a * b;
          if (Search(n - 1, r))
            return 1;
          if (b != 0)
            {
              expression[i] = "(" + expa + "/" + expb + ")";
              number[i] = a / b;
              if (Search(n - 1, r))
                return 1;
            }
          if (a != 0)
            {
              expression[i] = "(" + expa + "/" + expb + ")";
              number[i] = b / a;
              if (Search(n - 1, r))
                return 1;
            }
          number[i] = a;
          number[j] = b;
          expression[i] = expa;
          expression[j] = expb;
        }
    }
  return 0;
}
int main()
{
  int i, x;
  int n, m;
  cin >> n >> m;
  for (i = 0; i < n; i++)
    {
      cin >> x;
      number[i] = x;
      expression[i] = to_string(x);
    }
  if (!Search(n, m))
    cout << "No" << endl;
}

你知道本程序来自哪里
高小山不容易，望设最佳

跳转到最佳答案楼层

高山

这个要求对算法太有难度了，我曾经研究一段时间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[MAX_COUNT_OF_NUMBER];
string expression[MAX_COUNT_OF_NUMBER];
int Search(int n, int r)
{
  int i, j;
  double a, b;
  string expa, expb;
  if (n == 1)
    {
      if (fabs(number[0] - r) < PRECISION)
        {
          cout << expression[0] << endl;
          return 1;
        }
      else
        return 0;
    }
  for (i = 0; i < n; i++)
    {
      for (j = i + 1; j < n; j++)
        {
          a = number[i];
          b = number[j];
          number[j] = number[n - 1];
          expa = expression[i];
          expb = expression[j];
          expression[j] = expression[n - 1];
          expression[i] = "(" + expa + "+" + expb + ")";
          number[i] = a + b;
          if (Search(n - 1, r))
            return 1;
          expression[i] = "(" + expa + "-" + expb + ")";
          number[i] = a - b;
          if (Search(n - 1, r))
            return 1;
          expression[i] = "(" + expa + "-" + expb + ")";
          number[i] = b - a;
          if (Search(n - 1, r))
            return 1;
          expression[i] = "(" + expa + "*" + expb + ")";
          number[i] = a * b;
          if (Search(n - 1, r))
            return 1;
          if (b != 0)
            {
              expression[i] = "(" + expa + "/" + expb + ")";
              number[i] = a / b;
              if (Search(n - 1, r))
                return 1;
            }
          if (a != 0)
            {
              expression[i] = "(" + expa + "/" + expb + ")";
              number[i] = b / a;
              if (Search(n - 1, r))
                return 1;
            }
          number[i] = a;
          number[j] = b;
          expression[i] = expa;
          expression[j] = expb;
        }
    }
  return 0;
}
int main()
{
  int i, x;
  int n, m;
  cin >> n >> m;
  for (i = 0; i < n; i++)
    {
      cin >> x;
      number[i] = x;
      expression[i] = to_string(x);
    }
  if (!Search(n, m))
    cout << "No" << endl;
}

你知道本程序来自哪里
高小山不容易，望设最佳

tommyyu

打表：如果四个数的数据范围确定，可以先预处理出每一种输入所输出的算式，存储到一个文件中，然后在用户输入的时候读文件就可以了

或者你可以使用二叉树这个数据结构枚举去找到正确的运算顺序，然后用这个运算顺序推出算式，这一步或许可以使用逆波兰表达式

zhangjinxuan

tommyyu 发表于 2022-12-1 18:29
打表：如果四个数的数据范围确定，可以先预处理出每一种输入所输出的算式，存储到一个文件中，然后在用户输 ...

8个数啊，再加上数值范围大，怎么办

zhangjinxuan

tommyyu 发表于 2022-12-1 18:29
打表：如果四个数的数据范围确定，可以先预处理出每一种输入所输出的算式，存储到一个文件中，然后在用户输 ...

打表可能不靠谱，除非你把表发给我，可能只有搜索才能做出来，但是想了很多办法都不靠谱，可能已经赶上省选甚至NOI的难度了

tommyyu

zhangjinxuan 发表于 2022-12-1 18:40
8个数啊，再加上数值范围大，怎么办

用二叉树枚举的话，对于一组数据，最多只有660602880的运算方式，应该不会超时，就看代码可不可以实现了

tommyyu

zhangjinxuan 发表于 2022-12-1 18:43
打表可能不靠谱，除非你把表发给我，可能只有搜索才能做出来，但是想了很多办法都不靠谱，可能已经赶上省 ...

那就用我说的第二种试试

或者你可以使用二叉树这个数据结构枚举去找到正确的运算顺序，然后用这个运算顺序推出算式，这一步或许可以使用逆波兰表达式

刚刚说的660602880也是说的这个方法

zhangjinxuan

tommyyu 发表于 2022-12-1 18:29
打表：如果四个数的数据范围确定，可以先预处理出每一种输入所输出的算式，存储到一个文件中，然后在用户输 ...

怎么枚举？就是枚举每个运算符的运算顺序？

比如 5*5-5/5，先枚举第一个先算的符号，再枚举第二个...以此类推？

zhangjinxuan

tommyyu 发表于 2022-12-1 18:46
那就用我说的第二种试试刚刚说的660602880也是说的这个方法

但也不对啊，找没有括号的算式都找不出来，怎么找正确的运算顺序？

tommyyu

zhangjinxuan 发表于 2022-12-1 18:48
怎么枚举？就是枚举每个运算符的运算顺序？

比如 5*5-5/5，先枚举第一个先算的符号，再枚举第二个... ...

比如 5 5 5 5，此时可以构建一个表，其中有[5, 5, 5, 5]（也可以建树）
从其中选两个元素，进行运算，比如选5和5，进行相加，变成[10, 5, 5]，把这个结果再次进行枚举（开始递归）
可以将运算的过程使用逆波兰表达式记录，如果出现了正解，就可以将逆波兰表达式变成正常的表达式，然后输出

tommyyu

zhangjinxuan 发表于 2022-12-1 18:54
但也不对啊，找没有括号的算式都找不出来，怎么找正确的运算顺序？

逆波兰表达式变正常算式的时候就是加括号的时候，运算顺序可以用逆波兰描述，逆波兰是没有括号的

zhangjinxuan

tommyyu 发表于 2022-12-1 18:55
比如 5 5 5 5，此时可以构建一个表，其中有[5, 5, 5, 5]（也可以建树）
从其中选两个元素，进行运算，比 ...

这思路好像有点道理，我开始也想到了，但是还不知道怎么写，用vector记吗？

zhangjinxuan

tommyyu 发表于 2022-12-1 18:56
逆波兰表达式变正常算式的时候就是加括号的时候，运算顺序可以用逆波兰描述，逆波兰是没有括号的

对哦

人造人

你的上一个问题我还没写完呢，^_^
主要是表达式求值花了太多的时间
我先研究研究你的上一个问题吧

zhangjinxuan

人造人 发表于 2022-12-1 18:58
你的上一个问题我还没写完呢，^_^
主要是表达式求值花了太多的时间
我先研究研究你的上一个问题吧

难道这个程序就要陨落于此了吗？不！！！！！！！！！！！！！

tommyyu

zhangjinxuan 发表于 2022-12-1 18:58
这思路好像有点道理，我开始也想到了，但是还不知道怎么写，用vector记吗？

用堆或许可以

zhangjinxuan

人造人 发表于 2022-12-1 18:58
你的上一个问题我还没写完呢，^_^
主要是表达式求值花了太多的时间
我先研究研究你的上一个问题吧

不是，找您说的，分为两步，对吧，但是我这个程序就第一步不能过去，是这个意思

zhangjinxuan

tommyyu 发表于 2022-12-1 18:44
用二叉树枚举的话，对于一组数据，最多只有660602880的运算方式，应该不会超时，就看代码可不可以实现 ...

不过我算了算，好像超过了 660602880，你想一想，数字的排列有40320种，每一个运算符位置都有4种可能七个位置，也就是说不带括号的算式有4⁷*40320=660602880，不过这只是不带括号的算式，之后还要枚举每个运算符的先算还是后算，也就是说我们还要生成一个长度为7的全排列，再依次计算………这个枚举量惊人

经过我的不准确计算，时间复杂度高达 O(n! * 4^n-1 * (n-1)!)

tommyyu

zhangjinxuan 发表于 2022-12-2 08:26
不过我算了算，好像超过了 660602880，你想一想，数字的排列有40320种，每一个运算符位置都有4种可能七个 ...

我又算了一下，也就大概444426393600次，4千亿

zhangjinxuan

tommyyu 发表于 2022-12-2 08:45
我又算了一下，也就大概444426393600次，4千亿

这肯定不行啊