给定4个整
数,其中每个数字只能使用一次;任意使用 + - * / ( )
,构造出一个表达式,使得最终结果为24,这就是常见的算24点的游戏。这方面的程序很多,一般都是穷举求解。本文介绍一种典型的算24点的程序算法,并
给出两个具体的算24点的程序:一个是面向过程的C实现,一个是面向对象的java实现。
基本原理是穷举4个整数所有可能的表达式,然后对表达式求值。
表达式的定义: expression = (expression|number) operator (expression|number)
因为能使用的4种运算符 + - * / 都是2元运算符,所以本文中只考虑2元运算符。2元运算符接收两个参数,输出计算结果,输出的结果参与后续的计算。
由上所述,构造所有可能的表达式的算法如下:
(1) 将4个整数放入数组中
(2) 在数组中取两个数字的排列,共有 P(4,2) 种排列。对每一个排列,
(2.1) 对 + - * / 每一个运算符,
(2.1.1) 根据此排列的两个数字和运算符,计算结果
(2.1.2) 改表数组:将此排列的两个数字从数组中去除掉,将 2.1.1 计算的结果放入数组中
(2.1.3) 对新的数组,重复步骤 2
(2.1.4) 恢复数组:将此排列的两个数字加入数组中,将 2.1.1 计算的结果从数组中去除掉
可见这是一个递归过程。步骤 2 就是递归函数。当数组中只剩下一个数字的时候,这就是表达式的最终结果,此时递归结束。
在程序中,一定要注意递归的现场保护和恢复,也就是递归调用之前与之后,现场状态应该保持一致。在上述算法中,递归现场就是指数组,2.1.2 改变数组以进行下一层递归调用,2.1.3 则恢复数组,以确保当前递归调用获得下一个正确的排列。
括号 () 的作用只是改变运算符的优先级,也就是运算符的计算顺序。所以在以上算法中,无需考虑括号。括号只是在输出时需加以考虑。
#include <iostream>
#include <string>
#include <cmath>
#using <System.dll>
#using <System.Configuration.Install.dll>
using namespace std;
using namespace System;
using namespace System::Diagnostics;
const double PRECISION = 1E-6;
const int COUNT_OF_NUMBER = 4;
const int NUMBER_TO_BE_CAL = 24;
double number[COUNT_OF_NUMBER];
string expression[COUNT_OF_NUMBER];
bool Search(int n)
{
if (n == 1) {
if ( fabs(number[0] - NUMBER_TO_BE_CAL) < PRECISION ) {
cout << expression[0] <<" = 24"<< endl;
return true;
} else {
return false;
}
}
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
double a, b;
string expa, expb;
a = number[i];
b = number[j];
number[j] = number[n - 1];
expa = expression[i];
expb = expression[j];
expression[j] = expression[n - 1];
expression[i] = '(' + expa + '+' + expb + ')';
number[i] = a + b;
if ( Search(n - 1) ) return true;
expression[i] = '(' + expa + '-' + expb + ')';
number[i] = a - b;
if ( Search(n - 1) ) return true;
expression[i] = '(' + expb + '-' + expa + ')';
number[i] = b - a;
if ( Search(n - 1) ) return true;
expression[i] = '(' + expa + '*' + expb + ')';
number[i] = a * b;
if ( Search(n - 1) ) return true;
if (b != 0) {
expression[i] = '(' + expa + '/' + expb + ')';
number[i] = a / b;
if ( Search(n - 1) ) return true;
}
if (a != 0) {
expression[i] = '(' + expb + '/' + expa + ')';
number[i] = b / a;
if ( Search(n - 1) ) return true;
}
number[i] = a;
number[j] = b;
expression[i] = expa;
expression[j] = expb;
}
}
return false;
}
void main()
{
for (int i = 0; i < COUNT_OF_NUMBER; i++) {
char buffer[20];
int x;
cin >> x;
number[i] = x;
itoa(x, buffer, 10);
expression[i] = buffer;
}
if ( Search(COUNT_OF_NUMBER) ) {
cout << "Success." << endl;
} else {
cout << "Fail." << endl;
}
}