關(guān)于二十四點(diǎn)游戲的編程思路與基本算法


　　漫長(zhǎng)的假期對(duì)于我來(lái)說(shuō)總是枯燥無(wú)味的，閑來(lái)無(wú)聊便和同學(xué)玩起童年時(shí)經(jīng)常玩的二十四點(diǎn)牌游戲來(lái)。此游戲說(shuō)來(lái)簡(jiǎn)單，就是利用加減乘除以及括號(hào)將給出的四張牌組成一個(gè)值為24的表達(dá)式。但是其中卻不乏一些有趣的題目，這不，我們剛玩了一會(huì)兒，便遇到了一個(gè)難題——3、6、6、10（其實(shí)后來(lái)想想，這也不算是個(gè)太難的題，只是當(dāng)時(shí)我們的腦筋都沒(méi)有轉(zhuǎn)彎而已，呵呵）。

　　問(wèn)題既然出現(xiàn)了，我們當(dāng)然要解決。冥思苦想之際，我的腦中掠過(guò)一絲念頭——何不編個(gè)程序來(lái)解決這個(gè)問(wèn)題呢？文曲星中不就有這樣的程序嗎？所以這個(gè)想法應(yīng)該是可行。想到這里我立刻開(kāi)始思索這個(gè)程序的算法，最先想到的自然是窮舉法（后來(lái)發(fā)現(xiàn)我再也想不到更好的方法了，悲哀呀，呵呵），因?yàn)樵谶@學(xué)期我曾經(jīng)寫過(guò)一個(gè)小程序——計(jì)算有括號(hào)的簡(jiǎn)單表達(dá)式。只要我能編程實(shí)現(xiàn)四個(gè)數(shù)加上運(yùn)算符號(hào)所構(gòu)成的表達(dá)式的窮舉，不就可以利用這個(gè)計(jì)算程序來(lái)完成這個(gè)計(jì)算二十四點(diǎn)的程序嗎？確定了這個(gè)思路之后，我開(kāi)始想這個(gè)問(wèn)題的細(xì)節(jié)。 
首先窮舉的可行性問(wèn)題。我把表達(dá)式如下分成三類——
1、 無(wú)括號(hào)的簡(jiǎn)單表達(dá)式。
2、 有一個(gè)括號(hào)的簡(jiǎn)單表達(dá)式。
3、 有兩個(gè)括號(hào)的較復(fù)4、 雜表達(dá)式。
窮舉的開(kāi)始我對(duì)給出的四個(gè)數(shù)進(jìn)行排列，其可能的種數(shù)為4*3*2*1=24。我利用一個(gè)嵌套函數(shù)實(shí)現(xiàn)四個(gè)數(shù)的排列，算法如下:
/* ans[] 用來(lái)存放各種排列組合的數(shù)組 */
/* c[] 存放四張牌的數(shù)組 */
/* k[] c[]種四張牌的代號(hào)，其中k[I]=I+1。
用它來(lái)代替c[]做處理，考慮到c[]中有可能出現(xiàn)相同數(shù)的情況 */
/* kans[] 暫存生成的排列組合 */
/* j 嵌套循環(huán)的次數(shù) */
int fans(c,k,ans,kans,j)
int j,k[],c[];char ans[],kans[];
{ int i,p,q,r,h,flag,s[4],t[4][4];
for(p=0,q=0;p<4;p++)
{ for(r=0,flag=0;r if(k[p]!=kans[r]) flag++;
if(flag==j) t[j][q++]=k[p];
}
for(s[j]=0;s[j]<4-j;s[j]++)
{ kans[j]=t[j][s[j]];
if(j==3) { for(h=0;h<4;h++)
ans[2*h]=c[kans[h]-1]; /* 調(diào)整生成的排列組合在最終的表
達(dá)式中的位置 */
for(h=0;h<3;h++)
symbol(ans,h); /* 在表達(dá)式中添加運(yùn)算符號(hào) */
}
else { j++;
fans(c,k,ans,kans,j);
j--;
}
}
}

　　正如上面函數(shù)中提到的，在完成四張牌的排列之后，在表達(dá)式中添加運(yùn)算符號(hào)。由于只有四張牌，所以只要添加三個(gè)運(yùn)算符號(hào)就可以了。由于每一個(gè)運(yùn)算符號(hào)可重復(fù)，所以計(jì)算出其可能的種數(shù)為4*4*4=64種。仍然利用嵌套函數(shù)實(shí)現(xiàn)添加運(yùn)算符號(hào)的窮舉，算法如下:

/* ans[],j同上。sy[]存放四個(gè)運(yùn)算符號(hào)。h為表達(dá)式形式。*/
int sans(ans,sy,j,h)
char ans[],sy[];int j,h;
{ int i,p,k[3],m,n; char ktans[20];
for(k[j]=0;k[j]<4;k[j]++)
{ ans[2*j+1]=sy[k[j]]; /* 剛才的四個(gè)數(shù)分別存放在0、2、4、6位
這里的三個(gè)運(yùn)算符號(hào)分別存放在1、3、5位*/ 
if(j==2)
{ ans[5]=sy[k[j]];
/* 此處根據(jù)不同的表達(dá)式形式再進(jìn)行相應(yīng)的處理 */
}
else { j++; sans(ans,sy,j--,h); }
}
}

　　好了，接下來(lái)我再考慮不同表達(dá)式的處理。剛才我已經(jīng)將表達(dá)式分為三類，是因?yàn)樘砑尤齻€(gè)括號(hào)對(duì)于四張牌來(lái)說(shuō)肯定是重復(fù)的。對(duì)于第一種，無(wú)括號(hào)自然不用另行處理；而第二種情況由以下代碼可以得出其可能性有六種，其中還有一種是多余的。
for(m=0;m<=4;m+=2)
for(n=m+4;n<=8;n+=2)
　　這個(gè)for循環(huán)給出了添加一個(gè)括號(hào)的可能性的種數(shù)，其中m、n分別為添加在表達(dá)式中的左右括號(hào)的位置。我所說(shuō)的多余的是指m=0，n=8，也就是放在表達(dá)式的兩端。這真是多此一舉，呵呵！最后一種情況是添加兩個(gè)括號(hào)，我分析了一下，發(fā)現(xiàn)只可能是這種形式才不會(huì)是重復(fù)的——（a b）(c d)。為什么不會(huì)出現(xiàn)嵌套括號(hào)的情況呢？因?yàn)槿绻乔短桌ㄌ?hào)，那么外面的括號(hào)肯定是包含三個(gè)數(shù)字的（四個(gè)沒(méi)有必要），也就是說(shuō)這個(gè)括號(hào)里面包含了兩個(gè)運(yùn)算符號(hào)，而這兩個(gè)運(yùn)算符號(hào)是被另外一個(gè)括號(hào)隔開(kāi)的。那么如果這兩個(gè)運(yùn)算符號(hào)是同一優(yōu)先級(jí)的，則肯定可以通過(guò)一些轉(zhuǎn)換去掉括號(hào)（你不妨舉一些例子來(lái)試試），也就是說(shuō)這一個(gè)括號(hào)沒(méi)有必要；如果這兩個(gè)運(yùn)算符號(hào)不是同一優(yōu)先級(jí)，也必然是這種形式((a+-b)*/c)。而*和/在這幾個(gè)運(yùn)算符號(hào)中優(yōu)先級(jí)最高，自然就沒(méi)有必要在它的外面添加括號(hào)了。

