数字组合得到24
缘由
今天同事给我出了一道题：
有四个数字：8、8、3、3，通过加减乘除还有括号，使得结果为24
我一看这么简单的数学题，我弟弟都会，简直就是毫无挑战，于是就拿出笔开始算。“3x8=24”这么简单啊，但是还有两个“3、8”啊！，就这样算了一个小时，还是没算出来，内心很受打击。但是，没关系，我是程序员怎么可能解不出来啊，我非得写个算法算出来。于是有了下面的故事…
思路
要求出值为24的排列方式，我想到了暴力解法，将每一种可能性算一遍，如果结果刚好是24，那就是我需要的答案了呗。 所以题目就被分解了三个步骤：
- 遍历获取数字的排列方式
- 对于每一种数字的排列方式，获取符号的排列方式
- 计算每一种排列情况的值是否等于目标值
遍历数字的排列可能
思路： 4个数字有顺序的排列，其实就是一个排列组合问题，共有432*1 =
24种可能。我的想法是通过循环的方式遍历每一个可能，则对于第一个数字可以有四个数字可以选择，对于第二个数字则有剩余三个数字可以选择，对于第三个数字则有剩余两个数字可选，最后的一个数字则只剩一种可以选择。
遍历得到符号的排列组合
思路：对于可以使用的符号有“加减乘除”，另外还有括号，其实括号只是改变了计算的顺序，而我们已经将每一个可能的计算顺序排列了出来，所以只需要一步一步的从左往右计算就可以了。在四个数字之间加入符号一共有四个位置：
只需要对每一个位置进行一次循环求得所有的符号排列情况就好，需要注意的是：第一个符号位只能有“加减号”。
计算
对于每一个数字和符号的排列进行组合的情况，需要进行计算是否与目标值24相等，如果相等就打印出来。因为我们通过前面的组合得到了一个带有计算符号的字符串，这里我们可以使用eval()函数将值计算出来。
注意情况： 由于我们的所有操作都是从左到右一步一步的计算，如图：
所以会导致无法匹配出8/（1/3）=24的情况，所以，
当我们计算出来值为目标值的倒数的时候，就需要将除数与被除数交换位置，这个时候得到的表达式也是对的 。
完整代码
# -*- coding: UTF-8 -*-
from fractions import Fraction
# 目标值
targetNum = 24
# 已经输出的结果
printList = []
# 获取对应的符号
# 运算
def getNum(num1, num2, fu):
if fu == '/':
return "Fraction(" + num1 + "," + num2 + ")"
else:
return str(num1) + fu + str(num2)
# 计算结果 ,数字有4位，符号有3位
def computer(numlist, fulist):
global printList
global targetNum
# 前面两个数字计算的结果
v = "0"
# 计算表达式
pp = ""
# 遍历符号
# 从左到右依次计算，不需要按照乘除法先算的规则，因为要考虑括号的情况
for x in range(0, len(fulist)):
if x == 0:
v = getNum('', numlist[x], fulist[x])
pp = "" + fulist[x] + numlist[x]
else:
v = "(" + getNum(v, numlist[x], fulist[x]) + ")"
pp = "(" + pp + fulist[x] + numlist[x] + ")"
try:
# 判断是否已经输出了这个表达式，如果没有会报错
if printList.index(pp):
return
except Exception as e:
# 拦截错误，计算是否匹配结果
dif = eval(v) - targetNum
if abs(dif) == 0:
printList.append(pp)
print('----------------------')
print(pp, "=", eval(v))
print('----------------------')
elif eval(v) == Fraction(1, targetNum):
v = ""
pp = ""
# 除法倒置，将最后的一个除法的除数和被除数交换
for x in range(0, len(fulist)):
if x == 0:
v = getNum('', numlist[x], fulist[x])
pp = "" + fulist[x] + numlist[x]
else:
# 如果最后一个符号是“/”，则倒置
if x == len(fulist) - 1 and fulist[x] == '/':
v = "(" + getNum(numlist[x], v, fulist[x]) + ")"
pp = "(" + numlist[x] + fulist[x] + pp + ")"
else:
v = "(" + getNum(v, numlist[x], fulist[x]) + ")"
pp = "(" + pp + fulist[x] + numlist[x] + ")"
# 同样的计算方式，只打印一次
try:
printList.index(pp)
except Exception as e:
printList.append(pp)
print('----------------------')
print(pp, "=", eval(v))
print('----------------------')
# 计算排列组合答案
def computer24(numList):
global num
# 循环遍历出数字排列组合
for x in range(0, len(numList)):
# 得到第一个数字
a = numList[x]
# 获得剩下的三个数字的列表
restListA = []
for x1 in range(0, len(numList)):
if x1 != x:
restListA.append(numList[x1])
for y in range(0, len(restListA)):
# 第二个数字
b = restListA[y]
restListB = []
for y1 in range(0, len(restListA)):
if y1 != y:
restListB.append(restListA[y1])
#
for z in range(0, len(restListB)):
# 第三个数字
c = restListB[z]
for z1 in range(0, len(restListB)):
if z1 != z:
d = restListB[z1]
numArray = [a, b, c, d]
# 得到了数字组合，需要对数字间隔进行填符号
# 第一个符号
fulist = ['+', '-', '*', '/']
for q in range(0, 2):
# 第二位
for w in range(0, 4):
# 第三位
for e in range(0, 4):
# 第四位
for r in range(0, 4):
f = [fulist[q], fulist[w],
fulist[e], fulist[r]]
# print(numArray, f)
computer(numArray, f)
computer24(['8','8','3','3'])
print("计算完成！")
运行实例
计算
8、8、3、3组合成24>>>(8/((-8/3)+3)) = 24计算
1、5、5、5组合为24>>>(((-1/5)+5)*5) = 24计算
4、4、10、10组合为24>>>(((+10*10)-4)/4)= 24计算
2、2、11、11组合为24>>>(((+2/11)+2)*11) = 24