python 实现经典24点_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，输出截图为：