华为OJ24点问题：穷举法暴力求解
24点运算
http://www.nowcoder.com/questionTerminal/7e124483271e4c979a82eb2956544f9d
思路：
由于四则运算组合的可能性很多，而且不存在子问题模板化适配，所以 递归、分治、动态规划的方式不行，不要遇见难一点的题就条件反射到这些方法上。
本题是必须穷举的，也就是暴力法。
我们先评估下暴力求解时的问题规模：4个数字，3个运算符。由于不允许带括号，而且数字先后顺序不固定，所以对于数字位来说肯定是排序问题，一共4*3*2*1 = 24种排列，
另外对于运算符，每个位置都有4种取值可能，故是4^3 = 64种，所以整体的问题规模是 24*64 = 1536个计算组合。也就是给定4个数字，最极端的情况也就1536次四则运算，这个问题规模2s内完成。
这里用python的eval、笛卡尔积函数product跟生成排序序列的permutation函数，相比cpp/java 缩减代码行数。
运行时间：51ms 占用内存：3680k
import sys
import itertools
def calc_24points(data):
map2={'J':'11','Q':'12','K':'13','A':'1'}
new_data=[]
for d in data:
if d in map2:
new_data.append(map2[d])
else:
new_data.append(d)
map1={'0':'+','1':'-','2':'*','3':'/'}
for o in (''.join(x) for x in itertools.product(map(str,range(4)), repeat=3)):
for i in itertools.permutations(range(4),4):
temp1='(('+new_data[i[0]]+map1[o[0]]+new_data[i[1]]+')'+map1[o[1]]+new_data[i[2]]+')'+map1[o[2]]+new_data[i[3]]
temp2=data[i[0]]+map1[o[0]]+data[i[1]]+map1[o[1]]+data[i[2]]+map1[o[2]]+data[i[3]]
if ('joker' in temp1)&nbs***bsp;('JOKER' in temp1):
print('ERROR')
return
elif eval(temp1)==24:
print(temp2)
return
print('NONE')
for line in sys.stdin:
data = list(map(str, line.strip().split()))
calc_24points(data) 
投递牛客等公司