24點(diǎn)游戲算法
在現(xiàn)實(shí)項(xiàng)目開(kāi)發(fā)應(yīng)用中，游戲方面的應(yīng)用程序比較受歡迎，在軟件產(chǎn)業(yè)中占據(jù)了很大的比例。例如24點(diǎn)游戲是一個(gè)棋牌類(lèi)益智游戲，要求結(jié)果等于24。在本節(jié)中，將詳細(xì)講解C語(yǔ)言實(shí)現(xiàn)24點(diǎn)游戲的算法。
實(shí)例15-2 編程實(shí)現(xiàn)24點(diǎn)游戲
問(wèn)題描述：編寫(xiě)實(shí)現(xiàn)24點(diǎn)游戲的C語(yǔ)言程序。
算法分析：其實(shí)24點(diǎn)游戲是用4個(gè)數(shù)字經(jīng)過(guò)數(shù)學(xué)運(yùn)行，并得到結(jié)果是24的過(guò)程。大多數(shù)版本應(yīng)該使用撲克的52張牌（大小王除外），A表示1，K表示13，看任意4張牌是否能夠組合得到24。在將4個(gè)數(shù)進(jìn)行四則運(yùn)算時(shí)，一般的思維是在4個(gè)數(shù)中間的3個(gè)空放置3個(gè)運(yùn)算符，然后需要在不同的地方加上括號(hào)表示優(yōu)先級(jí)的不同。如果僅僅是數(shù)字和運(yùn)算符則很好實(shí)現(xiàn)，一旦要添加括號(hào)就會(huì)變得比較難了。但是后綴表達(dá)式可以實(shí)現(xiàn)無(wú)括號(hào)的優(yōu)先級(jí)運(yùn)算，那么此處使用后綴表達(dá)式的這種方法來(lái)實(shí)現(xiàn)就比較簡(jiǎn)單了。
在此假設(shè)I、J、M、N是4個(gè)數(shù)，r、s、t是3個(gè)運(yùn)算符。那么使用后綴表達(dá)式只有如下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種總計(jì)有6144種可能。假如每種情況計(jì)算3次，也就20000次計(jì)算而已，對(duì)計(jì)算機(jī)來(lái)說(shuō)這個(gè)數(shù)目是極小的。在實(shí)現(xiàn)應(yīng)用中，沒(méi)有采用任何取巧的辦法，而是每種情況使用了7個(gè)for循環(huán)進(jìn)行計(jì)算。唯一的取巧是前兩種的前邊4個(gè)for循環(huán)是一樣，可以將這兩種拼接起來(lái)。
在處理整數(shù)計(jì)算時(shí)會(huì)面對(duì)一個(gè)問(wèn)題，計(jì)算機(jī)無(wú)法精確地表示分?jǐn)?shù)，特別是那種無(wú)限小數(shù)，比如1/3這種。如果不能精確計(jì)算，最后就無(wú)法判斷是否精確等于24，這是計(jì)算機(jī)的一個(gè)弱點(diǎn)。此處的解決方法是，每個(gè)數(shù)字都用一個(gè)int表示，int表示為4字節(jié)。由于最大的單個(gè)數(shù)為13，那么即使是13的連乘也不過(guò)28561，不足兩個(gè)字節(jié)能表示的65536。因此使用一個(gè)int的低兩個(gè)字節(jié)表示分子或者實(shí)際的數(shù)值（沒(méi)有分母，也就等于整個(gè)int表示的數(shù)），高兩個(gè)字節(jié)表示分母（不存在分母則表示為0）。在做計(jì)算時(shí)將分子統(tǒng)一為等分母的數(shù)，然后計(jì)算之后與分母作用得到最后的數(shù)。根據(jù)上述描述，4/5就表示為0x00050004。
因?yàn)檎业揭环N解法就結(jié)束，所以根據(jù)輸入的數(shù)據(jù)，得到的可能與人工計(jì)算得到的結(jié)果有出入，比如2 2 6 6，人工計(jì)算結(jié)果一般為2*6+2*6，但是程序結(jié)果可能為(2+6)*(6/2)，當(dāng)然結(jié)果也是正確的。另外還需要注意的是，對(duì)于任何兩個(gè)數(shù)計(jì)算得到負(fù)數(shù)，并沒(méi)有繼續(xù)向下計(jì)算，因?yàn)檫@個(gè)必須得加一個(gè)正數(shù)或者乘以一個(gè)負(fù)數(shù)才可能等于24。而既然能夠得到負(fù)數(shù)，兩個(gè)數(shù)的位置調(diào)換一下就是一個(gè)正數(shù)了，沒(méi)有必要在數(shù)值前邊加上負(fù)號(hào)來(lái)處理。
具體實(shí)現(xiàn)：編寫(xiě)實(shí)例文件15-2.c，具體實(shí)現(xiàn)代碼如下所示。
#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 ("所有的數(shù)字都應(yīng)該是1到13正整數(shù)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;
}
/* 測(cè)試所有可能的情況，找到一種解法*/
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;
}
/* 計(jì)算兩個(gè)特定的數(shù)和操作符的結(jié)果*/
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;
}
/* 計(jì)算*/
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)
{
/* 分子可以整除，分母就沒(méi)有必要了。*/
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;
}
通過(guò)上述算法代碼，計(jì)算了4個(gè)1～13之間的數(shù)（包含）是否能夠通過(guò)加減乘除達(dá)到結(jié)果為24。執(zhí)行效果如圖15-1所示。
24點(diǎn)游戲執(zhí)行效果
