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

zhangjinxuan

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

给定两个数字 n (3 <= n <= 8), m (-10000000 <= m <= 10000000)，接下来输入 n 个数 (设数字为 i，那么 -1000000 <= i <= 1000000)，最后输出这些数字可不可以通过加减乘除凑成 m，可以则输出算式，算式中可以出现括号

样例：

1. 4 24
   
2. 1 2 3 4

复制代码

1. (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秒我的程序做不到。（希望能一起探讨下）

1. #include <cmath>
   
2. #include <iostream>
   
3. #include <string>
   
4. using namespace std;
   
5. //因为有除，所以要用浮点
   
6. #define PRECISION 1E-6
   
7. //最多8个数
   
8. #define MAX_COUNT_OF_NUMBER 8
   
9. double number[MAX_COUNT_OF_NUMBER];
   
10. string expression[MAX_COUNT_OF_NUMBER];
    
11. int Search(int n, int r)
    
12. {
    
13.   int i, j;
    
14.   double a, b;
    
15.   string expa, expb;
    
16.   if (n == 1)
    
17.     {
    
18.       if (fabs(number[0] - r) < PRECISION)
    
19.         {
    
20.           cout << expression[0] << endl;
    
21.           return 1;
    
22.         }
    
23.       else
    
24.         return 0;
    
25.     }
    
26.   for (i = 0; i < n; i++)
    
27.     {
    
28.       for (j = i + 1; j < n; j++)
    
29.         {
    
30.           a = number[i];
    
31.           b = number[j];
    
32.           number[j] = number[n - 1];
    
33.           expa = expression[i];
    
34.           expb = expression[j];
    
35.           expression[j] = expression[n - 1];
    
36.           expression[i] = "(" + expa + "+" + expb + ")";
    
37.           number[i] = a + b;
    
38.           if (Search(n - 1, r))
    
39.             return 1;
    
40.           expression[i] = "(" + expa + "-" + expb + ")";
    
41.           number[i] = a - b;
    
42.           if (Search(n - 1, r))
    
43.             return 1;
    
44.           expression[i] = "(" + expa + "-" + expb + ")";
    
45.           number[i] = b - a;
    
46.           if (Search(n - 1, r))
    
47.             return 1;
    
48.           expression[i] = "(" + expa + "*" + expb + ")";
    
49.           number[i] = a * b;
    
50.           if (Search(n - 1, r))
    
51.             return 1;
    
52.           if (b != 0)
    
53.             {
    
54.               expression[i] = "(" + expa + "/" + expb + ")";
    
55.               number[i] = a / b;
    
56.               if (Search(n - 1, r))
    
57.                 return 1;
    
58.             }
    
59.           if (a != 0)
    
60.             {
    
61.               expression[i] = "(" + expa + "/" + expb + ")";
    
62.               number[i] = b / a;
    
63.               if (Search(n - 1, r))
    
64.                 return 1;
    
65.             }
    
66.           number[i] = a;
    
67.           number[j] = b;
    
68.           expression[i] = expa;
    
69.           expression[j] = expb;
    
70.         }
    
71.     }
    
72.   return 0;
    
73. }
    
74. int main()
    
75. {
    
76.   int i, x;
    
77.   int n, m;
    
78.   cin >> n >> m;
    
79.   for (i = 0; i < n; i++)
    
80.     {
    
81.       cin >> x;
    
82.       number[i] = x;
    
83.       expression[i] = to_string(x);
    
84.     }
    
85.   if (!Search(n, m))
    
86.     cout << "No" << endl;
    
87. }
    
88. 
    

复制代码

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

跳转到最佳答案楼层

高山

这个要求对算法太有难度了，我曾经研究一段时间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秒我的程序做不到。（希望能一起探讨下）

1. #include <cmath>
   
2. #include <iostream>
   
3. #include <string>
   
4. using namespace std;
   
5. //因为有除，所以要用浮点
   
6. #define PRECISION 1E-6
   
7. //最多8个数
   
8. #define MAX_COUNT_OF_NUMBER 8
   
9. double number[MAX_COUNT_OF_NUMBER];
   
10. string expression[MAX_COUNT_OF_NUMBER];
    
11. int Search(int n, int r)
    
12. {
    
13.   int i, j;
    
14.   double a, b;
    
15.   string expa, expb;
    
16.   if (n == 1)
    
17.     {
    
18.       if (fabs(number[0] - r) < PRECISION)
    
19.         {
    
20.           cout << expression[0] << endl;
    
21.           return 1;
    
22.         }
    
23.       else
    
24.         return 0;
    
25.     }
    
26.   for (i = 0; i < n; i++)
    
27.     {
    
28.       for (j = i + 1; j < n; j++)
    
29.         {
    
30.           a = number[i];
    
31.           b = number[j];
    
32.           number[j] = number[n - 1];
    
33.           expa = expression[i];
    
34.           expb = expression[j];
    
35.           expression[j] = expression[n - 1];
    
36.           expression[i] = "(" + expa + "+" + expb + ")";
    
37.           number[i] = a + b;
    
38.           if (Search(n - 1, r))
    
39.             return 1;
    
40.           expression[i] = "(" + expa + "-" + expb + ")";
    
41.           number[i] = a - b;
    
42.           if (Search(n - 1, r))
    
43.             return 1;
    
44.           expression[i] = "(" + expa + "-" + expb + ")";
    
45.           number[i] = b - a;
    
46.           if (Search(n - 1, r))
    
47.             return 1;
    
48.           expression[i] = "(" + expa + "*" + expb + ")";
    
49.           number[i] = a * b;
    
50.           if (Search(n - 1, r))
    
51.             return 1;
    
52.           if (b != 0)
    
53.             {
    
54.               expression[i] = "(" + expa + "/" + expb + ")";
    
55.               number[i] = a / b;
    
56.               if (Search(n - 1, r))
    
57.                 return 1;
    
58.             }
    
59.           if (a != 0)
    
60.             {
    
61.               expression[i] = "(" + expa + "/" + expb + ")";
    
62.               number[i] = b / a;
    
63.               if (Search(n - 1, r))
    
64.                 return 1;
    
65.             }
    
66.           number[i] = a;
    
67.           number[j] = b;
    
68.           expression[i] = expa;
    
69.           expression[j] = expb;
    
70.         }
    
71.     }
    
72.   return 0;
    
73. }
    
74. int main()
    
75. {
    
76.   int i, x;
    
77.   int n, m;
    
78.   cin >> n >> m;
    
79.   for (i = 0; i < n; i++)
    
80.     {
    
81.       cin >> x;
    
82.       number[i] = x;
    
83.       expression[i] = to_string(x);
    
84.     }
    
85.   if (!Search(n, m))
    
86.     cout << "No" << endl;
    
87. }
    
88. 
    

复制代码

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

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千亿

这肯定不行啊