24點游戲算法

在現實項目開發應用中，游戲方面的應用程序比較受歡迎，在軟件產業中占據了很大的比例。例如24點游戲是一個棋牌類益智游戲，要求結果等于24。在本節中，將詳細講解C語言實現24點游戲的算法。

實例15-2　編程實現24點游戲

問題描述：編寫實現24點游戲的C語言程序。

算法分析：其實24點游戲是用4個數字經過數學運行，并得到結果是24的過程。大多數版本應該使用撲克的52張牌（大小王除外），A表示1，K表示13，看任意4張牌是否能夠組合得到24。在將4個數進行四則運算時，一般的思維是在4個數中間的3個空放置3個運算符，然后需要在不同的地方加上括號表示優先級的不同。如果僅僅是數字和運算符則很好實現，一旦要添加括號就會變得比較難了。但是后綴表達式可以實現無括號的優先級運算，那么此處使用后綴表達式的這種方法來實現就比較簡單了。

在此假設I、J、M、N是4個數，r、s、t是3個運算符。那么使用后綴表達式只有如下4種情況：

（1）I J r M N s t ==> (I r J) t (M s N)

（2）I J r M s N t ==> ((I r J) s M) t N

（3）I J M r s N t ==> (I s (J r M)) t N

（4）I J M N r s t ==> I t (J s (M r N))

上面4種情況分別有1536中可能，4種總計有6144種可能。假如每種情況計算3次，也就20000次計算而已，對計算機來說這個數目是極小的。在實現應用中，沒有采用任何取巧的辦法，而是每種情況使用了7個for循環進行計算。唯一的取巧是前兩種的前邊4個for循環是一樣，可以將這兩種拼接起來。

在處理整數計算時會面對一個問題，計算機無法精確地表示分數，特別是那種無限小數，比如1/3這種。如果不能精確計算，最后就無法判斷是否精確等于24，這是計算機的一個弱點。此處的解決方法是，每個數字都用一個int表示，int表示為4字節。由于最大的單個數為13，那么即使是13的連乘也不過28561，不足兩個字節能表示的65536。因此使用一個int的低兩個字節表示分子或者實際的數值（沒有分母，也就等于整個int表示的數），高兩個字節表示分母（不存在分母則表示為0）。在做計算時將分子統一為等分母的數，然后計算之后與分母作用得到最后的數。根據上述描述，4/5就表示為0x00050004。

因為找到一種解法就結束，所以根據輸入的數據，得到的可能與人工計算得到的結果有出入，比如2 2 6 6，人工計算結果一般為2*6+2*6，但是程序結果可能為(2+6)*(6/2)，當然結果也是正確的。另外還需要注意的是，對于任何兩個數計算得到負數，并沒有繼續向下計算，因為這個必須得加一個正數或者乘以一個負數才可能等于24。而既然能夠得到負數，兩個數的位置調換一下就是一個正數了，沒有必要在數值前邊加上負號來處理。

具體實現：編寫實例文件15-2.c，具體實現代碼如下所示。

