1、概述
給定4個整數，其中每個數字只能使用一次；任意使用 + - * / ( ) ，構造出一個表達式，使得最終結果為24，這就是常見的算24點的游戲。這方面的程序很多，一般都是窮舉求解。本文介紹一種典型的算24點的程序算法，並給出兩個具體的算24點的程序：一個是面向過程的C實現，一個是面向對象的java實現。
2、基本原理
基本原理是窮舉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 則恢復數組，以確保當前遞歸調用獲得下一個正確的排列。
括號 () 的作用只是改變運算符的優先級，也就是運算符的計算順序。所以在以上算法中，無需考慮括號。括號只是在輸出時需加以考慮。
3、面向過程的C實現
這是 csdn 算法論壇前版主海星的代碼，程序非常簡練、精致：
#include
#include
#include
using namespace std;
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] << 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;
}
}
使用任一個 c++ 編譯器編譯即可。
這個程序的算法與 2、基本原理 所述的算法基本相同。其中 bool Search(int n) 就是遞歸函數，double number[] 就是數組。程序中比較重要的地方解釋如下：
(1) string expression[] 存放每一步產生的表達式，最後的輸出中要用到。expression[] 與 number[] 類似，也是遞歸調用的現場，必須在下一層遞歸調用前改變、在下一層遞歸調用後恢復。
(2) number[] 數組長度只有4。在 search() 中，每次取出兩個數後，使用局部變量 a, b 保存這兩個數，同時數組中加入運算結果，並調整數組使得有效的數字都排列在數組前面。在下一層遞歸調用後，利用局部變量 a, b 恢復整個數組。對 expression[] 的處理與 number[] 類似。
(3) 因為 + * 滿足交換率而 - / 不滿足，所以程序中，從數組生成兩個數的排列，
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
其內層循環 j 是從 i+1 -> n，而非從 0->n ，因為對於交換率來說，兩個數字的順序是無所謂的。當然，循環內部對 - / 做了特殊處理，計算了 a-b b-a a/b b/a 四種情況。
(4) 此程序只求出第一個解。當求出第一個解時，通過層層 return true 返回並輸出結果，然後程序結束。
(5) 以 double 來進行求解，定義精度，用以判斷是否為 24 。考慮 (5-1/5)*5 這個表達式就知道這麼做的原因了。
(6) 輸出時，為每個表達式都添加了括號。
4、面向對象的java實現
算法依然同 2、基本原理 。使用對象的好處是程序的結構更清晰，功能的擴充更方便。當然效率會比結構化程序低。對象設計如下：
類 類含有的變量 類含有的方法 說明 Number double value String toString() 這樣可以清晰地表達出 expression 的遞歸定義 Expression extends Number Number leftNumber right
char operator
String toString() Calculator Number[] numbersExpression[] expressions
add() clear() //操作 numberscalculate()
Permutor permutor()
java 程序的主類，實現算法 Permutor int i,j boolean next() 排列生成器，類似 iterator，從一個指定的數組中生成2個元素的排列完整的源代碼請看 http://www.ch2000.com.cn/~ganxc/expression.zip 。這是一個簡單的24點計算程序和表達式解析求值程序，使用方法請參閱其中的 ReadMe.txt
從中可以看到很多面向對象設計的好處：
(1) 在輸出表達式時，只要改寫 Number.toString() 和 Expression.toString() 即可。為了輸出必要的括號，去掉不必要的括號，只要改寫 Expression.toString() 即可。
(2) Permutor 排列生成器使得流程結構大大簡化。
(3) 封裝性好，生成3個數的排列，理論上只需改動 Permutor 的內部實現代碼
(4) 重用性好，Number, Expression 可以在其它地方，如表達式解析程序中重用。
當然這只是一個示例性的代碼，內部還有很多可以封裝、簡化的地方。在類的框架上作修改其實是很方便的事情。
