E18223: 24点

brute force, http://cs101.openjudge.cn/pctbook/E18223/

给定4个整数，判断是否能只用加减运算（即在4个数中间插入3个+或-符号，可以调换数字顺序），使得运算结果为24。

输入

第一行1个整数，代表m组数据（1≤m≤100）接下来m行，每行为4个整数， Xi (1≤Xi≤10^100)，注意整数可能很大。

输出

共m行，每行为YES或者NO，代表是否能凑成24点。对于如下输入，6+6+6+6=24,25-3+1+1=24，100000000000000000000000-100000000000000000000000-100000000000000000000000+100000000000000000000024=24

样例输入

4
6 6 6 6
3 25 1 1
100000000000000000000000 100000000000000000000000 100000000000000000000000 100000000000000000000024
2 3 4 5

样例输出

YES
YES
YES
NO

来源：cs101-2018

直接穷举

python

m = int(input())

for i in range(m):
	a,b,c,d = [int(num) for num in input().split()]
	flag = False
	for j in [a, -a]:
		for k in [b, -b]:
			for l in [c, -c]:
				for m in [d, -d]:
					if j + k + l + m == 24:
						flag = True
	print('YES' if flag else 'NO')

example: permutations(range(3), 2) --> (0,1), (0,2), (1,0), (1,2), (2,0), (2,1)

python

from itertools import permutations

m = int(input())
mx = [input().split() for _ in range(m)]

def v(i):
    a,b,c,d = i
    l2 = list(permutations([a,b,c,d], 4))
    for j in l2:
        a,b,c,d = j
        for u in ('+','-'):
            for j in ('+','-'):
                for k in ('+', '-'):
                    if eval(a+u+b+j+c+k+d)==24:
                        return 'YES'
    return 'NO'

for i in mx:    
    print(v(i))

2021fall-cs101，黄湘榆，http://cs101.openjudge.cn/practice/18223/

因为不想穷举公式，觉得穷举加减符号应该会比较简洁，所以从网上找到了operator.add和operator.sub。基本思路就是把加减符号的各种排列方式列出来储存在一个字典里，之后再用循环把字典里的每个符号组合都过一遍。之前一直WA是因为for o in output之前的else缩进错误，日后要多注意。

python

import operator
m =int(input())
op = ["+++", "---", "++-", "+-+", "-++", "+--", "-+-", "--+"]
op_dict ={"+": operator.add, "-": operator.sub}

output = []
for i in range(m):
    a,b,c,d = [int(a) for a in input().split()]
    for o in op:
        if abs( op_dict[o[2]](op_dict[o[1]](op_dict[o[0]](a,b), c), d))==24:
            output.append("YES")
            break
    else:
        output.append("NO")

print('\n'.join(output))

2021fall-cs101，留美琪

调用permutation进行排列组合，同时使用set是防止数字相同时，出现排列相同情况，重复计算。运算符考虑以下4中：['+++', '++-', '+--', '---']，但是看老师录课的时候，发现枚举了8种情况，但个人感觉以上4种足够了。运算符号的主要区别在于"-"号的个数，因为数字的顺序在改变，以1,2,3,4和"++-"与"+-+"为例，1+2+3-4 =1+2-4+3，因此上述4种应该是囊括了所有情况的。（后来看到微信群里有人仅对运算符号进行排列组合，所以数字和运算符号仅需对其中一种进行组合就可以了）。

python

# 2021fall-cs101，留美琪
import itertools
m = int(input())
for _ in range(m):
    a, b, c, d = map(int, input().split())
    res = a + b + c + d
    data = set(itertools.permutations([a,b,c,d],4))
    
    for i in data:
        res1 = i[0] + i[1] + i[2] - i[3]
        res2 = i[0] + i[1] - i[2] - i[3]
        res3 = i[0] - i[1] - i[2] - i[3]
        if res==24 or res1 == 24 or res2 == 24 or res3==24:
            print('YES')
            break
    else:
        print('NO')

四个数通过加减运算等价于为每个数分配正负号后求和，其符号组合共 2^4=16 种，构成全部解空间。本方法采用蒙特卡洛随机采样策略，进行 256 次随机试验，检查目标值 24 是否在结果中出现，以此近似判断解的存在性。

python

import random

# 读取测试组数
num_tests = int(input())

for _ in range(num_tests):
    # 读取四个整数
    numbers = list(map(int, input().split()))
    
    # 构建每个数的正负选项 [[a, -a], [b, -b], [c, -c], [d, -d]]
    pos_neg_options = []
    for num in numbers:
        pos_neg_options.append([num, -num])
    
    # 存储随机模拟的结果
    simulation_results = []
    
    # 进行 256 次随机模拟
    for _ in range(256):
        total = 0
        # 对每个数，随机选择正或负
        for i in range(4):
            total += random.choice(pos_neg_options[i])
        simulation_results.append(total)
    
    # 判断 24 是否在模拟结果中出现
    print('YES' if 24 in simulation_results else 'NO')

E18223: 24点 ​

E18223: 24点