Python秒算24点实现及原理详解
什么是24点
我们先来约定下老王和他媳妇玩的24点规则:给定4个任意数字(0-9),然后通过+,-,*,/,将这4个数字计算出24。
小时候玩的都是这个规则,长大了才有根号,才有各种莫名其妙的高级算法,不好玩了,因为我不会。
可能有人会觉得很简单,但是真的简单吗?
比如:
8,3,3,3
7,3,3,3
你能一眼看出来答案吗?好像真的可以……
大致思路
这样想,将四个数字进行全排列,在他们之间添加运算符号。
运算符我们需要进行排列组合,因为只有四个数字,所以只需要三个运算符,而且算法符可能会重复,比如三个都是+。
再遍历四个数字的全排列,对每一组数字而言,遍历所有组合的操作符。最后将数字和操作符进行拼接运算,就可以得到最终结果了。
演示环境
操作系统:windows10
python版本:python3.7
代码编辑器:pycharm2018.2
使用模块:math,itertools,collections.abc
具体代码
1、首先我们对所有数字进行去全排列,这里我们使用itertools.permutations来帮助我们完成。
iertools.permutations用法演示
fromitertoolsimportpermutations data_list=permutations([1,2,3,4],2) fordataindata_list: print(data)
结果显示
(1,2) (1,3) (1,4) (2,1) (2,3) (2,4) (3,1) (3,2) (3,4) (4,1) (4,2) (4,3)
permutations第一个参数是接收一个课迭代的对象,第二个参数指定每次排列时从课迭代对象中选着几个字符进行排列。也可以不传入第二个参数,那么默认就是可迭代对象的长度。并且返回一个生成器。
所以我们需要对所有数字进行全排列,就可以像下面这样写:
defget_all_data_sequence(data_iter): returnpermutations(data_iter)
2、然后我们需要拿到所有的操作运算符的所有组合方式。这里我们就会使用itertools.product函数了。
itertools.product用法演示
fromitertoolsimportproduct sequence1=product('ABCD','xy') sequence2=product([0,1],repeat=3) forsequenceinsequence1: print(sequence) print('-'*30) forsequenceinsequence2: print(sequence)
结果显示
('A','x') ('A','y') ('B','x') ('B','y') ('C','x') ('C','y') ('D','x') ('D','y') ------------------------------ (0,0,0) (0,0,1) (0,1,0) (0,1,1) (1,0,0) (1,0,1) (1,1,0) (1,1,1)
itertools.product,返回传入所有序列中笛卡尔积的元祖,repeat参数表示传入序列的重复次数。返回的是一个生成器。
那么获取所有的操作运算符就可以通过这个函数来获取了
defget_all_operations_sequence(): operations=['+','-','*','/'] returnproduct(operations,repeat=3)
3、现在我们已经拿到了所有可能组合的操作符和数字了,接下来就需要对他们进行拼接了。然后执行运算。
这一步操作我们会用到itertools.zip_longest()和itertools.chain.form_iterable()函数。
itertools.zip_longest()用法演示
data=zip_longest([1,2,3,4],['*','-','+'],fillvalue='') forvalueindata: print(value)
结果显示
(1,'*') (2,'-') (3,'+') (4,'')
zip_longest()其实和python内置的zip()函数用法差不多,只是zip_longest是以最长的一个序列为基准,缺失值就使用fillvalue参数的值进行填充
itertools.chain.form_iterable()用法演示
data=zip_longest([1,2,3,4],['*','-','+'],fillvalue='') data_chain=chain.from_iterable(data) forvalueindata_chain: print(value)
结果显示
1 * 2 - 3 + 4
这里的data是什么样的大家知道了吧,然后我们将data传入chain.form_iterable()中,它就能将里面的值依次拿出来。
了解了这两个函数之后,那么我们就可以开始拼接数字和操作运算符了。
defcalculate(self): ''' 计算值,返回对应的表达式和值 :return: ''' fordata_sequenceinget_all_data_sequence(): operation_sequences=get_all_operation_sequence() foroperation_sequenceinoperation_sequences: value=zip_longest(data_sequence,operation_sequence, fillvalue='') value_chain=chain.from_iterable(value) calculate_str='' #对得到的字符进行拼接成为表达式calculate_str for_invalue_chain: calculate_str+=_ try: result=eval(calculate_str #处理被除数可能为零的情况,然后就直接跳过这次循环 exceptZeroDivisionError: continue ifmath.isclose(result,24): returncalculate_str,result returnNone,None
代码分析
1、eval()函数,接受一个字符串,能让这个字符串当成python代码运行,返回运行的结果。
2、math.isclose():为什么这里需要使用math.isclose(),而不是直接使用==运算符呢?这是因为最后算出来的表达式可能有精度问题,例如23.9...或者24.0...等数字,所以我们就需要使用math.isclose()函数来帮助我们判断两个数字是否相等了,这个函数就有一个精度范围。这样出现上面情况的时候,我们也能匹配得到条件了。
我们运行代码,然后测试代码是否能达到我们的需求。
首先我们测试1,2,3,4四个数字,
程序出来了结果1*2*3*424
看来好像我们写的代码是正确的
我们再来测试一组数据8,8,3,3.
嗯?我们并没有得到结果?这四个数字不能运算出24吗?
8/(3-8/3)这样组合可以吧,为什么没有算出来这种结果呢?
这是因为我们没有考虑括号的原因。括号是可以改变运算优先级的。所以我们得把括号考虑进去。
那么想一下括号最多可以有几个呢?怎样给我们的表达式添加括号呢?
在4个数字的运算中,括号最多只能有三个。
并且,在这里,我们使用一种简单的方法添加括号,我们把所有可能出现括号的情况全部罗列出来,然后在将得到的运算表达式拼接进去。
可能大家会觉得罗列出所有括号出现的情况不现实,因为有很多情况
其实不然,当我们去罗列的时候,你就会发现,只有11种情况。
FORM_STRS=[ #数字运算符数字运算符数字运算符数字 #一个括号的情况 '(%s%s%s)%s%s%s%s', '(%s%s%s%s%s)%s%s', '(%s%s%s%s%s%s%s)', '%s%s(%s%s%s)%s%s', '%s%s(%s%s%s%s%s)', '%s%s%s%s(%s%s%s)', #两个括号的情况 '(%s%s%s)%s(%s%s%s)', '((%s%s%s)%s%s)%s%s', '(%s%s(%s%s%s))%s%s', '%s%s((%s%s%s)%s%s)', '%s%s(%s%s(%s%s%s))', #三个括号是重复的,就不用罗列出来了 ]
然后我们对得到的表达式在进行遍历拼接,然后我们再运算表达式。
这样我们就能得出正确的结果了
代码写完了,终于可以开始和媳妇,哦不,老王家的媳妇玩起来了
代码已全部上传至Github
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持毛票票。