用Python玩转经典24点游戏
一,概述
算24点:任意给定四个整数,用加、减、乘、除以及适当的括号连接,无论顺序,使计算结果为24,也可能根本就无解。如何用程序简单实现找到算式是程序初学者关注的问题,百度上可以搜到许多这样的文章,有递归法、回溯法、穷举法。但穷举法最为简单、易于理解。
二,算法
穷举法就是把四个数字的所有运算式进行尝试计算,要设法把所有排列一点不差地穷举出,
一、是四个整数位置的排列,用0,1,2,3表示位置,排列是不能重复的,所以有P(4,4)种情况,即4!=4*3*2*1=24种;
二、是三个运算符的变化,每个运算符为+-*/ ,可以相同,所以,有4*4*4=64种;
三、三个运算符的优先级,就是括号位置的变化,可能性为P(3,3)-1=6-1=5种;
所以,表达式的可能性为:24*64*5=7680种
首先,对第一点进行说明,当用户输入的数值穿在重复值时,实际的有效数值组合是少于24的,如输入为6\6\6\6(即四个数值相同)则对于这种情况,只有一种数值组合顺序;如输入为6\6\6\1(即三个数值相同),则对于这种情况,只有4种数值组合顺序,...在python的语法体系中,set()函数可以很方便的排除重复项,因此,可以先采用穷举法给出所有的数值顺序可能,再用set()函数排除重复项,而在本文中,设置的程序数据格式为集合类型
其次,针对第三点,运算符有优先级,一般是用括号表示。我们可以规定运算符的优先级来代替括号。设四个数字为a、b、c、d,运算符为①、②、③,表达式为a ① b ② c ③ d。 这3个运算符的运算顺序有3!=6种,分别是:
1.①②③ 2.①③② 3.②①③ 4.②③① 5.③①② 6.③②①
等价的表达式分别是:
1.((a①b②)c③)d 2.(a①b)②(c③d) 3.(a①(b②c))③d
4.a①((b②c)③d) 5.(a①b)②(c③d) 6. a①(b②(c③d))
显然,2和5是相同的,因此只考虑5种情况。这样,括号的问题就解决了。
另外,为了用户体验和程序的稳定性,采用了用户输入数据有效性核查机制和程序倒计时退出机制
程序代码
参考代码如下(基于python3.x)
#二十四点
import os
from time import sleep
from time import perf_counter
global Goal,MaxAllowRetryNum,Count
Goal,MaxAllowRetryNum,Count=24,3,0
#输出程序相关信息
def ptintInfo():
print('''" 经典 24 点 "'''.center(72,"="))
print(" 请用户输入四个正整数值 ".center(64,"-"))
print(" 单个数值提供三试错机会。若机会用完,程序倒计时5秒退出 ".center(50, "-"))
print(" 将输出所有的24点方案,并对方案进行计数 ".center(58,"-"))
print(" 若无方案,程序退出,输出0 ".center(65, "-"))
def printSatistics(times):
print("一共有{}种方案".format(Count))
print("共耗时{:.3f}ms".format(times*1000))
#得到四个用户输入值
def getNumbers():
a=getOneNumber("一")
b=getOneNumber("二")
c=getOneNumber("三")
d=getOneNumber("四")
print("输入的数值为:"+a+','+b+','+c+','+d)
return a+' '+b+' '+c+' '+d
#得到单个用户输入值
#单个提供三次试错机会,(不包括第一次输入)
#试错机会用完后,程序倒计时五秒强制退出
def getOneNumber(temp):
global MaxAllowRetryNum
for tryies in range(MaxAllowRetryNum+1):
num=input("请输入第{}个值:".format(temp))
try:
num=int(eval(num))
if num > 0:
break
else:
print("请核对输入信息,还剩余{}次机会".format(MaxAllowRetryNum-tryies))
except:
print("请核对输入信息,还剩余{}次机会".format(MaxAllowRetryNum-tryies))
if tryies == MaxAllowRetryNum:
for i in range(5):
print("\r所有次数已用完,程序将在{}秒后退出".format(5-i))
sleep(1)
print("\n")
os._exit(0)
return str(num)
#穷举所有的数值列表
#共4!=24种
def getNumList(numbers):
items=numbers.split()
#四重循环遍历穷举所有的数值组合
#data_list = []
# for i in range(4):
# for j in range(4):
# if i!=j:
# for p in range(4):
# if p!=i and p!=j:
# for q in range(4):
# if q!=i and q!=j and q!=p:
# data_list.append(items[i]+' '+items[j]+' '+items[p]+' '+items[q])
data_list = [(items[i]+' '+items[j]+' '+items[p]+' '+items[q]) for i in range(4) for j in range(4) for p in range(4) for q in range(4) if (i != j) &(i != p) &(i != q) &(j != p) &(j != q) &(p != q)]
#使用set方法排除冗余的数字组合
#当输入的数字中存在重复数字,则4!=24种排序方案会存在重复,必须排除
return set(data_list)
#穷举所有的操作符列表
#共4x4x4=64种
def getOplist(ops):
# op_list_orgin=ops
# op_list=[]
#三重循环遍历穷举
# for i in range(4):
# for j in range(4):
# for p in range(4):
# item=str(op_list_orgin[i])+' '+str(op_list_orgin[j])+' '+str(op_list_orgin[p])
# op_list.append(item)
op_list=[ops[i]+' '+ops[j]+' '+ops[p] for i in range(4) for j in range(4) for p in range(4)]
return op_list
#计算24点
def Cal(num_list,opt_list):
for numlist in num_list:
nums=numlist.split()
for oplist in opt_list:
ops=oplist.split()
Cal24(nums,ops)
#对单种运算符顺序和单种数字顺序进行组合运算
def Cal24(nums,op):
global Goal,Count
#第一种情况 ((num0 op0 num1)op1 num2)op2 num3
try:
if round(eval("(("+nums[0]+op[0]+nums[1]+")"+op[1]+nums[2]+")"+op[2]+nums[3]),5) == Goal:
Count+=1
print("(({}{}{}){}{}){}{}={}".format(\
nums[0], op[0], nums[1], op[1], nums[2], op[2], nums[3], Goal))
except:
pass
#第二种情况 (num0 op0 num1) op1 (num2 op2 num3)
try:
if round(eval("("+nums[0]+op[0]+nums[1]+")"+op[1]+"("+nums[2]+op[2]+nums[3]+")"), 5) == Goal:
Count += 1
print("({}{}{}){}({}{}{})={}".format(\
nums[0], op[0], nums[1], op[1], nums[2], op[2], nums[3], Goal))
except:
pass
#第三种情况 ( num0 op0 ( num1 op1 num2 )) op2 num3
try:
if round(eval("("+nums[0]+op[0]+"("+nums[1]+op[1]+nums[2]+"))"+op[2]+nums[3]), 5) == Goal:
Count += 1
print("({}{}({}{}{})){}{}={}".format(\
nums[0], op[0], nums[1], op[1], nums[2], op[2], nums[3], Goal))
except:
pass
#第四种情况 num0 op0 (( num1 op1 num2 ) op2 num3 )
try:
if round(eval(nums[0]+op[0]+"(("+nums[1]+op[1]+nums[2]+")"+op[2]+nums[3]+")"), 5) == Goal:
Count += 1
print("{}{}(({}{}{}){}{})={}".format(\
nums[0], op[0], nums[1], op[1], nums[2], op[2], nums[3], Goal))
except:
pass
#第五种情况 num0 op0 ( num1 op1 ( num2 op2 num3 ))
try:
if round(eval(nums[0]+op[0]+"("+nums[1]+op[1]+"("+nums[2]+op[2]+nums[3]+"))"), 5) == Goal:
Count += 1
print("{}{}({}{}({}{}{}))={}".format(\
nums[0], op[0], nums[1], op[1], nums[2], op[2], nums[3], Goal))
except:
pass
if __name__ == '__main__':
ptintInfo()
numbers=getNumbers()
start=perf_counter()
num_list=getNumList(numbers)
opt_list=getOplist('+-*/')
Cal(num_list,opt_list)
printSatistics(perf_counter()-start)
当输入为5\6\7\8,输出截图为:
上一篇: 如何编写一个计算24点的程序?
推荐阅读