快捷導(dǎo)航

python經(jīng)典趣味24點(diǎn)游戲程序設(shè)計(jì)

更新時(shí)間：2019年07月26日 14:19:59 作者：轉(zhuǎn)瞬之夏

這篇文章主要介紹了python經(jīng)典趣味24點(diǎn)游戲程序設(shè)計(jì)，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧

一、游戲玩法介紹：

24點(diǎn)游戲是兒時(shí)玩的主要益智類游戲之一，玩法為：從一副撲克中抽取4張牌，對(duì)4張牌使用加減乘除中的任何方法，使計(jì)算結(jié)果為24。例如，2,3,4,6，通過( ( ( 4 + 6 ) - 2 ) * 3 ) = 24，最快算出24者剩。

二、設(shè)計(jì)思路：

由于設(shè)計(jì)到了表達(dá)式，很自然的想到了是否可以使用表達(dá)式樹來設(shè)計(jì)程序。本程序的確使用了表達(dá)式樹，也是程序最關(guān)鍵的環(huán)節(jié)。簡(jiǎn)要概括為：先列出所有表達(dá)式的可能性，然后運(yùn)用表達(dá)式樹計(jì)算表達(dá)式的值。程序中大量的運(yùn)用了遞歸，各個(gè)遞歸式不是很復(fù)雜，大家耐心看看，應(yīng)該是能看懂的

表達(dá)式樹：

表達(dá)式樹的所有葉子節(jié)點(diǎn)均為操作數(shù)(operand)，其他節(jié)點(diǎn)為運(yùn)算符(operator)。由于本例中都是二元運(yùn)算，所以表達(dá)式樹是二叉樹。下圖就是一個(gè)表達(dá)式樹

具體步驟：

1、遍歷所有表達(dá)式的可能情況

遍歷分為兩部分，一部分遍歷出操作數(shù)的所有可能，然后是運(yùn)算符的所有可能。全排列的計(jì)算采用了遞歸的思想

#返回一個(gè)列表的全排列的列表集合
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、根據(jù)傳入的表達(dá)式的值，構(gòu)造表達(dá)式樹

由于表達(dá)式樹的特點(diǎn)，所有操作數(shù)均為葉子節(jié)點(diǎn)，操作符為非葉子節(jié)點(diǎn)，而一個(gè)表達(dá)式(例如( ( ( 6 + 4 ) - 2 ) * 3 ) = 24) 只有3個(gè)運(yùn)算符，即一顆表達(dá)式樹只有3個(gè)非葉子節(jié)點(diǎn)。所以樹的形狀只有兩種可能，就直接寫死了

#樹節(jié)點(diǎn)
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、計(jì)算表達(dá)式樹的值

也運(yùn)用了遞歸

#根據(jù)兩個(gè)數(shù)和一個(gè)符號(hào)，計(jì)算值
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、輸出所有可能的表達(dá)式

還是運(yùn)用了遞歸

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、輸出結(jié)果

三、所有源碼

#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)


#根據(jù)兩個(gè)數(shù)和一個(gè)符號(hào)，計(jì)算值
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

#返回一個(gè)列表的全排列的列表集合
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])

以上就是本文的全部內(nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章: