本
文
摘
要
昨天在刷QQ空间的时候发现了一条好玩的说说：
用四个10，通过添加符号来算出1到10的结果。我人脑可能一时想不到，但用电脑把所有可能都试一遍，总能找到结果吧？（手动滑稽）。
我首先想到的是，4个10中间有三个空，无非就是往三个空里填四种运算符号， 一共434^3 种可能，就是三层循环嘛。但是又一想，如果需要加括号呢？这样写循环可就麻烦多了。如果再过分一点，不是4个10，而是4个不一样的数字呢？我是不是还要考虑它们四个的排列顺序？
没办法，只能想一种不那么暴力的算法。
其实我们可以不那么纠结于算式的样子，表面上你往式子里加了括号，实际上你是在表达“先算这一步，再算那一步”。也就是说，往式子里添加符号的本质是：“从四个数的数组中先挑出两个数进行四则运算，得到的结果与剩下的两个数，组成三个数的新数组；再从三个数的新数组中挑两个数进行四则运算，得到的结果与剩下的一个数，组成两个数的新数组；最后对两个数的新数组中的两个数进行四则运算，使最后的结果等于你想要的结果。”
这个算法特别适合函数递归求解，每次需要给函数传入的参数是“数组”和“想要的结果”，每调用一次函数就更新这个“数组”，并把新的数组作为参数继续调用这个函数，直到数组里只剩一个数。
当然，在上面的递归过程中，我们需要记录每一步的操作，不然最后咋知道结果是怎么算出来的。于是就有了下面的代码：
class solution: step=[] #用于记录每一步的步骤 def helper(self,nums,n): #nums是数组，n是想得到的算式结果 if len(nums) == 1: #当数组里只剩一个数时，返回“这个数是不是你想要的结果” return abs(nums[0] - n) < 1e-6 for i in range(len(nums)): for j in range(len(nums)): if i != j: #从数组里挑两个数（当然这里挑的是下标） newnums = [nums[k] for k in range(len(nums)) if i != k != j] #把原数组删去这两个数之后组成新数组 if self.helper(newnums + [nums[i] + nums[j]],n): #对挑出的两个数进行加法运算并把结果与新数组合并，作为参数递归调用 self.step.append(str(nums[i])+++str(nums[j])+=+str(nums[i] + nums[j])) #用字符串记录这一步的操作 return self.step else: self.step=[] #如果最后发现运算结果不是想要的算式结果，清空step if self.helper(newnums + [nums[i] - nums[j]],n): #对挑出的两个数进行减法运算并把结果与新数组合并，作为参数递归调用 self.step.append(str(nums[i])+-+str(nums[j])+=+str(nums[i] - nums[j])) #用字符串记录这一步的操作 return self.step else: self.step=[] #如果最后发现运算结果不是想要的算式结果，清空step if self.helper(newnums + [nums[i] * nums[j]],n): #对挑出的两个数进行乘法运算并把结果与新数组合并，作为参数递归调用 self.step.append(str(nums[i])+*+str(nums[j])+=+str(nums[i] * nums[j])) #用字符串记录这一步的操作 return self.step else: self.step=[] #如果最后发现运算结果不是想要的算式结果，清空step if nums[j] != 0 and self.helper(newnums + [nums[i] / nums[j]],n): #对挑出的两个数进行除法运算并把结果与新数组合并，作为参数递归调用 self.step.append(str(nums[i])+/+str(nums[j])+=+str(nums[i] / nums[j])) #用字符串记录这一步的操作 return self.step else: self.step=[] #如果最后发现运算结果不是想要的算式结果，清空step return False在上面的代码中，我们用step属性记录每一步的操作。当你在某个分支到达最底层时，如果发现没有算出想要的结果，可以选择清空step。因为这样递归调用的方法类似“深度优先搜索”，所以在没求出想要的结果的分支清空step，可以使其他分支在使用step时，总是以空列表开始。这样在最后显示step的内容时，可以保证里面只有“能算出想要的结果”的那一种方法。
下面我们调用一下这个方法，看看QQ空间里的那道智商测试题怎么做：
S=solution() for i in range(1,11): print(i,:,end=) res=S.helper([10]*4,i) if res: for s in res[::-1]: print(s,end=) print() else: print(无解)（因为上面代码的step.append()是从最底层开始往里添加，所以读取的时候倒序才是我们想要的顺序）运行以后，可以看到结果：
也就是说，如果只用加减乘除和括号，四个10没法算出4、6、7。其他的可以算，步骤也给出了。
其实这个算法不仅仅适用于这道智商测试题，还可以用来玩著名小游戏：“24点”(给你四个数让你用它们算出24）。毕竟两者的原理一模一样。
不过用来玩24点的话要稍微注意一个情况：这个算法只是返回找到的第一个符合的结果，你并不能保证它里面不会出现这样的步骤：
3-1=-2 ， 6--2=8在上面的智商测试题里没有出现这样的结果，但换做其他数就不一定了。其实结果上没有错，但减-2这样表示不太符合我们的习惯，于是我们对”记录每一步的操作“的语句进行一点点修改：如果运算符后的数字是负数，就加括号：
def helper(self,nums,n): if len(nums) == 1: return abs(nums[0] - n) < 1e-6 for i in range(len(nums)): for j in range(len(nums)): if i != j: newnums = [nums[k] for k in range(len(nums)) if i != k != j] if self.helper(newnums + [nums[i] + nums[j]],n): if nums[j]>=0: self.step.append(str(nums[i]) + + + str(nums[j]) + = + str(nums[i] + nums[j])) else: self.step.append(str(nums[i]) + +( + str(nums[j]) + )= + str(nums[i] + nums[j])) return self.step else: self.step=[] if self.helper(newnums + [nums[i] - nums[j]],n): if nums[j]>=0: self.step.append(str(nums[i]) + - + str(nums[j]) + = + str(nums[i] - nums[j])) else: self.step.append(str(nums[i]) + -( + str(nums[j]) + )= + str(nums[i] - nums[j])) return self.step else: self.step=[] if self.helper(newnums + [nums[i] * nums[j]],n): if nums[j]>=0 : self.step.append(str(nums[i]) + * + str(nums[j]) + = + str(nums[i] * nums[j])) else: self.step.append(str(nums[i]) + *( + str(nums[j]) + )= + str(nums[i] * nums[j])) return self.step else: self.step=[] if nums[j] != 0 and self.helper(newnums + [nums[i] / nums[j]],n): if nums[j]>=0: self.step.append(str(nums[i]) + / + str(nums[j]) + = + str(nums[i] / nums[j])) else: self.step.append(str(nums[i]) + /( + str(nums[j]) + )= + str(nums[i] / nums[j])) return self.step else: self.step=[] return self.step现在我们就从网页24点小游戏找个例子试试：
运行下面的代码：
s=solution1() res=s.helper([2,3,9,5],24)[::-1] for r in res: print(r,end=)显示的结果是：
回到网页照着这个顺序操作一通：
果然算出想要的结果了呢！
