HJ67 24点游戏算法

本节目标：理解“HJ67 24点游戏算法”的核心思路，并能把它用于实际开发或面试表达。 中等 通过率：33.13% 时间限制：1秒 空间限制：32M 知识点==dfs====搜索== 描述 给出4个1-10的数字，通过加减乘除运算，得到数字为24就算胜利,除法指实数除法运算,运算符仅允许出现在两个数字之间,本题对数字选取顺序无要求，但每个数字仅允许使用一次，且需考虑括号运算

此题允许数字重复，如3 3 4 4为合法输入，此输入一共有两个3，但是每个数字只允许使用一次，则运算过程中两个3都被选取并进行对应的计算操作。 输入描述： 读入4个[1,10]的整数，数字允许重复，测试用例保证无异常数字。 输出描述： 对于每组案例，输出一行表示能否得到24点，能输出true，不能输出false 示例1 输入： 7 2 1 10 ==复制== 输出： true

解决这个问题的方法之一是使用深度优先搜索（DFS）。思路是尝试所有可能的数字组合和所有可能的运算符组合，检查是否能得到24。这里是具体的步骤：

1. 选择操作数：从剩下的数字中选择两个数字，有 $\frac{n(n-1)}{2}$ 种选择方法（$n$是当前剩余的数字数量）。
2. 选择运算符：对于每一对选择的数字，尝试所有四种运算（加、减、乘、除）。注意，减法和除法是不对称的，所以每种操作都有两种不同的顺序（比如$a-b$和$b-a$）。
3. 递归：每次操作后，将操作结果加入到数字集合中，并从集合中移除被操作的两个数字，然后递归地进行下一步搜索。
4. 终止条件：当数字集合中只剩下一个数字时，检查这个数字是否为24（或在某个很小的误差范围内，考虑到浮点数的精度问题）。

以下是基于这个思路的Python代码实现： def solve(nums): if len(nums) == 1:

考虑到浮点数的精度问题，这里使用一个小的误差范围来判断是否等于24

return abs(nums[0] - 24) < 1e-6

尝试所有可能的数字组合

for i in range(len(nums)): for j in range(len(nums)): if i != j:

对于每一对数字，尝试所有可能的运算

next_nums = [nums[k] for k in range(len(nums)) if i != k != j] a, b = nums[i], nums[j] candidates = set([a+b, a-b, b-a, a*b]) if b: candidates.add(a / b) if a: candidates.add(b / a) for n in candidates: if solve(next_nums + [n]): return True return False

输入四个数字

nums = list(map(int, input().split()))

输出是否可以通过运算得到24

print('true' if solve(nums) else 'false')

这段代码首先定义了一个递归函数solve，用于检查给定的数字列表是否能通过运算得到24。对于每一对数字，它尝试所有可能的运算，并递归地检查剩余数字加上运算结果是否能得到24。当数字列表只剩下一个数字时，它检查这个数字是否为24，以确定是否找到了解决方案。最后，根据solve函数的返回值输出结果。