　　綜上所述，所有可能的表達(dá)式的種數(shù)為24*64*（1+6+1）=12288種。哈哈，只有一萬(wàn)多種可能性（這其中還有重復(fù)），這對(duì)于電腦來(lái)說(shuō)可是小case喲！所以，對(duì)于窮舉的可行性分析和實(shí)現(xiàn)也就完成了。


　　接下來(lái)的問(wèn)題就是如何對(duì)有符號(hào)的簡(jiǎn)單表達(dá)式進(jìn)行處理。這是棧的一個(gè)著名應(yīng)用，那么什么是棧呢？棧的概念是從日常生活中貨物在貨棧種的存取過(guò)程抽象出來(lái)的，即最后存放入棧的貨物（堆在靠出口處）先被提取出去，符合“先進(jìn)后出，后進(jìn)先出”的原則。這種結(jié)構(gòu)猶如子彈夾。
在棧中，元素的插入稱為壓入（push）或入棧，元素的刪除稱為彈出（pop）或退棧。

　　棧的基本運(yùn)算有三種，其中包括入棧運(yùn)算、退棧運(yùn)算以及讀棧頂元素，這些請(qǐng)參考相關(guān)數(shù)據(jù)結(jié)構(gòu)資料。根據(jù)這些基本運(yùn)算就可以用數(shù)組模擬出棧來(lái)。

