游戲24點課程設(shè)計報告

1、 游戲24點課程設(shè)計報告一.題目:分析類:計算24點：任意輸入4位數(shù)字，利用+,-,*,/四則運算使之得到結(jié)果 24。輸出所有不同算法的計算表達(dá)式，可為運算優(yōu)先級而使用括號。二.問題分析：1.全面性：此問題要求輸出結(jié)果為24的計算表達(dá)式，并且要求輸出要全面，我考慮用for循環(huán)與遞歸實現(xiàn)遍歷來保證輸出的全面性，考慮到遞歸的一歸到底,每一次完整遞歸都代表一種算法(詳情見算法)。2.輸出的判定和四位數(shù)字的類型：在輸出的時候?qū)ψ詈蠼Y(jié)果等于24的判別，因為考慮到有除法，有可能中途結(jié)果可能會出現(xiàn)不能整除的情況與小數(shù)，所以輸出的四個數(shù)都設(shè)為float型，且輸出判定的時候用近似判定法，而不直接寫讓最后結(jié)果等于

2、24(詳情見算法)。3.重復(fù)性：如果用循環(huán)與遞歸保證了輸出24的表達(dá)式的全面性，但不可避免的會出現(xiàn)重復(fù)，才開始我想在遍歷與遞歸時，加一些限定條件來消除重復(fù)但是這樣做不但會出錯，還不能保證它的輸出全面性。于是我想在輸出的時候加限定條件，使重復(fù)的只輸出一遍。但是對于輸入的那4位數(shù)字中如果有重復(fù)的話，程序結(jié)果還是會出現(xiàn)重復(fù)的,此問題尚未解決.(詳情見算法)。4.括號問題的處理：對于括號問題，我規(guī)定對每一步的計算表達(dá)式，除了*之外，+，-,都加上括號，即讓程序按自己規(guī)定的方向執(zhí)行，輸出的括號只是讓人能看懂，其實在運算時不起作用(詳情見算法)。5.輸出：輸出方面我以為用了遍歷所以在每一層遍歷都把運算表達(dá)

3、式存到一個較大的數(shù)組中，在輸出的時候如果滿足輸出條件(在遍歷時紀(jì)錄每次遞歸的第一次運算的結(jié)果，第一次運算的運算符，第二次運算的結(jié)果，第二次運算的運算符和第三次運算的運算符)，就直接把那個數(shù)組里的內(nèi)容輸出，遍歷會直接去尋找表達(dá)式里的表達(dá)式(詳情見算法)。三.算法描述（源代碼里有更詳盡解釋）：1.主要方法：遍歷與遞歸。2.主要思路：把輸入的四個數(shù)放在一個數(shù)組n4中，然后任取其中任意兩個（不能取同一個-既不能出現(xiàn)自己和自己運算的情況），然后用一個for和一個switch語句來實現(xiàn)這兩個數(shù)的加減乘除運算， 然后把運算的結(jié)果放到另一個數(shù)組b4中并記錄此運算的表達(dá)式（放到一個大一點的數(shù)組tm425中），同

4、時把其他兩個沒用到的數(shù)也放到該數(shù)組中，然后重復(fù)以上過程（用遍歷實現(xiàn)），最后先判定是不是最后一層運算，是的話在判定最后結(jié)果是不是等于24，等于24的話就把那個紀(jì)錄運算式的數(shù)組輸出。然后考慮到不能出現(xiàn)重復(fù)的（例如：1*2*3*4和2*4*3*1等等）我在遍歷的同時記錄了第一次運算的結(jié)果，第一次運算的運算符，第二次運算的結(jié)果，第二次運算的運算符和第三次運算的運算符，對輸出的時候做限定（例如：對運算符全*的只輸出一遍等等）。在有一次輸出后我還定義了另外兩個數(shù)組用來分別保存上一次輸出的第一次運算的結(jié)果，第一次運算的運算符，第二次運算的結(jié)果，第二次運算的運算符和第三次運算的運算符，來解決重復(fù)輸出的問題，不

5、過此種做法有可能導(dǎo)致輸出的時候不全。（此問題尚未解決）即還不能同時保證全面性與不重復(fù)性。主要函數(shù)與數(shù)組：主要有兩個函數(shù)，一個主函數(shù)，用來輸入四個數(shù)，并且完成初始化。還有一個count(float a,char tem25,int n)函數(shù)，用來完成遍歷，遞歸，與輸出，其中a中存放要輸入的4個數(shù)，tem25中放計算步驟，n是a中元素的個數(shù)。在函數(shù)體內(nèi)還定義了b4和tm425用來完成遞歸，函數(shù)一開始先判定輸出條件（是否是第三次運算，結(jié)果是否等于24），如果不滿足條件就做遍歷與遞歸，遍歷用了3個for循環(huán)和1個switch語句來完成，然后為遞歸準(zhǔn)備數(shù)據(jù)，用sprintf函數(shù)將運算式輸出到數(shù)祖tm中，

6、在輸入運算式的同時把括號輸?shù)絫m中，然后提取第一次運算的運算符與運算結(jié)果，提取第二次運算的運算符與運算結(jié)果和提取第三次運算的運算符，然后備份沒用到的數(shù)據(jù)（為遞歸之用）。接下來進(jìn)行遞歸重復(fù)上述過程。4.算法流程圖：(簡化的流程圖，源代碼里有更詳盡解釋) 四.源代碼及其分析#include#include#include#include#include#include#define max 4;/最大輸入個數(shù)。int k=0;/全局變量 用來判定是否有解char tp4=0,0,0,0,tpt2000=0,tptt2000=0,tre2000=0;/用來消除重復(fù)。tp1-3用來記錄運算式中的3個運