#include <stdint.h>
#include <unistd.h>
#include <stdio.h>
#define MASK 0xFFFF
#define SHIFT 16
enum {FAILURE = 0, SUCCESS};
const char ops[] = "+*-/";
int test (const int nums[], char *result);
int calculate (int num1, int num2, char op);
int main(int argc, char * argv[])
{
int len = 0;
int nums[4] = {0};
int i;
char *result;
if (argc != 5)
 {
printf("Usage: 24.exe num1 num2 num3 num4n");
exit(1);
 }
for (i = 0 ;i < 4 ;i++ )
 {
len += strlen (argv[i+1]);
nums[i] = atoi (argv[i+1]);
if (nums[i] < 1 || nums[i] > 13)
 {
 printf ("所有的數字都應該是1到13正整數n");
 exit(2);
 }
 }
 /*2 pairs of paren, 3 operators, 1 for NULL. */
len += 4 + 3 + 1;
result = (char *)malloc (len);
if (test(nums, result))
 printf ("%sn", result);
else
 printf ("No Matched.n");
if (result != NULL)
 free (result);
getch();
return 0;
}
/* 測試所有可能的情況，找到一種解法*/
int test (const int nums[], char * result)
{
 int I, J, M, N;
int r, s, t;
int ret, ret1, ret2;
 /*first loop: I J r M N s t ==> (I r J) t (M s N) */
for (I = 0; I < 4; I++)
 {
for (J = 0; J < 4; J++)
 {
if (J == I)
continue;
for (r = 0; r < 4; r++)
 {
 ret1 = calculate (nums[I], nums[J], ops[r]);
if (ret1 <= 0)
 continue;
for (M = 0; M < 4; M++)
 {
if (M == I || M == J)
 continue;
for (N = 0; N < 4; N++)
 {
if (N == I || N == J || N == M)
 continue;
for (s = 0; s < 4; s++)
 {
 ret2 = calculate (nums[M], nums[N], ops[s]);
if (ret2 <= 0)
 continue;
for (t = 0; t < 4; t++)
 {
ret = calculate (ret1, ret2, ops[t]);
if (((ret&MASK)==24) && ((ret>>SHIFT)==0))
 {
 sprintf (result, "(%d%c%d)%c(%d%c%d)", 
 nums[I], ops[r], nums[J], ops[t],
 nums[M], ops[s], nums[N]);
 return SUCCESS;
 }
 }
 }
 }
 /* second loop: I J r M s N t ==> ((I r J) s M) t N */
for (s = 0; s < 4; s++)
 {
 ret2 = calculate (ret1, nums[M], ops[s]);
if (ret2 <= 0)
 continue;
for (N = 0; N < 4; N++)
 {
if (N == I || N == J || N == M)
 continue;
for (t = 0; t < 4; t++)
 {
ret = calculate (ret2, nums[N], ops[t]);
if (((ret&MASK)==24) && ((ret>>SHIFT)==0))
 {
sprintf (result, "((%d%c%d)%c%d)%c%d", 
nums[I], ops[r], nums[J], ops[s],
nums[M], ops[t], nums[N]);
return SUCCESS;
 }
 }
 }
 }
 }
 }
 }
 }
 /* third loop: I J M r s N t ==> (I s (J r M)) t N */
for (I = 0; I < 4; I++)
 {
for (J = 0; J < 4; J++)
 {
if (J == I)
 continue;
for (M = 0; M < 4; M++)
 {
if (M == I || M == J)
 continue;
for (r = 0; r < 4; r++)
 {
 ret1 = calculate (nums[J], nums[M], ops[r]);
if (ret1 <= 0)
 continue;
for (s = 0; s < 4; s++)
 {
 ret2 = calculate (nums[I], ret1, ops[s]);
if (ret2 <= 0)
 continue;
for (N = 0; N < 4; N++)
 {
if (N == I || N == J || N == M)
 continue;
for (t = 0; t < 4; t++)
 {
 ret = calculate (ret2, nums[N], ops[t]);
if (((ret&MASK)==24) && ((ret>>SHIFT)==0))
 {
 sprintf (result, "(%d%c(%d%c%d))%c%d", 
 nums[I], ops[s], nums[J], ops[r],
 nums[M], ops[t], nums[N]);
 return SUCCESS;
 }
 }
 }
 }
 }
 }
 }
 }
 /* forth loop: I J M N r s t ==> I t (J s (M r N)) */
for (I = 0; I < 4; I++)
 {
for (J = 0; J < 4; J++)
 {
if (J == I)
 continue;
for (M = 0; M < 4; M++)
 {
if (M == I || M == J)
 continue;
for (N = 0; N < 4; N++)
 {
if (N == I || N == J || N == M)
 continue;
for (r = 0; r < 4; r++)
 {
 ret1 = calculate (nums[M], nums[N], ops[r]);
if (ret1 <= 0)
 continue;
for (s = 0; s < 4; s++)
 {
 ret2 = calculate (nums[J], ret1, ops[s]);
if (ret2 <= 0)
 continue;
for (t = 0; t < 4; t++)
 {
ret = calculate (nums[I], ret2, ops[t]);
if (((ret&MASK)==24) && ((ret>>SHIFT)==0))
 {
 sprintf (result, "%d%c(%d%c(%d%c%d))", 
 nums[I], ops[t], nums[J], ops[s],
 nums[M], ops[r], nums[N]);
 return SUCCESS;
 }
 }
 }
 }
 }
 }
 }
 }
return FAILURE;
}
/* 計算兩個特定的數和操作符的結果*/
int calculate (int num1, int num2, char op)
{
 int numerator_num1, numerator_num2;
 int denominator_num1, denominator_num2;
 int ret = 0;
 int denominator, numerator;
 denominator_num1 = num1 >> SHIFT; //分母
 denominator_num2 = num2 >> SHIFT;
 numerator_num1 = num1 & MASK; //分子
 numerator_num2 = num2 & MASK;
 /* 確定分母，將分子同一化*/
if (denominator_num1 > 0 && denominator_num2 > 0)
 {
 denominator = denominator_num1 * denominator_num2;
 numerator_num1 = denominator_num2 * numerator_num1;
 numerator_num2 = denominator_num1 * numerator_num2;
 }
else if (denominator_num1 > 0 && denominator_num2 == 0)
 {
 denominator = denominator_num1;
 numerator_num2 = denominator_num1 * numerator_num2;
 }
else if (denominator_num1 == 0 && denominator_num2 > 0)
 {
 denominator = denominator_num2;
 numerator_num1 = denominator_num2 * numerator_num1;
 }
else
 {
 denominator = 0;
 }
 /* 計算*/
if (op == '+')
 {
 numerator = numerator_num1 + numerator_num2;
 }
else if (op == '-')
 {
 numerator = numerator_num1 - numerator_num2;
 }
else if (op == '*')
 {
 numerator = numerator_num1 * numerator_num2;
 denominator *= denominator;
 }
else if (op == '/')
 {
if (numerator_num2 > 0 && numerator_num1%numerator_num2 == 0)
 {
 /* 分子可以整除，分母就沒有必要了。*/
 numerator = numerator_num1 / numerator_num2;
 denominator = 0;
 }
else
 {
 numerator = numerator_num1;
 denominator = numerator_num2;
 }
 }
if (denominator>0 && numerator%denominator == 0)
 {
 numerator = numerator / denominator;
 denominator = 0;
 }
 ret = (numerator<=0)?numerator:((numerator&MASK) | (denominator<<SHIFT));
 return ret;
}

通過上述算法代碼，計算了4個1～13之間的數（包含）是否能夠通過加減乘除達到結果為24。執行效果如圖15-1所示。

24點游戲執行效果