　　那么作為棧的著名應(yīng)用，表達(dá)式的計(jì)算可以有兩種方法。

　　第一種方法——
　　首先建立兩個(gè)棧，操作數(shù)棧OVS和運(yùn)算符棧OPS。其中，操作數(shù)棧用來(lái)記憶表達(dá)式中的操作數(shù)，其棧頂指針為topv，初始時(shí)為空，即topv=0；運(yùn)算符棧用來(lái)記憶表達(dá)式中的運(yùn)算符，其棧頂指針為topp，初始時(shí)，棧中只有一個(gè)表達(dá)式結(jié)束符，即topp=1，且OPS（1）=‘；’。此處的‘；’即表達(dá)式結(jié)束符。
　　然后自左至右的掃描待處理的表達(dá)式，并假設(shè)當(dāng)前掃描到的符號(hào)為W，根據(jù)不同的符號(hào)W做如下不同的處理：
1、 若W為操作數(shù)
2、 則將W壓入操作數(shù)棧OVS
3、 且繼續(xù)掃描下一個(gè)字符
4、 若W為運(yùn)算符
5、 則根據(jù)運(yùn)算符的性質(zhì)做相應(yīng)的處理：
(1)、若運(yùn)算符為左括號(hào)或者運(yùn)算符的優(yōu)先級(jí)大于運(yùn)算符棧棧頂?shù)倪\(yùn)算符(即OPS(top)),則將運(yùn)算符W壓入運(yùn)算符棧OPS，并繼續(xù)掃描下一個(gè)字符。
(2)、若運(yùn)算符W為表達(dá)式結(jié)束符‘；’且運(yùn)算符棧棧頂?shù)倪\(yùn)算符也為表達(dá)式結(jié)束符（即OPS(topp)=’;’），則處理過(guò)程結(jié)束，此時(shí)，操作數(shù)棧棧頂元素（即OVS（topv））即為表達(dá)式的值。
(3)、若運(yùn)算符W為右括號(hào)且運(yùn)算符棧棧頂?shù)倪\(yùn)算符為左括號(hào)（即OPS（topp）=’(‘)，則將左括號(hào)從運(yùn)算符棧談出，且繼續(xù)掃描下一個(gè)符號(hào)。
(4)、若運(yùn)算符的右不大于運(yùn)算符棧棧頂?shù)倪\(yùn)算符（即OPS(topp)），則從操作數(shù)棧OVS中彈出兩個(gè)操作數(shù)，設(shè)先后彈出的操作數(shù)為a、b，再?gòu)倪\(yùn)算符棧OPS中彈出一個(gè)運(yùn)算符，設(shè)為+，然后作運(yùn)算a+b,并將運(yùn)算結(jié)果壓入操作數(shù)棧OVS。本次的運(yùn)算符下次將重新考慮。

　　第二種方法——
　　首先對(duì)表達(dá)式進(jìn)行線性化，然后將線性表達(dá)式轉(zhuǎn)換成機(jī)器指令序列以便進(jìn)行求值。

