计算24点有不同版本,这里规定:运用加减乘除计算四个整数使它的结果为24。当然这个算法经过适当的修改适合所有的二元运算符,也能计算超过四个整数。
计算24点的算法较简单,就是穷举法。由于一般计算表达式含有括号,这使得穷举无从下手。所以本文使用另一种表达式——后缀表达式。
后缀表达式就是数字放前运算符放后的表达式。如:a+b表示为a b+,(a+b)*c-d表示为a b + c * d -。用这样表达式可以去掉括号,这对本文的算法很关键。
任何一个计算24点的算式都可以化成7位的后缀表达式。假设给定的四个整数:a b c d。给定的运算符号集{+,-,*,/}。首先从符号集中取出三个运算符,然后加上a b c d。这七个单位的每一个排列都可以当成一个后缀表达式:或者是不合法的,或者是合法的。穷举并计算这样的排列,就可找出答案。
上面的方法是先取定7个单位,然后判断这7个单位组成的表达式是否合法。换一种思路,先取定一个合法的表达式,即确定数字和符号的位置,然后确定7个单位,对应数字和符号的位置。
这两种枚举方法都可行,第二种会快一些,它把判断后缀表达式合法性放在最外层循环,从而省去了不少的判断。
注:这个里用的枚举集合的方法参见另一篇文章《从集合中枚举子集》。
具体实现见代码。
编译方式:
g++ Calc24.cpp SetIter.cpp 得到第一种方法。
g++ Calc24.cpp SetIter.cpp -DCALC24_ADV 得到第二种方法。