谁有“二十四点”游戏的解题方法
- 提问者网友:皆是孤独
- 2021-04-29 12:59
- 五星知识达人网友:孤老序
- 2021-04-29 13:29
第一种思路:
把多元运算转化为两元运算,先从四个数中取出两个数进行运算,然后把运算结果和第三个数进行运算,再把结果与第四个数进行运算。在求表达式的过程中,最难处理的就是对括号的处理,而这种思路很好的避免了对括号的处理。基于这种思路有两种算法:
第一种算法:
(1) 将4个整数放入数组中,
(2) 在数组中取两个数字的排列,共有 P(4,2) 种排列。对每一个排列,
(2.1) 对 + - * / 每一个运算符,
(2.1.1) 根据此排列的两个数字和运算符,计算结果,
(2.1.2) 改表数组:将此排列的两个数字从数组中去除掉,将 2.1.1 计算的结果放入数组中,
(2.1.3) 对新的数组,重复步骤 2,
(2.1.4) 恢复数组:将此排列的两个数字加入数组中,将 2.1.1 计算的结果从数组中去除掉。
可以看出,步骤2是一个递归函数。当数组中只剩下一个数字的时候,这就是表达式的最终结果,此时递归结束
第二种算法(此算法思想参考了CSDN(penguinMII)--企鹅的算法思想):
可以寻找所有表达式的规律,得出如下结论:把表达式看成一个函数F(A,B,C,D)=24,可分两种情况F=(((A,B),C),D)和F=((A,B),(C,D)),对其分别计算即可得到答案,算法过程如下:
1)先对第一个数和第二个数进行计算,并保存结果和表达式;
2)对上述结果与第三个数进行计算,并保存结果和表达式;
3)对上述结果与第四个个数进行计算,并保存结果和表达式;
4)判断结果,并输出结果;
5)对第三个数和第四个数进行计算,并保存结果和表达式;
6)对第一个数与第二个数的结果和第三个数与第四个数的结果进行计算,并保存结果和表达式;
7)判断结果,并输出结果;
在这种算法中需要对所有数据进行排列组合,对所有组合进行上述运算过程
第二种思路:
还是尽量避免处理括号,实在是很麻烦。有一种没有括号的表达式——逆波兰表达式(后缀表达式),逆波兰表达式严格地按照从左至右的顺序执行。因此,只需把所有的数字的排列组合与所有的符号的排列组合再进行排列组合即可遍历所有可能的表达式。在输出结果时,只需把逆波兰表达式按照规则还原成正常的表达式即可
说明:'-'和'/'有两种情况,'a-b'用'a-b'表示,'b-a'用'a|b'表示,'a/b'用'a/b'表示,'b/a'用'a\b'表示,'\'是转义字符,要用'\\'表示