文章目录

• 1. 问题
• 2. 分析
• 2.1 数字
• 2.2 运算符号
• 2.3 括号
• 2.4 计算
• 3. 答案

1. 问题

暑假期间，办公室里经常会出现因无人看护而不得不跟随爸爸妈妈来上班的小朋友。如果不忙的话，我会陪他们一起玩，他们也都很喜欢和我玩。我们都喜欢玩数字游戏。这不，有位小朋友给我出了一道难题：三个5和一个1，只用加减乘除四则运算，每个数字只能且必须使用一次，如何让结果等于24？

这不就是经典的24点问题吗？这个咱拿手啊，从小就玩，小儿科的游戏岂能难倒老许！可是，对于这道题，我尝试了很久，却仍然找不到答案。

“这个题，是不是无解啊？”我试探着问小朋友。

“不是啦，这个题有答案，而且很简单。”小朋友一脸认真。

“好，再给我5分钟。”我赶紧溜进自己办公室，关上门，打开电脑。不用Python，估计是镇不住场子了。

2. 分析

走投无路的时候，穷举也许是最佳选择。4个数字，4种运算符号，外加括号，如何穷尽全部的算式呢？我们把问题分解一下。

2.1 数字

4个数字，每个数字只能且必须使用一次，这是一个排列问题，共有 4 × 3 × 2 = 24 4\times3\times2=24 4×3×2=24种排列方案。

Python内置模块itertools提供了排列函数permutations()，可以给出全部的排列方案。如果用ABCD表示4个数字，那么全部的排列如下。

>>> from itertools import permutations
>>> for item in permutations('ABCD'):
		print(item)
	
('A', 'B', 'C', 'D')
('A', 'B', 'D', 'C')
('A', 'C', 'B', 'D')
('A', 'C', 'D', 'B')
('A', 'D', 'B', 'C')
('A', 'D', 'C', 'B')
('B', 'A', 'C', 'D')
('B', 'A', 'D', 'C')
('B', 'C', 'A', 'D')
('B', 'C', 'D', 'A')
('B', 'D', 'A', 'C')
('B', 'D', 'C', 'A')
('C', 'A', 'B', 'D')
('C', 'A', 'D', 'B')
('C', 'B', 'A', 'D')
('C', 'B', 'D', 'A')
('C', 'D', 'A', 'B')
('C', 'D', 'B', 'A')
('D', 'A', 'B', 'C')
('D', 'A', 'C', 'B')
('D', 'B', 'A', 'C')
('D', 'B', 'C', 'A')
('D', 'C', 'A', 'B')
('D', 'C', 'B', 'A')

2.2 运算符号

针对每一种数字排列，我们需要从4种运算符号中允许重复地取出3个，组成一个算式。这个问题幻化成如下描述：有3个篮子，每个篮子里都有4种运算符，从每个篮子里各取1个符号，共有多少种可能？这是一个笛卡尔积的问题，答案是 4 × 4 × 4 = 64 4\times4\times4=64 4×4×4=64种可能。

Python内置模块itertools提供了笛卡尔积函数product()，可以给出全部的方案。

>>> from itertools import product
>>> for item in product('+-*/', '+-*/', '+-*/'):
		print(item)
	
('+', '+', '+')
('+', '+', '-')
('+', '+', '*')
('+', '+', '/')
('+', '-', '+')
('+', '-', '-')
('+', '-', '*')
('+', '-', '/')
('+', '*', '+')
('+', '*', '-')
('+', '*', '*')
('+', '*', '/')
('+', '/', '+')
('+', '/', '-')
('+', '/', '*')
('+', '/', '/')
('-', '+', '+')
('-', '+', '-')
('-', '+', '*')
('-', '+', '/')
('-', '-', '+')
('-', '-', '-')
('-', '-', '*')
('-', '-', '/')
('-', '*', '+')
('-', '*', '-')
('-', '*', '*')
('-', '*', '/')
('-', '/', '+')
('-', '/', '-')
('-', '/', '*')
('-', '/', '/')
('*', '+', '+')
('*', '+', '-')
('*', '+', '*')
('*', '+', '/')
('*', '-', '+')
('*', '-', '-')
('*', '-', '*')
('*', '-', '/')
('*', '*', '+')
('*', '*', '-')
('*', '*', '*')
('*', '*', '/')
('*', '/', '+')
('*', '/', '-')
('*', '/', '*')
('*', '/', '/')
('/', '+', '+')
('/', '+', '-')
('/', '+', '*')
('/', '+', '/')
('/', '-', '+')
('/', '-', '-')
('/', '-', '*')
('/', '-', '/')
('/', '*', '+')
('/', '*', '-')
('/', '*', '*')
('/', '*', '/')
('/', '/', '+')
('/', '/', '-')
('/', '/', '*')
('/', '/', '/')

