給定4個(gè)整
數(shù)，其中每個(gè)數(shù)字只能使用一次；任意使用 + - * / ( )
，構(gòu)造出一個(gè)表達(dá)式，使得最終結(jié)果為24，這就是常見的算24點(diǎn)的游戲。這方面的程序很多，一般都是窮舉求解。本文介紹一種典型的算24點(diǎn)的程序算法，并
給出兩個(gè)具體的算24點(diǎn)的程序：一個(gè)是面向過程的C實(shí)現(xiàn)，一個(gè)是面向?qū)ο蟮膉ava實(shí)現(xiàn)。
基本原理是窮舉4個(gè)整數(shù)所有可能的表達(dá)式，然后對(duì)表達(dá)式求值。
表達(dá)式的定義： expression = (expression|number) operator (expression|number)
因?yàn)槟苁褂玫?種運(yùn)算符 + - * / 都是2元運(yùn)算符，所以本文中只考慮2元運(yùn)算符。2元運(yùn)算符接收兩個(gè)參數(shù)，輸出計(jì)算結(jié)果，輸出的結(jié)果參與后續(xù)的計(jì)算。
由上所述，構(gòu)造所有可能的表達(dá)式的算法如下：
(1) 將4個(gè)整數(shù)放入數(shù)組中
(2) 在數(shù)組中取兩個(gè)數(shù)字的排列，共有 P(4,2) 種排列。對(duì)每一個(gè)排列，
(2.1) 對(duì) + - * / 每一個(gè)運(yùn)算符，
(2.1.1) 根據(jù)此排列的兩個(gè)數(shù)字和運(yùn)算符，計(jì)算結(jié)果
(2.1.2) 改表數(shù)組：將此排列的兩個(gè)數(shù)字從數(shù)組中去除掉，將 2.1.1 計(jì)算的結(jié)果放入數(shù)組中
(2.1.3) 對(duì)新的數(shù)組，重復(fù)步驟 2
(2.1.4) 恢復(fù)數(shù)組：將此排列的兩個(gè)數(shù)字加入數(shù)組中，將 2.1.1 計(jì)算的結(jié)果從數(shù)組中去除掉
可見這是一個(gè)遞歸過程。步驟 2 就是遞歸函數(shù)。當(dāng)數(shù)組中只剩下一個(gè)數(shù)字的時(shí)候，這就是表達(dá)式的最終結(jié)果，此時(shí)遞歸結(jié)束。
在程序中，一定要注意遞歸的現(xiàn)場保護(hù)和恢復(fù)，也就是遞歸調(diào)用之前與之后，現(xiàn)場狀態(tài)應(yīng)該保持一致。在上述算法中，遞歸現(xiàn)場就是指數(shù)組，2.1.2 改變數(shù)組以進(jìn)行下一層遞歸調(diào)用，2.1.3 則恢復(fù)數(shù)組，以確保當(dāng)前遞歸調(diào)用獲得下一個(gè)正確的排列。
括號(hào) () 的作用只是改變運(yùn)算符的優(yōu)先級(jí)，也就是運(yùn)算符的計(jì)算順序。所以在以上算法中，無需考慮括號(hào)。括號(hào)只是在輸出時(shí)需加以考慮。
#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;
}
}