456主机测评
24点扑克游戏详细解析附代码
题目要求：
52张牌里面选4张，可以重复，任意使用±/*和括号，使得最后运算结果为24.
多少种排列组合：
有131313*13种排列，但是这些排列的牌会有重复的，比如（1，1，2，3）和（1，3，2，1）就算是重复，把不重复的叫做一个组合，那么实际上有1820种组合。
成功的组合：
这1820种组合里面有1362种组合是成功解的。
成功的概率：
但是因为每个组合出现的概率不一样，不能使用1362/1820来做成功概率。比如组合123包含排列123，132，213，231，312，321.而组合221只包含排列122，212，221.所以最后的成功概率是要加权计算的，最后的成功概率为80.0%左右
优化求概率算法：
实际上，推广到广义更多牌（非4张），更多点数（非13点），可能使用完全逐一验证排列的算法会很耗时。例如变形为从无数副扑克里面挑10张牌出来算24点，复杂度变为13的10次方，如果使用逐一验证每个排列是否有解，会很耗性能。另外一种思路是随机抽样调查，随机产生适当数量的排列，验证是否有解，然后统计概率。
代码：
本算法的get_math_probability是逐个验证解，get_sim_probability是模拟统计解，对于一种组合，使用遍历换位，括号，运算符的方式来生成表达式。使用eval函数来计算表达式。
算法的坑：
对于（3，3，8，8）组合，有解"8/（3-8/3）"=24，但是如果直接计算会得到23.99999999999.所以解决方案是把eval(expr)==24改为abs(eval(expr)-24)<0.000001。限制精确度范围。
为什么是24：
因为24有1，2，3，4，6，8，12，24。总共8乘法个因子，并且24/4=6，6这个数字在[1，13]点里面是中间位置。所以24无论是乘除法，还是加减法都比较容易拼凑，使用其它数字会降低成功概率。
源代码：
import itertools as it import random def get_tu_res(tu): ''' :param tu: 整数元组 :return: 能成功做出24点的字符串的集合 ''' situation = it.permutations(tu, 4) res=set() for si in situation: a,b,c,d=si for o1 in "+-*/": for o2 in "+-*/": for o3 in "+-*/": e1=f"(({a}{o1}{b}){o2}{c}){o3}{d}" e2= f"({a}{o1}{b}){o2}({c}{o3}{d})" e3= f"({a}{o1}({b}{o2}{c})){o3}{d}" e4 = f"{a}{o1}(({b}{o2}{c}){o3}{d})" e5 = f"{a}{o1}({b}{o2}({c}{o3}{d}))" for expr in (e1,e2,e3,e4,e5): try: t=eval(expr) except: continue if t==24: res.add(expr) return res def is_ok_tu(tu): ''' 性能提高在如果找到第一个解的时候就跳出了，节省计算 :param tu: 整数元组 :return: 布尔值，能否运算成24点 ''' situation = it.permutations(tu, 4) for si in situation: a, b, c, d = si for o1 in "+-*/": for o2 in "+-*/": for o3 in "+-*/": e1 = f"(({a}{o1}{b}){o2}{c}){o3}{d}" e2 = f"({a}{o1}{b}){o2}({c}{o3}{d})" e3 = f"({a}{o1}({b}{o2}{c})){o3}{d}" e4 = f"{a}{o1}(({b}{o2}{c}){o3}{d})" e5 = f"{a}{o1}({b}{o2}({c}{o3}{d}))" for expr in (e1, e2, e3, e4, e5): try: t = eval(expr) except: continue if abs(t-24)<0.00000001: return True return False def get_defeat_com(): all_com=get_all_com() defeat_com = set() for tu in all_com: if not is_ok_tu(tu): defeat_com.add(tu) return defeat_com def get_all_com(): com = set() for a in range(1, 14): for b in range(a, 14): for c in range(b, 14): for d in range(c, 14): tu = (a, b, c, d) com.add(tu) return com def get_math_probability(defeat_com): cnt_defeat=0 for a in range(1,14): for b in range(1,14): for c in range(1,14): for d in range(1,14): arr=[a,b,c,d] arr.sort() tu=tuple(arr) if tu in defeat_com: cnt_defeat+=1 probability=1-(cnt_defeat/28561) return probability def get_sim_probability(defeat_com): times=1000 cnt_defeat=0 for t in range(times): arr=[random.randint(1,13),random.randint(1,13),random.randint(1,13),random.randint(1,13)] arr.sort() tu=tuple(arr) if tu in defeat_com: cnt_defeat+=1 return (times-cnt_defeat)/times defeat_com=get_defeat_com() print(get_math_probability(defeat_com)) print(get_sim_probability(defeat_com)) - 海报