7、算符。char op4=+,*,-,/;void count(float a,char tem25,int n);/a中存放要輸入的4個數(shù)，tem25中放計算步驟，n是a中元素的個數(shù)。int q=0,p=0,e=0,w=0,t=0,r=0,g=0,h=0,v=0,u=0,tu=0,te=0;/用于消除重復(fù)。float group2=0,0,flow20=0,flo20=0;/tem25中放計算步驟，n是a中元素的個數(shù)。void main() char br=1; int d;while (br=1) float number4;/放四個數(shù)。 char temp425; /放運算式，初始化放四個

8、數(shù)。 coutplease insert four numbers:; coutendl; for(d=0;dnumberd;/輸入四個數(shù) for(d=0;d4;d+) sprintf(tempd,%d,(int) numberd); /初始化tempd； count(number,temp,4);/調(diào)用count函數(shù)。 if (k=0) coutno answer; coutendl; coutpress 0 endendl; scanf (%d,&br); void count(float a,char tem25,int n)float b4;char tm425;/b4和t4作用同上（

9、為 遞歸之用）。int i,j,l,x,y;/i,j用來作雙循環(huán)；l用來作加減乘除的開關(guān)；x,y為后面準(zhǔn)備遞歸數(shù)據(jù)之用。/*/輸出部分if(n=1) if (fabs(a0-24)0.00001)/因為要考慮除法所以用fabs函數(shù)求絕對值與24比較。/相當(dāng)于等于24時的情況。 /*/以下是限定輸出條件：if(tp3=-&tp2=-&tp1=*) if(te=0)coutn有解為tem0=24;/最后的運算式存在tem0中k=1;te=1;/對運算符全*的只輸出一遍。else if(tp3=+&(tp2=+|tp0=+)&tp1=+) if(t=0)coutn有解為tem0=24;/最后的運算式

10、存在tem0中k=1;t=1;/對運算符全+的只輸出一遍。else if(tp3=+&(tp2=*|tp0=*)&tp1=+) if(g=0)coutn有解為tem0=24;/最后的運算式存在tem0中k=1;g=1;else if(tp3=-&tp2=+)|(tp3=+&tp2=-)if(w=0)coutn有解為tem0=24;/最后的運算式存在tem0中k=1;w=1;/對于第二次運算時取到b0時，第一第二個運算符是+,-或-，+的只輸出一遍。else if(tp3=+&tp2=+) if(u=0)coutn有解為tem0=24;/最后的運算式存在tem0中k=1;u=1;/對于第二次運算

11、時取到b0時，第一第二個運算符是+,+的只輸出一遍else if(tp3=*&tp2=*)if(r=0)coutn有解為tem0=24;/最后的運算式存在tem0中k=1;r=1;else if(tp3=*&tp0=*&tp1=+)if(tu=0)coutn有解為tem0=24;/最后的運算式存在tem0中k=1;tu=1;else for(h=0;hq;h+)if(group0=flowh) if(tp3=tpth) if(tp2=tptth)if(group1=floh)if(p=0) coutn有解為tem0=24;/最后的運算式存在tem0中k=1;p=1; else if(h=q-1

12、) coutn有解為tem01)/該條件語句用來結(jié)束一次遞歸。for(i=0;in;i+)/對n個 數(shù)做+,*,-,/遍歷。for(j=0;jn;j+)if(i=j) continue;for(l=0;l4;l+)/進(jìn)行四則運算。switch(l)case(0): if(n=2)b0=a0+a1;break; else b0=ai+aj;break;case(1):if(n=2) b0=a0*a1;break;elseb0=ai*aj;break; /對加和乘做遍歷時去除ai+aj與aj+ai等情況。case(2): b0=ai-aj;break;case(3):if(aj=0)break;

13、b0=ai/aj;break; /對-和/做遍歷時考慮ai-aj與aj-ai的不同。default:break;/switchif(l!=3|aj!=0)/為遞歸準(zhǔn)備數(shù)據(jù)(把沒用到的數(shù)也放到b與tm中)。 if(l=0|l=2|l=3) /用sprintf函數(shù)將運算式輸出到數(shù)祖tm中。/在輸入運算式的同時把括號輸?shù)絫m中。sprintf(tm0,(%s%c%s),temi,opl,temj); if(l=1) sprintf(tm0,%s%c%s,temi,opl,temj);if(n=3)/提取第一次運算的運算符與運算結(jié)果。group1=b0; if(i!=0&j!=0)tp0=opl; e

14、lsetpn-1=opl;else if(n=4)/提取第二次運算的運算符與運算結(jié)果。tpn-1=opl;group0=b0;else /提取第三次運算的運算符。 tpn-1=opl;for(x=0,y=1;xn;x+)/備份沒用到的數(shù)據(jù)（為遞歸之用）。 if(x!=i&x!=j) by=ax; strcpy(tmy,temx);/復(fù)制字符串。 y+; /if /for/ifcount(b,tm,n-1);/第三層for循環(huán)結(jié)束。/第二層for循環(huán)結(jié)束。/for循環(huán)結(jié)束。/if 結(jié)束。/count函數(shù)結(jié)束。五.運行數(shù)據(jù)測試1輸入數(shù)據(jù)（以空格分開）2回車后出運行結(jié)果3按0退出六.心得體會設(shè)計本程序，起因于兒時的游戲24點，游戲簡單富有思考價值。程序數(shù)據(jù)結(jié)構(gòu)是用的樹，每一片葉子代表一種算法，從根開始為一個結(jié)點（第一層，第一次計算有48種情況，所以第二層有48個結(jié)點，第二次計算有24種情況，所以第三層有48*24個結(jié)點，即第二層的每一個結(jié)點有24個分支，最后一次計算有兩種情況，所以第三層的每