游戲24點(diǎn)課程設(shè)計(jì)報(bào)告

游戲24點(diǎn)課程設(shè)計(jì)報(bào)告一.題目:分析類:計(jì)算24點(diǎn)：任意輸入4位數(shù)字，利用+,-,*,/四則運(yùn)算使之得到結(jié)果24。輸出所有不同算法的計(jì)算表達(dá)式，可為運(yùn)算優(yōu)先級(jí)而使用括號(hào)。二.問題分析：1.全面性：此問題要求輸出結(jié)果為24的計(jì)算表達(dá)式，并且要求輸出要全面，我考慮用for循環(huán)與遞歸實(shí)現(xiàn)遍歷來保證輸出的全面性，考慮到遞歸的‘一歸到底',每一次完整遞歸都代表一種算法(詳情見算法)。2.輸出的判定和四位數(shù)字的類型：在輸出的時(shí)候?qū)ψ詈蠼Y(jié)果等于24的判別，因?yàn)榭紤]到有除法，有可能中途結(jié)果可能會(huì)出現(xiàn)不能整除的情況與小數(shù)，所以輸出的四個(gè)數(shù)都設(shè)為float型，且輸出判定的時(shí)候用近似判定法，而不直接寫讓最后結(jié)果等于24(詳情見算法)。3.重復(fù)性：如果用循環(huán)與遞歸保證了輸出24的表達(dá)式的全面性，但不可避免的會(huì)出現(xiàn)重復(fù)，才開始我想在遍歷與遞歸時(shí)，加一些限定條件來消除重復(fù)但是這樣做不但會(huì)出錯(cuò)，還不能保證它的輸出全面性。于是我想在輸出的時(shí)候加限定條件，使重復(fù)的只輸出一遍。但是對(duì)于輸入的那4位數(shù)字中如果有重復(fù)的話，程序結(jié)果還是會(huì)出現(xiàn)重復(fù)的,此問題尚未解決.(詳情見算法)。4.括號(hào)問題的處理：對(duì)于括號(hào)問題，我規(guī)定對(duì)每一步的計(jì)算表達(dá)式，除了*之外，+，-,\都加上括號(hào)，即讓程序按自己規(guī)定的方向執(zhí)行，輸出的括號(hào)只是讓人能看懂，其實(shí)在運(yùn)算時(shí)不起作用(詳情見算法)。5.輸出：輸出方面我以為用了遍歷所以在每一層遍歷都把運(yùn)算表達(dá)式存到一個(gè)較大的數(shù)組中，在輸出的時(shí)候如果滿足輸出條件(在遍歷時(shí)紀(jì)錄每次遞歸的第一次運(yùn)算的結(jié)果，第一次運(yùn)算的運(yùn)算符，第二次運(yùn)算的結(jié)果，第二次運(yùn)算的運(yùn)算符和第三次運(yùn)算的運(yùn)算符)，就直接把那個(gè)數(shù)組里的內(nèi)容輸出，遍歷會(huì)直接去尋找表達(dá)式里的表達(dá)式(詳情見算法)。三.算法描述（源代碼里有更詳盡解釋）：1.主要方法：遍歷與遞歸。2.主要思路：把輸入的四個(gè)數(shù)放在一個(gè)數(shù)組n[4]中，然后任取其中任意兩個(gè)（不能取同一個(gè)--既不能出現(xiàn)自己和自己運(yùn)算的情況），然后用一個(gè)for和一個(gè)switch語句來實(shí)現(xiàn)這兩個(gè)數(shù)的加減乘除運(yùn)算，然后把運(yùn)算的結(jié)果放到另一個(gè)數(shù)組b[4]中并記錄此運(yùn)算的表達(dá)式（放到一個(gè)大一點(diǎn)的數(shù)組tm[4][25]中），同時(shí)把其他兩個(gè)沒用到的數(shù)也放到該數(shù)組中，然后重復(fù)以上過程（用遍歷實(shí)現(xiàn)），最后先判定是不是最后一層運(yùn)算，是的話在判定最后結(jié)果是不是等于24，等于24的話就把那個(gè)紀(jì)錄運(yùn)算式的數(shù)組輸出。然后考慮到不能出現(xiàn)重復(fù)的（例如：1*2*3*4和2*4*3*1等等）我在遍歷的同時(shí)記錄了第一次運(yùn)算的結(jié)果，第一次運(yùn)算的運(yùn)算符，第二次運(yùn)算的結(jié)果，第二次運(yùn)算的運(yùn)算符和第三次運(yùn)算的運(yùn)算符，對(duì)輸出的時(shí)候做限定（例如：對(duì)運(yùn)算符全*的只輸出一遍等等）。在有一次輸出后我還定義了另外兩個(gè)數(shù)組用來分別保存上一次輸出的第一次運(yùn)算的結(jié)果，第一次運(yùn)算的運(yùn)算符，第二次運(yùn)算的結(jié)果，第二次運(yùn)算的運(yùn)算符和第三次運(yùn)算的運(yùn)算符，來解決重復(fù)輸出的問題，不過此種做法有可能導(dǎo)致輸出的時(shí)候不全。（此問題尚未解決）即還不能同時(shí)保證全面性與不重復(fù)性。３．主要函數(shù)與數(shù)組：主要有兩個(gè)函數(shù)，一個(gè)主函數(shù)，用來輸入四個(gè)數(shù)，并且完成初始化。還有一個(gè)count(floata[],chartem[][25],intn)函數(shù)，用來完成遍歷，遞歸，與輸出，其中a[]中存放要輸入的4個(gè)數(shù)，tem[][25]中放計(jì)算步驟，n是a[]中元素的個(gè)數(shù)。在函數(shù)體內(nèi)還定義了b[4]和tm[4][25]用來完成遞歸，函數(shù)一開始先判定輸出條件（是否是第三次運(yùn)算，結(jié)果是否等于24），如果不滿足條件就做遍歷與遞歸，遍歷用了3個(gè)for循環(huán)和1個(gè)switch語句來完成，然后為遞歸準(zhǔn)備數(shù)據(jù)，用sprintf函數(shù)將運(yùn)算式輸出到數(shù)祖tm[]中，在輸入運(yùn)算式的同時(shí)把括號(hào)輸?shù)絫m[]中，然后提取第一次運(yùn)算的運(yùn)算符與運(yùn)算結(jié)果，提取第二次運(yùn)算的運(yùn)算符與運(yùn)算結(jié)果和提取第三次運(yùn)算的運(yùn)算符，然后備份沒用到的數(shù)據(jù)（為遞歸之用）。接下來進(jìn)行遞歸重復(fù)上述過程。4.算法流程圖：(簡(jiǎn)化的流程圖，源代碼里有更詳盡解釋)四.源代碼及其分析#include<iostream.h>#include<math.h>#include<string.h>#include<stdio.h>#include<conio.h>#include<stdlib.h>#defineMAX4;//最大輸入個(gè)數(shù)。intk=0;//全局變量用來判定是否有解chartp[4]={0,0,0,0},tpt[2000]={0},tptt[2000]={0},tre[2000]={0};//用來消除重復(fù)。tp[1-3]用來記錄運(yùn)算式中的3個(gè)運(yùn)算符。charop[4]={'+','*','-','/'};voidcount(floata[],chartem[][25],intn);//a[]中存放要輸入的4個(gè)數(shù)，tem[][25]中放計(jì)算步驟，n是a[]中元素的個(gè)數(shù)。intq=0,p=0,e=0,w=0,t=0,r=0,g=0,h=0,v=0,u=0,tu=0,te=0;//用于消除重復(fù)。floatgroup[2]={0,0},flow[20]={0},flo[20]={0};////tem[][25]中放計(jì)算步驟，n是a[]中元素的個(gè)數(shù)。voidmain(){charbr=1;intd;while(br==1){floatnumber[4];//放四個(gè)數(shù)。chartemp[4][25];//放運(yùn)算式，初始化放四個(gè)數(shù)。cout<<"pleaseinsertfournumbers:";cout<<endl;for(d=0;d<4;d++)cin>>number[d];//輸入四個(gè)數(shù)for(d=0;d<4;d++){ sprintf(temp[d],"%d",(int)number[d]);}//初始化temp[d]；count(number,temp,4);//調(diào)用count函數(shù)。if(k==0) cout<<"noanswer";cout<<endl;cout<<"press0end"<<endl;scanf("%d",&br);}}voidcount(floata[],chartem[][25],intn){ floatb[4]; chartm[4][25];//b[4]和t[4][]作用同上（為遞歸之用）。 inti,j,l,x,y;//i,j用來作雙循環(huán)；l用來作加減乘除的開關(guān)；x,y為后面準(zhǔn)備遞歸數(shù)據(jù)之用。/************************************************************************************/ //輸出部分 if(n==1) { if(fabs(a[0]-24)<0.00001)//因?yàn)橐紤]除法所以用fabs函數(shù)求絕對(duì)值與24比較。 //相當(dāng)于等于24時(shí)的情況。 { /************************************************************************************///以下是限定輸出條件： if(tp[3]=='-'&&tp[2]=='-'&&tp[1]=='*') { if(te==0) { cout<<"\n有解為"<<tem[0]<<"=24";//最后的運(yùn)算式存在tem[0]中 k=1; te=1; } }//對(duì)運(yùn)算符全*的只輸出一遍。 elseif(tp[3]=='+'&&(tp[2]=='+'||tp[0]=='+')&&tp[1]=='+') { if(t==0) { cout<<"\n有解為"<<tem[0]<<"=24";//最后的運(yùn)算式存在tem[0]中 k=1; t=1; } }//對(duì)運(yùn)算符全+的只輸出一遍。 elseif(tp[3]=='+'&&(tp[2]=='*'||tp[0]=='*')&&tp[1]=='+') { if(g==0) { cout<<"\n有解為"<<tem[0]<<"=24";//最后的運(yùn)算式存在tem[0]中 k=1; g=1; } } elseif((tp[3]=='-'&&tp[2]=='+')||(tp[3]=='+'&&tp[2]=='-')) { if(w==0) { cout<<"\n有解為"<<tem[0]<<"=24";//最后的運(yùn)算式存在tem[0]中 k=1; w=1; } }//對(duì)于第二次運(yùn)算時(shí)取到b[0]時(shí)，第一第二個(gè)運(yùn)算符是+,-或-，+的只輸出一遍。 elseif(tp[3]=='+'&&tp[2]=='+'){ if(u==0) { cout<<"\n有解為"<<tem[0]<<"=24";//最后的運(yùn)算式存在tem[0]中 k=1; u=1; } }//對(duì)于第二次運(yùn)算時(shí)取到b[0]時(shí)，第一第二個(gè)運(yùn)算符是+,+的只輸出一遍 elseif(tp[3]=='*'&&tp[2]=='*') { if(r==0) { cout<<"\n有解為"<<tem[0]<<"=24";//最后的運(yùn)算式存在tem[0]中 k=1; r=1; } } elseif(tp[3]=='*'&&tp[0]=='*'&&tp[1]=='+') { if(tu==0) { cout<<"\n有解為"<<tem[0]<<"=24";//最后的運(yùn)算式存在tem[0]中 k=1; tu=1; } } else { for(h=0;h<q;h++) { if(group[0]==flow[h]) { if(tp[3]==tpt[h]) { if(tp[2]=tptt[h]) { if(group[1]==flo[h]) { if(p==0) { cout<<"\n有解為"<<tem[0]<<"=24";//最后的運(yùn)算式存在tem[0]中 k=1; p=1; } } } } } elseif(h==q-1) { cout<<"\n有解為"<<tem[0]<<"=24";//最后的運(yùn)算式存在tem[0]中 k=1; } } } flo[q]=group[1];//限定條件初始化。 flow[q] =group[0];//限定條件初始化。 tpt[q]=tp[3];//限定條件初始化。 tptt[q]=tp[2];//限定條件初始化。 tre[q]=tp[1];//限定條件初始化。 tp[0]=0; tp[1]=0; tp[2]=0; tp[3]=0; q=q+1; } }/************************************************************************************/ //運(yùn)算部分：if(n>1)//該條件語句用來結(jié)束一次遞歸。 { for(i=0;i<n;i++)//對(duì)n個(gè)數(shù)做'+','*','-','/'遍歷。 { for(j=0;j<n;j++) { if(i==j) continue; for(l=0;l<4;l++)//進(jìn)行四則運(yùn)算。 { switch(l) { case(0):if(n==2) { b[0]=a[0]+a[1]; break; } elseb[0]=a[i]+a[j]; break; case(1):if(n==2) { b[0]=a[0]*a[1]; break; } else b[0]=a[i]*a[j]; break; //對(duì)加和乘做遍歷時(shí)去除a[i]+a[j]與a[j]+a[i]等情況。 case(2): b[0]=a[i]-a[j]; break; case(3): if(a[j]==0) break; b[0]=a[i]/a[j]; break;//對(duì)'-'和'/'做遍歷時(shí)考慮a[i]-a[j]與a[j]-a[i]的不同。 default:break; }//switch if(l!=3||a[j]!=0)//為遞歸準(zhǔn)備數(shù)據(jù)(把沒用到的數(shù)也放到b[]與tm[]中)。 { {if(l==0||l==2||l==3)//用sprintf函數(shù)將運(yùn)算式輸出到數(shù)祖tm[]中。 //在輸入運(yùn)算式的同時(shí)把括號(hào)輸?shù)絫m[]中。 sprintf(tm[0],"(%s%c%s)",tem[i],op[l],tem[j]); if(l==1) sprintf(tm[0],"%s%c%s",tem[i],op[l],tem[j]); } {if(n==3)//提取第一次運(yùn)算的運(yùn)算符與運(yùn)算結(jié)果。 { group[1]=b[0]; if(i!=0&&j!=0) tp[0]=op[l]; else tp[n-1]=op[l]; } elseif(n==4)//提取第二次運(yùn)算的運(yùn)算符與運(yùn)算結(jié)果。 { tp[n-1]=op[l]; group[0]=b[0]; } else//提取第三次運(yùn)算的運(yùn)算符。 tp[n-1]=op[l];