国庆假天天躺尸,也没啥动力写文章,就把以前写的24点游戏的代码整理一下算了。24点游戏基本每个人都玩过,这里尝试用python给出在n个数情况下,24点游戏所有可能的结果,首先对游戏规则进行说明
任给n个数,通过加减乘除括号运算计算24,给出所有可以得到24的计算方法
有两种思路,一种是从循环的角度出发,n个数,中间可以加n-1个运算符号,对n个数进行排列,对n-1个运算符号分别用加减乘除去尝试,返回可以得到24的运算方式,这种方法想起来感觉很可行,但实际操作的时候就会出现各种问题,尤其是考虑括号的情况下,加不加括号?哪里加括号?加几个括号? 要分类讨论的情况太多,所以放弃了这种方法。
另一个思路是从递归的角度出发,对于n个数,每次我们任意选择两个数字进行加减乘除合并,合并之后就变成了n-1个数字,对于这n-1个数字,再进行合并,直到最后剩下一个数字,如果这个数字恰好是24,表明我们找到了一种可行的计算方式。
与循环相比,这种方法基本不存在需要讨论的特殊情况,每次任意选择两个数,可以视为是对这两个数字加了括号,就避免了循环中怎么加括号的问题。
这里唯一存在的问题是怎么样记录,按照之前说的,实际上每次只记录了最终计算的结果,并没有记录计算过程,每合并一次后,需要对记录的运算方式做相应的改变,这里我用字典进行记录,也有别的方法,看到有用二叉树做的,思想类似。
每次合并后,增加一个键值对,把合并后的值赋给value,key设置为合并方式,然后删除合并前的两个键值对。举个例子,比如说某次合并前的字典为:
如果用加法合并,合并后的字典为
减法乘法类似,除法需要讨论分子是不是0,这里key是字符串的合并,value是值的运算。key合并每次都必须在外面加括号,这样在最终合并成一个值时,才能看出运算的顺序。
为了得到所有可行的结果,最外层需要加一个循环,循环所有对n个数中取两个数的情况。
代码在后台回复“24点”可得,我用的是python3,python2可能会报错。大致说明一下代码,总共两个函数,fun1输入一个数字列表,转化为字典,然后调用fun得到结果的函数
def fun1(nums):
nums0 = dict(zip(map(str,nums),map(float,nums)))
fun(nums0)
print('结束!')
fun为递归进行加减乘除合并的函数,较长,部分代码如下
def fun(nums):
if len(nums) == 1:
# 打印符合条件的计算方式
if list(nums.values())[0] == 24.0:
print(list(nums.keys())[0])
# 长度大于2时,遍历所有的值,对六种情况进行递归
else:
for i in range(len(nums)):
for j in range(i):
# 相加
nums1 = nums.copy()
nums1['(' + str(list(nums.keys())[i]) + '+' + str(list(nums.keys())[j]) + ')'] = list(nums.values())[i] + list(nums.values())[j]
nums1.pop(list(nums.keys())[i])
nums1.pop(list(nums.keys())[j])
fun(nums1)
...
...
...
# 相除(若分母为0,跳过运算)
if list(nums.values())[j]!= 0:
nums1 = nums.copy()
nums1['(' + str(list(nums.keys())[i]) + '/' + str(list(nums.keys())[j]) + ')'] = list(nums.values())[i] / list(nums.values())[j]
nums1.pop(list(nums.keys())[i])
nums1.pop(list(nums.keys())[j])
fun(nums1)
# 换序相减
nums1 = nums.copy()
nums1['(' + str(list(nums.keys())[j]) + '-' + str(list(nums.keys())[i]) + ')'] = list(nums.values())[j] - list(nums.values())[i]
nums1.pop(list(nums.keys())[i])
nums1.pop(list(nums.keys())[j])
fun(nums1)
以1,2,3,4,5为例结果如下
最后说明一下代码中存在的一些问题