来源:Python与数据分析链接:
小外甥女的课后作业是算24点,看了一下题目,发现都挺难的,像下面这些:
7 7 3 3
8 8 3 3
5 5 5 1
1 5 7 10
2 5 5 10
只能用加减乘除,算出24点。
发现心算不容易,于是突发奇想,用Python写了一个程序来算。
基本思路
枚举4个数字可以组成的所有的算式,找到其中等于24的式子。
对于每一个算式,我们用一棵二叉树来存取。根节点保存运算符(+,-,*,/),左子树保存运算符左侧的子算式,右子树保存运算符右侧的子算式,运算结果也存在根节点中。如下图
这棵二叉树对应的算式就是 (4 + 10) + (2 * 5) 。非常简单直观。
有了二叉树后,对于给定的一组数字,我们就可以递归地列出这组数字组成的所有可能的算式。
具体实现
首先定义二叉树。对于树中的每一个节点,我们用一个Node类来保存
Node类中,如果 _operator 是None,则 _result 就是数字本身,如果 _operator 不为None,则 _result 表示的是左右两棵子树运算的结果。
对于一组给定顺序的数字,我们用递归的方式获取所有可能的算式
上面函数的输入是一组数字,第一层for循环中将这组数字,拆成左右两部分,分别对应左右两棵子树的部分,输出的 treelist 是所有可能的算式。
对于给定的左子树和右子树,build_tree 函数用加减乘除把它们连接在一起,组成新的二叉树。build_tree 函数如下
build_tree 中会枚举所有的运算方式,组成新的二叉树并返回所有可能的组合。
这里需要注意的是,如果运算方式是除法,除数也就是右侧子算式的结果不能为0。
罗列出所有的算式后,我们就来找一找有没有算式的结果是24。
以上就实现了我们的算法。
测试
下面是令人兴奋的时刻。我们用文章开始的几个例子来测一下我们的算法。
运行结果如下
哈哈,都用到了小数运算,怪不得心算这么难呢~ 是不是很有趣?
算法中有一些重复的计算,有关于优化算法的建议,欢迎留言~
完整代码
(完)
看完本文有收获?请转发分享给更多人
关注「Python那些事」,做全栈开发工程师
领取专属 10元无门槛券
私享最新 技术干货