　　那么什么是表達(dá)式的線性化呢？人們所習(xí)慣的表達(dá)式的表達(dá)方法稱為中綴表示。中綴表示的特點(diǎn)是運(yùn)算符位于運(yùn)算對(duì)象的中間。但這種表示方式，有時(shí)必須借助括號(hào)才能將運(yùn)算順序表達(dá)清楚，而且處理也比較復(fù)雜。

　　 1929年，波蘭邏輯學(xué)家Lukasiewicz提出一種不用括號(hào)的邏輯符號(hào)體系，后來(lái)人們稱之為波蘭表示法（Polish notation）。波蘭表達(dá)式的特點(diǎn)是運(yùn)算符位于運(yùn)算對(duì)象的后面，因此稱為后綴表示。在對(duì)波蘭表達(dá)式進(jìn)行運(yùn)算，嚴(yán)格按照自左至右的順序進(jìn)行。下面給出一些表達(dá)式及其相應(yīng)的波蘭表達(dá)式。
表達(dá)式 波蘭表達(dá)式
A-B AB-
（A-B）*C+D AB-C*D+
A*（B+C/D）-E*F ABCD/+*EF*-
（B+C）/（A-D） BC+AD-/

　　OK，所謂表達(dá)式的線性化是指將中綴表達(dá)的表達(dá)式轉(zhuǎn)化為波蘭表達(dá)式。對(duì)于每一個(gè)表達(dá)式，利用棧可以把表達(dá)式變換成波蘭表達(dá)式，也可以利用棧來(lái)計(jì)算波蘭表達(dá)式的值。

　　至于轉(zhuǎn)換和計(jì)算的過(guò)程和第一種方法大同小異，這里就不再贅述了。

　　下面給出轉(zhuǎn)換和計(jì)算的具體實(shí)現(xiàn)程序——

/* first函數(shù)給出各個(gè)運(yùn)算符的優(yōu)先級(jí)，其中=為表達(dá)式結(jié)束符 */
int first(char c)
{ int p;
switch(c)
{ case '*': p=2; break;
case '/': p=2; break;
case '+': p=1; break;
case '-': p=1; break;
case '(': p=0; break;
case '=': p=-1; break;
}
return(p);
}
/* 此函數(shù)實(shí)現(xiàn)中綴到后綴的轉(zhuǎn)換 */
/* M的值宏定義為20 */
/* sp[]為表達(dá)式數(shù)組 */
int mid_last()
{ int i=0,j=0; char c,sm[M];
c=s[0]; sm[0]='='; top=0;
while(c!='\0')
{ if(islower(c)) sp[j++]=c;
else switch(c)
{ case '+':
case '-':
case '*':
case '/': while(first(c)<=first(sm[top]))
sp[j++]=sm[top--];
sm[++top]=c; break;
case '(': sm[++top]=c; break;
case ')': while(sm[top]!='(')
sp[j++]=sm[top--];
top--; break;
default :return(1);
}
c=s[++i];
}
while(top>0) sp[j++]=sm[top--];
sp[j]='\0'; return(0);
}
/* 由后綴表達(dá)式來(lái)計(jì)算表達(dá)式的值 */
int calc()
{ int i=0,sm[M],tr; char c;
c=sp[0]; top=-1;
while(c!='\0')
{ if(islower(c)) sm[++top]=ver[c-'a'];/*在轉(zhuǎn)換過(guò)程中用abcd等來(lái)代替數(shù)，
這樣才可以更方便的處理非一位數(shù)， 
ver數(shù)組中存放著這些字母所代替的數(shù)*/
else switch(c)
{ case '+': tr=sm[top--]; sm[top]+=tr; break;
case '-': tr=sm[top--]; sm[top]-=tr; break;
case '*': tr=sm[top--]; sm[top]*=tr; break;
case '/': tr=sm[top--];sm[top]/=tr;break;
default : return(1);
}
c=sp[++i];
}
if(top>0) return(1);
else { result=sm[top]; return(0); }
}

