python经典趣味24点游戏程序设计
一、游戏玩法介绍:
24点游戏是儿时玩的主要益智类游戏之一,玩法为:从一副扑克中抽取4张牌,对4张牌使用加减乘除中的任何方法,使计算结果为24。例如,2,3,4,6,通过( ( ( 4 + 6 ) - 2 ) * 3 ) = 24,最快算出24者剩。
二、设计思路:
由于设计到了表达式,很自然的想到了是否可以使用表达式树来设计程序。本程序的确使用了表达式树,也是程序最关键的环节。简要概括为:先列出所有表达式的可能性,然后运用表达式树计算表达式的值。程序中大量的运用了递归,各个递归式不是很复杂,大家耐心看看,应该是能看懂的
表达式树:
表达式树的所有叶子节点均为操作数(operand),其他节点为运算符(operator)。由于本例中都是二元运算,所以表达式树是二叉树。下图就是一个表达式树
具体步骤:
1、遍历所有表达式的可能情况
遍历分为两部分,一部分遍历出操作数的所有可能,然后是运算符的所有可能。全排列的计算采用了递归的思想
?
1 2 3 4 5 6 7 8 9 10
|
#返回一个列表的全排列的列表集合 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个非叶子节点。所以树的形状只有两种可能,就直接写死了
?
1 2 3 4 5 6 7
|
#树节点 class Node: def __init__( self , val): self .val = val self .left = None self .right = None |
?
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
|
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、计算表达式树的值
也运用了递归
?
1 2 3 4 5 6 7 8
|
#根据两个数和一个符号,计算值 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、输出所有可能的表达式
还是运用了递归
?
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
|
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、输出结果
三、所有源码
?
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94
|
#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 ]) |
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持脚本之家。
赞 (0)