24点
* * * *
拉格朗日计划
* * * *
24点

24点是一种用扑克牌进行的算术游戏。

去掉大小王,在其余52张牌中取出4张(J,Q,K分别表示11,12,13),选择这四个数的一种排列顺序,随后在这4个数之间添加括号和四则运算加减乘除的符号,使得结果为24。

不是所有的组合都能算出24,按升序(数字也要按升序排列)打印出所有能算出24的组合。

注意计算的中间结果不一定需要是整数,例如$6/(1-3/4)=24$是有效的计算。

本题难度:



解答

比较繁琐的问题,由于有5秒的运行限制,直接暴力穷举会超时,需要合理剪枝。

先按升序生成所有数字和组合,对每个组合形成的序列,作递归计算:

取出两个数字a,b,分别计算$a+b, a\times b, a-b, b-a, a\div b, b\div a$这六种情况(除法还需排除除数为0的情况)的结果,并放回序列作递归,直到序列长度为1,就检验其是否为24。

枚举所有的取法和计算结果即可。

最终代码行有13行。

代码长度:386字节 vs. 全站第一:166字节。

from itertools import*
e=range
def f(x):
  k=len(x)
  r=e(k)
  if k==1:return abs(x[0]-24)<0.01
  for c in combinations(r,2):
  a,b=[x[i]for i in r if i in c]
  y,z=[x[i]for i in r if i not in c],[[a+b],[a*b],[a-b],[b-a]]
  if a:z+=[[b/a]]
  if b:z+=[[a/b]]
  if any(f(d+y)for d in z):return 1
[f([u,v,w,r])and print(u,v,w,r)for u in e(1,14)for v in e(u,14)for w in e(v,14)for r in e(w,14)]