　　這樣這個(gè)程序基本上就算解決了，回過(guò)頭來(lái)拿這個(gè)程序來(lái)算一算文章開(kāi)始的那個(gè)問(wèn)題。哈哈，算出來(lái)了，原來(lái)如此簡(jiǎn)單——（6-3）*10-6=24。

　　最后我總結(jié)了一下這其中容易出錯(cuò)的地方——

　　1、 排列的時(shí)候由于一個(gè)數(shù)只能出現(xiàn)一次， 所以必然有一個(gè)判斷語(yǔ)句。但是用什么來(lái)判斷，用大小顯然不行，因?yàn)橛锌赡苓@四個(gè)數(shù)中有兩個(gè)或者以上的數(shù)是相同的。我的方法是給每一個(gè)數(shù)設(shè)置一個(gè)代號(hào)，在排列結(jié)束時(shí)，通過(guò)這個(gè)代號(hào)找到這個(gè)數(shù)。

　　2、在應(yīng)用嵌套函數(shù)時(shí)，需仔細(xì)分析程序的執(zhí)行過(guò)程，并對(duì)個(gè)別變量進(jìn)行適當(dāng)?shù)恼{(diào)整（如j的值）,程序才能正確的執(zhí)行。

　　3、在分析括號(hào)問(wèn)題的時(shí)候要認(rèn)真仔細(xì)，不要錯(cuò)過(guò)任何一個(gè)可能的機(jī)會(huì)，也要盡量使程序變得簡(jiǎn)單一些。不過(guò)我的分析可能也有問(wèn)題，還請(qǐng)高手指點(diǎn)。 

　　4、在用函數(shù)對(duì)一個(gè)數(shù)組進(jìn)行處理的時(shí)候，一定要注意如果這個(gè)數(shù)組還需要再應(yīng)用，就必須將它先保存起來(lái)，否則會(huì)出錯(cuò)，而且是很嚴(yán)重的錯(cuò)誤。

　　5、在處理用戶輸入的表達(dá)式時(shí)，由于一個(gè)十位數(shù)或者更高位數(shù)是被分解成各位數(shù)存放在數(shù)組中，所以需對(duì)它們進(jìn)行處理，將它們轉(zhuǎn)化成實(shí)際的整型變量。另外，在轉(zhuǎn)化過(guò)程中，用一個(gè)字母來(lái)代替這個(gè)數(shù)，并將這個(gè)數(shù)存在一個(gè)數(shù)組中，且它在數(shù)組中的位置和代替它的這個(gè)字母有一定的聯(lián)系，這樣才能取回這個(gè)數(shù)。

　　6、由于在窮舉過(guò)程難免會(huì)出現(xiàn)計(jì)算過(guò)程中有除以0的計(jì)算，所以我們必須對(duì)calc函數(shù)種對(duì)于除的運(yùn)算加以處理，否則程序會(huì)因?yàn)槌鲥e(cuò)而退出（Divide by 0）。

　　7、最后一個(gè)問(wèn)題，本程序尚未解決。對(duì)于一些比較著名的題目，本程序無(wú)法解答。比如說(shuō)5、5、5、1或者8、8、3、3。這是由于這些題目在計(jì)算的過(guò)程用到了小數(shù)，而本程序并沒(méi)有考慮到小數(shù)。

　　最后，由于此文檔并沒(méi)有在寫程序的同時(shí)完成，所以難免因?yàn)橛洃浀牟铄e(cuò)和小弟水平的不足而有不少錯(cuò)誤，還望各位批評(píng)指正；或者你認(rèn)為我寫得還不夠清楚，你也可以給我來(lái)信討論。

小弟的程序可以從以下地址下載 


作者：檀銀兵
郵編：210016
聯(lián)系地址：江蘇省南京市御道街29號(hào)112信箱
電子郵件：muyunqiu@sina.com
個(gè)人主頁(yè)：http://wcfall.126.com
QQ:9403509（歡迎編程愛(ài)好者加我為好友）