论坛上有人在问怎样写计算24点的程序。我觉得这个题目挺有趣的，于是就自己写了一个。虽然这个程序也能运行，而且还曾帮两个同事解决了他们孩子的作业问题，但是我却并不满意。原因很简单：它虽然能列举出所有可能的组合，但这只是我预先分析的结果。如果给出的数字不是4个，而是5个或6个，那么这段程序就彻底报废了。更重要的是，如果有5个，6个或者更多的数字，事先分析的办法也行不通了。因此我必须寻找一个真正的算法。
算法分析基本的运算只有四种，加、减、乘、除。因此，不论一个算式有多复杂，我们总可以把它概括成一个基本的加减乘除算式，只是运算符的左边和（或）右边不是一个简单的数，而是一个复杂的算式罢了。于是，我们的第一个任务，就是把一个集合拆解成两个集合，并且枚举出其所有的可能性。
分拆集合首先要声明，说集合实际上并不准确。集合里面不能有重复的元素，但是计算24点的数字却可以重复。不过由于这个算法的思路是源自于集合运算，因此我还是把它称为“集合的分拆”。
那么怎样才能将一个集合分拆开来，并且枚举出其所有的可能性呢？我们都知道，如果一个集合有n个元素，那么它总共会有2**n个子集[1]。因为根据排列组合的乘法原则，对于其任意一个子集，每个元素都有两种状态，属于或不属于。因此，n个元素就会有2**n个子集。于是：
def enumerateAllSubsets(elements) : def appendElement(orig_subsets, element) : result = [] for set in orig_subsets : result.append(set) tmp = [] for ele in set : tmp.append(ele) tmp.append(element) result.append(tmp) return result result = [[]] for e in elements : result = appendElement(result, e) for e in result : e.sort() return result
这段程序的思路是这样的：假设有一个集合，它的子集集合是orig_subsets，那么当这个集合增加一个元素element之后，appendElement方法就负责返回这个新集合的子集集合。而enumerateAllSubsets先创建一个只包含空集的集合。这个只含空集的集合，就是空集的子集集合。然后我们依次往空集里面添加元素，并且利用appendElement获取其子集的集合。这样等我们把elements全都加进去之后，也就获得了elements的子集集合了。
enumerateAllSubsets所返回的子集集合并不能直接用于24点的计算，因此我们必须先做一些准备工作——去除空集和全集。由于集合中可能会有重复的数字，为了减少运算量，我们还要去除重复的子集。
def getSets (elements): elements.sort() tmp_result = enumerateAllSubsets(elements) tmp_result.remove([]) tmp_result.remove(elements) result = [] for e in tmp_result : e.sort() try: result.index(e) except ValueError: result.append(e) return result
此外，我们还需要一个计算补集的函数。
def suppSet (fullSet, subSet): result = [] for item in fullSet : # 由于可能会有重复的元素，因此不能写 result.append(item) # for item in fullSet: for item in subSet : # if not item in subSet : result.remove(item) # result.append(item) return result
构造算式就这个算法而言，算式的构造并不难，但是很烦。下面我们用二叉树来表示算式，用递归来求值和打印。
ADD = "+" MIN = "-" MUL = "*" DIV = "/" TYPE_OF_NUMBERS = (type(1), type(1.0)) class equationTree(object) : def __init__ (self, left_tree, operator=None, right_tree=None): self.left_tree = left_tree self.right_tree = right_tree self.operator = operator def value (self): if not self.operator : return float(self.left_tree) else: if type(self.left_tree) in TYPE_OF_NUMBERS: str_to_calc = str(float(self.left_tree)) else: str_to_calc = str(self.left_tree.value()) str_to_calc += self.operator if type(self.right_tree) in TYPE_OF_NUMBERS: str_to_calc += str(float(self.right_tree)) else: str_to_calc += str(self.right_tree.value()) try: ## 1. 出现 ZeroDivError的时候，这个算式的值就为None ## 2. 这要这个算式的某一部分的值为None，那么这个算式的值就是None result = eval(str_to_calc) except : result = None return result def __repr__ (self): if type(self.left_tree) in TYPE_OF_NUMBERS : left_repr = str(self.left_tree) else: left_repr = `self.left_tree` if type(self.right_tree) in TYPE_OF_NUMBERS : right_repr = str(self.right_tree) else: right_repr = `self.right_tree` if not self.operator : return left_repr else: if self.operator == ADD: pass elif self.operator == MIN: if type(self.right_tree) not in TYPE_OF_NUMBERS and self.right_tree.operator in (ADD, MIN): right_repr = "(" + right_repr + ")" elif self.operator == MUL: if type(self.left_tree) not in TYPE_OF_NUMBERS and self.left_tree.operator in (ADD, MIN) : left_repr = "(" + left_repr + ')' if type(self.right_tree) not in TYPE_OF_NUMBERS and self.right_tree.operator in (ADD, MIN): right_repr = "(" + right_repr +')' else: if type(self.right_tree) not in TYPE_OF_NUMBERS and self.right_tree.operator : right_repr = "(" + right_repr + ')' if type(self.left_tree) not in TYPE_OF_NUMBERS and (self.left_tree.operator in (ADD, MIN)): left_repr = "(" + left_repr + ')' return left_repr + self.operator + right_repr
枚举算式接下来我们就用上面准备的这两个工具来枚举出所有的算式。还是用递归。
def getEqTrees (elements): if len(elements) == 1 : return [equationTree(elements[0])] elif len(elements) == 2: return [equationTree(elements[0], ADD, elements[1]), equationTree(elements[0], MIN, elements[1]), equationTree(elements[0], MUL, elements[1]), equationTree(elements[0], DIV, elements[1]), equationTree(elements[1], MIN, elements[0]), equationTree(elements[1], DIV, elements[0]),] else: result = [] for e in getSets(elements): for left_tree in getEqTrees(e) : for right_tree in getEqTrees(suppSet(elements, e)) : for op in (ADD, MIN, MUL, DIV) : result.append(equationTree(left_tree, op, right_tree)) return result
结尾程序已经大致完成了，最有只要加一段主程序就能运行了[2]。
if __name__ == '__main__' : print """ Written by shhgs, on March 3, 2004.""" result = [] print """ Please input a tuple of integer, delimited by colon. For example: 1, 2, 3, 4 Don't try to input more than 5 numbers, otherwise it will take a long long time to respond. Four is recommended. """ tup = input('Please input the tuple of integers: ') for eq in getEqTrees(list(tup)): if eq.value() == 24 : result.append(eq) print "%s = 24" % eq
我用4个变量和5个变量测试过这段程序，都获得了成功。但是6变量算了一个小时还是没结果，最后我放弃了。我想大概还是计算量太大了。有兴趣的读者可以试试。顺便说一下，我的测试平台是P4 Celeron 2.0G, 1G内存，Windows 2000 SP4。如果你的配置低于这个，建议就不要试了。
[1]这个算法是用Python实现的，因此这里用Python的表示方法。有兴趣的读者可以试着用Java或其他语言来实现。
[2]这个程序里面有中文注释，所以运行的时候会出现警告。要想解决这个问题，可以在程序的第一行加上：
# -*- coding: mbcs -*-
本文地址：http://com.8s8s.com/it/it37242.htm