这篇文章主要介绍python如何实现24点游戏程序,文中介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们一定要看完!
一、游戏玩法介绍:
24点游戏是儿时玩的主要益智类游戏之一,玩法为:从一副扑克中抽取4张牌,对4张牌使用加减乘除中的任何方法,使计算结果为24。例如,2,3,4,6,通过( ( ( 4 + 6 ) - 2 ) * 3 ) = 24,最快算出24者剩。
二、设计思路:
由于设计到了表达式,很自然的想到了是否可以使用表达式树来设计程序。本程序的确使用了表达式树,也是程序最关键的环节。简要概括为:先列出所有表达式的可能性,然后运用表达式树计算表达式的值。程序中大量的运用了递归,各个递归式不是很复杂,大家耐心看看,应该是能看懂的
表达式树:
表达式树的所有叶子节点均为操作数(operand),其他节点为运算符(operator)。由于本例中都是二元运算,所以表达式树是二叉树。下图就是一个表达式树
具体步骤:
1、遍历所有表达式的可能情况
遍历分为两部分,一部分遍历出操作数的所有可能,然后是运算符的所有可能。全排列的计算采用了递归的思想
#返回一个列表的全排列的列表集合 def list_result(l): if len(l) == 1: return [l] all_result = [] for index,item in enumerate(l): r = list_result(l[0:index] + l[index+1:]) map(lambda x : x.append(item),r) all_result.extend(r) return all_result
2、根据传入的表达式的值,构造表达式树
由于表达式树的特点,所有操作数均为叶子节点,操作符为非叶子节点,而一个表达式(例如( ( ( 6 + 4 ) - 2 ) * 3 ) = 24) 只有3个运算符,即一颗表达式树只有3个非叶子节点。所以树的形状只有两种可能,就直接写死了
#树节点 class Node: def __init__(self, val): self.val = val self.left = None self.right = None
def one_expression_tree(operators, operands): root_node = Node(operators[0]) operator1 = Node(operators[1]) operator2 = Node(operators[2]) operand0 = Node(operands[0]) operand1 = Node(operands[1]) operand2 = Node(operands[2]) operand3 = Node(operands[3]) root_node.left = operator1 root_node.right =operand0 operator1.left = operator2 operator1.right = operand1 operator2.left = operand2 operator2.right = operand3 return root_node def two_expression_tree(operators, operands): root_node = Node(operators[0]) operator1 = Node(operators[1]) operator2 = Node(operators[2]) operand0 = Node(operands[0]) operand1 = Node(operands[1]) operand2 = Node(operands[2]) operand3 = Node(operands[3]) root_node.left = operator1 root_node.right =operator2 operator1.left = operand0 operator1.right = operand1 operator2.left = operand2 operator2.right = operand3 return root_node
3、计算表达式树的值
也运用了递归
#根据两个数和一个符号,计算值 def cal(a, b, operator): return operator == '+' and float(a) + float(b) or operator == '-' and float(a) - float(b) or operator == '*' and float(a) * float(b) or operator == '÷' and float(a)/float(b) def cal_tree(node): if node.left is None: return node.val return cal(cal_tree(node.left), cal_tree(node.right), node.val)
4、输出所有可能的表达式
还是运用了递归
def print_expression_tree(root): print_node(root) print ' = 24' def print_node(node): if node is None : return if node.left is None and node.right is None: print node.val, else: print '(', print_node(node.left) print node.val, print_node(node.right) print ')', #print ' ( %s %s %s ) ' % (print_node(node.left), node.val, print_node(node.right)),
5、输出结果
三、所有源码
#coding:utf-8 from __future__ import division from Node import Node def calculate(nums): nums_possible = list_result(nums) operators_possible = list_result(['+','-','*','÷']) goods_noods = [] for nums in nums_possible: for op in operators_possible: node = one_expression_tree(op, nums) if cal_tree(node) == 24: goods_noods.append(node) node = two_expression_tree(op, nums) if cal_tree(node) == 24: goods_noods.append(node) map(lambda node: print_expression_tree(node), goods_noods) def cal_tree(node): if node.left is None: return node.val return cal(cal_tree(node.left), cal_tree(node.right), node.val) #根据两个数和一个符号,计算值 def cal(a, b, operator): return operator == '+' and float(a) + float(b) or operator == '-' and float(a) - float(b) or operator == '*' and float(a) * float(b) or operator == '÷' and float(a)/float(b) def one_expression_tree(operators, operands): root_node = Node(operators[0]) operator1 = Node(operators[1]) operator2 = Node(operators[2]) operand0 = Node(operands[0]) operand1 = Node(operands[1]) operand2 = Node(operands[2]) operand3 = Node(operands[3]) root_node.left = operator1 root_node.right =operand0 operator1.left = operator2 operator1.right = operand1 operator2.left = operand2 operator2.right = operand3 return root_node def two_expression_tree(operators, operands): root_node = Node(operators[0]) operator1 = Node(operators[1]) operator2 = Node(operators[2]) operand0 = Node(operands[0]) operand1 = Node(operands[1]) operand2 = Node(operands[2]) operand3 = Node(operands[3]) root_node.left = operator1 root_node.right =operator2 operator1.left = operand0 operator1.right = operand1 operator2.left = operand2 operator2.right = operand3 return root_node #返回一个列表的全排列的列表集合 def list_result(l): if len(l) == 1: return [l] all_result = [] for index,item in enumerate(l): r = list_result(l[0:index] + l[index+1:]) map(lambda x : x.append(item),r) all_result.extend(r) return all_result def print_expression_tree(root): print_node(root) print ' = 24' def print_node(node): if node is None : return if node.left is None and node.right is None: print node.val, else: print '(', print_node(node.left) print node.val, print_node(node.right) print ')', if __name__ == '__main__': calculate([2,3,4,6])
以上是“python如何实现24点游戏程序”这篇文章的所有内容,感谢各位的阅读!希望分享的内容对大家有帮助,更多相关知识,欢迎关注亿速云行业资讯频道!
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。