2.3 括号

针对一个算式，枚举所有添加括号的可能，似乎没有规律。稍加分析，也很容易找到解决方案。我们用N表示数字，用#表示运算符，可能的情况大概有以下11种类型（其中有些是等价的，为了简单起见，我们不再继续优化了）。

1. N # N # N # N
2. (N # N ) # N # N
3. N # N # (N # N)
4. N # (N # N) # N
5. (N # N) # (N # N)
6. (N # N # N) # N
7. ((N # N) # N) # N
8. (N # (N # N)) # N
9. N # (N # N # N)
10. N # ((N # N) # N)
11. N # (N # (N # N))

2.4 计算

数字有24种排列方式，运算符号有64种方案，添加括号有11种可能，则全部可能的算式有 24 × 64 × 11 = 16896 24\times64\times11=16896 24×64×11=16896个。我们只要将每一个字符串形式的算式（表达式）用eval()函数计算结果，就可以找到结果等于24的算式。当然，有些算式可能无意义，比如除数为0的情况。针对无意义的算式，eval()会抛出异常，我们只需捕捉并忽略异常就可以。

3. 答案

有了上面的分析，写代码就成了水到渠成、轻松愉快的事情了。

>>> from itertools import permutations, product
>>> def game24(n1,n2,n3,n4):
		for a,b,c,d in permutations((n1,n2,n3,n4),4):
			for o1,o2,o3 in product(['+','-','*','/'], repeat=3): # 笛卡尔积的另一种写法
				cases = list()
				cases.append('%d%s%d%s%d%s%d'%(a,o1,b,o2,c,o3,d))
				cases.append('(%d%s%d)%s%d%s%d'%(a,o1,b,o2,c,o3,d))
				cases.append('%d%s%d%s(%d%s%d)'%(a,o1,b,o2,c,o3,d))
				cases.append('%d%s(%d%s%d)%s%d'%(a,o1,b,o2,c,o3,d))
				cases.append('(%d%s%d)%s(%d%s%d)'%(a,o1,b,o2,c,o3,d))
				cases.append('(%d%s%d%s%d)%s%d'%(a,o1,b,o2,c,o3,d))
				cases.append('((%d%s%d)%s%d)%s%d'%(a,o1,b,o2,c,o3,d))
				cases.append('(%d%s(%d%s%d))%s%d'%(a,o1,b,o2,c,o3,d))
				cases.append('%d%s(%d%s%d%s%d)'%(a,o1,b,o2,c,o3,d))
				cases.append('%d%s((%d%s%d)%s%d)'%(a,o1,b,o2,c,o3,d))
				cases.append('%d%s(%d%s(%d%s%d))'%(a,o1,b,o2,c,o3,d))
				for expression in cases:
					try: # 捕获表达式中分母为0的异常
						if eval(expression) == 24:
							print('答案：%s = 24'%expression)
							return
					except:
						pass
		print('无解！')
	
>>> game24(5,5,5,1)
答案：5*(5-1/5) = 24
>>> game24(1,3,4,6)
答案：6/(1-3/4) = 24
>>> game24(10,10,4,4)
答案：(10*10-4)/4 = 24
>>> game24(7,7,3,3)
答案：7*(3/7+3) = 24
>>> game24(1,5,7,10)
答案：(1+7/5)*10 = 24
>>> game24(15,25,37,80)
无解！

穷举所有变化，速度怎么样？加上时间度量，用上面同样的题目测试，最快5毫秒，最慢（全部穷尽算式）146毫秒。

>>> game24(5,5,5,1)
答案：5*(5-1/5) = 24，耗时0.011
>>> game24(1,3,4,6)
答案：6/(1-3/4) = 24，耗时0.117
>>> game24(10,10,4,4)
答案：(10*10-4)/4 = 24，耗时0.005
>>> game24(7,7,3,3)
答案：7*(3/7+3) = 24，耗时0.017
>>> game24(1,5,7,10)
答案：(1+7/5)*10 = 24，耗时0.014
>>> game24(15,25,37,80)
无解！耗时0.146

经过验证，一切都OK了。接下来，就是我在小朋友们面前吹牛的时刻了，你一定能想象得到。哈哈哈。