学步园

24点是一种老少皆宜的游戏，它的具体玩法如下：

给玩家4张牌，每张牌的面值都在1---13之间，允许其中有数值相同的牌。采用加、减、乘、除四则运算，允许中间运算存在小数，并且可以使用括号，但每张牌只能使用一次，尝试构造一个多项式，使其运算结果为24.

输入：n1，n2，n3，n4。

输出：若能得到运算结果为24，则输出一个对应的计算表达式。

输入：11，8，3，5

输出：(11-8)*(3+5) = 24

分析与解法

最直接的想法就是采用穷举法，因为运算符号只有4种，每个数字只能使用一次，所以通过穷举4个数所有可能的表达式，并分别计算出各表达式的值，就可以得到答案。那么如何穷举所有可能的表达式呢？

先不考虑使用括号，可以做出如下分析：

每个数只能使用一次，对4个整数进行全排列，总共有4!=4*3*2*1=24中排列。4个数的四则运算中总共需要3个运算符，同一运算符可以重复出现，那么对于每一个排列，总共可有4*4*4中表达式。因此在不考虑括号的情况下，总共可以得到4!*4*4*4=1536中表达式。

接下来再考虑加上括号后的情况，对于4个数而言，总共会有以下5种加括号的方式：

(A(B(CD)))、(A((BC)D))、((AB)(CD))、((A(BC))D)、(((AB)C)D)。

所以需要遍历的表达式数最多有4!*4*4*4*5=7680种。即使采用逆波兰表达式，其总数也不变。

通过上面的分析，得到了一种解24点的基本思路，即遍历运算符、数字和括号的所有排列组合形式，接下来，我们将更加细致地讨论这种解法的一个具体实现。

假设给定的4个数组成的集合为A={1,2,3,4}，定义函数f(A)为对集合A中的元素进行所有可能的四则混合运算所得到的值。

首先从集合A中任意取出两个数，如取出1和2，A=A-{1,2}，对取出来的数分别进行不同的四则运算，1+2=3,1-2=-1,1/2=0.5,1*2=2，将得到的结果再分别加入集合A，可得到B={3,3,4}，C={-1,3,4}，D={0.5,3,4}，E={2,3,4}四个新的集合，那么f(A)= f(B)+f(C)+f(D)+f(E)，通过以上的计算就达到了分而治之的目的，问题规模就从4个数降到了3个数，成了3个数的4个子问题之和。综上所述，可以得到递归解法如下：

将给定的4个数放入数组Array中，将其作为参数传入函数f中，伪代码如下所示：

f(Array)<br /> {<br /> if(Array.Length < 2)<br /> {<br /> if(得到的最终结果为)<br /> 输出表达式<br /> else 输出无法构造符合要求的表达式<br /> }<br /> foreach(从数组中任取两个数的组合)<br /> {<br /> foreach(运算符(+, -, *, /))<br /> {<br /> 1、计算该组合在此运算符下的结果<br /> 2、将该组合中的两个数从原数组中移除，并将步骤的计算结果放入数组<br /> 3、对新数组递归调用f。如果找到一个表达式则返回<br /> 4、将步骤的计算结果移除，并将该组合中的两个数重新放回数组中对应的位置<br /> }<br /> }<br /> }

具体代码如下所示：

#include "iostream"<br /> #include "cmath"<br /> #include "string"<br /> using namespace std;</p> <p>const double Threshold = 1E-6; //容差值<br /> const int CardsNumber = 4;<br /> const int ResultValue = 24;<br /> double number[CardsNumber]; //输入的4个整数<br /> string result[CardsNumber]; //保存表达式</p> <p>bool PointsGame(int n)<br /> {<br /> if(n == 1)<br /> {<br /> //由于浮点数运算会有精度误差，所以用一个很小的数1E-6来做容差值<br /> if(fabs(number[0] - ResultValue) < Threshold)<br /> {<br /> cout << result[0] << " == 24" << endl;<br /> return true;<br /> }<br /> else<br /> {<br /> return false;<br /> }<br /> }<br /> for(int i = 0; i < n; i++)<br /> {<br /> for(int j = i + 1; j < n; j++) //从数组中任取两个数的组合<br /> {<br /> double a, b;<br /> string expa, expb;</p> <p> a = number[i];<br /> b = number[j];<br /> number[j] = number[n-1]; //任取两个数并将其结果放入数组后，原数组的个数减少一个</p> <p> expa = result[i]; //保存表达式中的数字<br /> expb = result[j];<br /> result[j] = result[n-1];</p> <p> result[i] = '(' + expa + '+' + expb + ')'; //任取的两个数在“+”运算符下的结果<br /> number[i] = a + b; //将该运算符下的运算结果放入数组中<br /> if(PointsGame(n - 1))<br /> return true;</p> <p> result[i] = '(' + expa + '-' + expb + ')'; //任取的两个数在“-”运算符下的结果<br /> number[i] = a - b;<br /> if(PointsGame(n - 1))<br /> return true;</p> <p> result[i] = '(' + expb + '-' + expa + ')'; //任取的两个数在“-”运算符下的结果<br /> number[i] = b - a;<br /> if(PointsGame(n - 1))<br /> return true;</p> <p> result[i] = '(' + expa + '*' + expb + ')'; //任取的两个数在“*”运算符下的结果<br /> number[i] = a * b;<br /> if(PointsGame(n - 1))<br /> return true;<br /> if(b != 0)<br /> {<br /> result[i] = '(' + expa + '/' + expb + ')'; //任取的两个数在“/”运算符下的结果<br /> number[i] = a / b;<br /> if(PointsGame(n - 1))<br /> return true;<br /> }<br /> if(a != 0)<br /> {<br /> result[i] = '(' + expb + '/' + expa + ')'; //任取的两个数在“/”运算符下的结果<br /> number[i] = b / a;<br /> if(PointsGame(n - 1))<br /> return true;<br /> }<br /> number[i] = a; //将刚开始任取的两个数重新放回数组中对应的位置<br /> number[j] = b;<br /> result[i] = expa;<br /> result[j] = expb;<br /> }<br /> }<br /> return false;<br /> }</p> <p>int main(void)<br /> {<br /> int i,x;<br /> for(i = 0; i < CardsNumber; i++)<br /> {<br /> char buffer[20];<br /> cout << "Please input the " << i+1 << "th number:";<br /> cin >> x;<br /> number[i] = x; //保存输入的4个整数的浮点型数组<br /> itoa(x, buffer, 10); //把输入的4个整数按10进制转化为字符串<br /> result[i] = buffer;<br /> }<br /> if(PointsGame(CardsNumber) )<br /> {<br /> cout << "Success." << endl;<br /> }<br /> else<br /> {<br /> cout << "Fail." << endl;<br /> }<br /> system("pause");<br /> return 0;<br /> }

运行效果图如下：