計(jì)算24點(diǎn) 數(shù)據(jù)結(jié)構(gòu)

1、目 錄課程設(shè)計(jì)任務(wù)書 -1=課程設(shè)計(jì)任務(wù)書學(xué)生姓名： 趙旭林 專業(yè)班級(jí)： 計(jì)算機(jī)科學(xué)與技術(shù)0801 指導(dǎo)教師： 楊克 工作單位： 計(jì)算機(jī)科學(xué)系 題 目: 計(jì)算24點(diǎn) 初始條件：有2、3、4、5、6、7、8、9、10、J、Q、K、A共13張牌，編一程序，判斷對(duì)任意給定的4張牌，能否在進(jìn)行加、減、乘、除運(yùn)算后，其運(yùn)算結(jié)果等于24。其中J按11計(jì)算，Q按12計(jì)算，K按13計(jì)算，A按1計(jì)算。（1）能接受用戶輸入的4張牌點(diǎn)，并進(jìn)行24點(diǎn)判斷，并輸出判定結(jié)果。（2）若能得到結(jié)果24，要求輸出至少一個(gè)可得到該結(jié)果的計(jì)算表達(dá)式。 例如，對(duì)給定的2，7，J，Q，按下述方法計(jì)算可得到結(jié)果24： (J-7)*(Q/

2、2) 或 Q*(J-2-7) （3）若不能得到24點(diǎn)，亦應(yīng)輸出提示。要求完成的主要任務(wù): （包括課程設(shè)計(jì)工作量及其技術(shù)要求，以及說明書撰寫等具體要求）課程設(shè)計(jì)報(bào)告按學(xué)校規(guī)定格式用A4紙打?。〞鴮懀?yīng)包含如下內(nèi)容： 1. 問題描述簡述題目要解決的問題是什么。2. 設(shè)計(jì)存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)、主要算法設(shè)計(jì)（用類C/C+語言或用框圖描述）、測試用例設(shè)計(jì)；3. 調(diào)試報(bào)告調(diào)試過程中遇到的問題是如何解決的；對(duì)設(shè)計(jì)和編碼的討論和分析。4. 經(jīng)驗(yàn)和體會(huì)（包括對(duì)算法改進(jìn)的設(shè)想）5. 附源程序清單和運(yùn)行結(jié)果。源程序要加注釋。如果題目規(guī)定了測試數(shù)據(jù)，則運(yùn)行結(jié)果要包含這些測試數(shù)據(jù)和運(yùn)行輸出。說明：1. 設(shè)計(jì)報(bào)告、程序不得相

3、互抄襲和拷貝；若有雷同，則所有雷同者成績均為0分。2. 凡拷貝往屆任務(wù)書或課程設(shè)計(jì)充數(shù)者，成績一律無效，以0分記。時(shí)間安排：1、第18周完成。2、7月2日8:30時(shí)到實(shí)驗(yàn)中心檢查程序、交課程設(shè)計(jì)報(bào)告、源程序（U盤）。指導(dǎo)教師簽名： 2010年 月 日系主任（或責(zé)任教師）簽名： 2010年 月 日數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)正文 -計(jì)算24點(diǎn)1. 問題描述在A、2、3、4、5、6、7、8、9、10、J、Q、K中任意選擇4個(gè)數(shù)，通過這4個(gè)數(shù)進(jìn)行任意+ 、- 、*、 /的運(yùn)算（這四個(gè)數(shù)可以任意排列），而且可以添加需要的“（）”來進(jìn)行先后運(yùn)算?？词欠衲軌虻玫揭粋€(gè)計(jì)算式，使得其結(jié)果為24。如果有，則輸出所有的計(jì)算式

4、，如果沒有，則輸出相應(yīng)的提示。例如，對(duì)給定的2，7，J，Q，按下述方法計(jì)算可得到結(jié)果24，并且輸出下列的表達(dá)式： (J-7)*(Q/2)=24 Q*(J-2-7)=24 由于輸入有A、J、Q、K字符型數(shù)據(jù)，所以把輸入數(shù)據(jù)存放在char字符型數(shù)組中，并且在程序內(nèi)部定義一個(gè)數(shù)組，把輸入的字符型數(shù)據(jù)一一轉(zhuǎn)換為相對(duì)應(yīng)的int整型，其中A代表為1，J代表為11，Q代表為12，K代表為13。約束條件：輸入的4個(gè)數(shù)不能為重復(fù)，如果重復(fù)，則輸出錯(cuò)誤提示，并要求重新輸入。而且輸入的數(shù)不能在所要求的數(shù)之外，如果輸入了不在輸入范圍內(nèi)的數(shù)，則也應(yīng)該輸出相應(yīng)錯(cuò)誤提示，并要求重新輸入。2.實(shí)驗(yàn)設(shè)計(jì)2.1 算法設(shè)計(jì)：采用窮

5、舉法，把所有可能的情況一一計(jì)算，如果計(jì)算式得到24，則把相應(yīng)的計(jì)算式輸出；假設(shè)選擇A B C D四張牌，#代表操作符，則有以下五種情況： 1.(A#B)#C)#D 2.(A#B)#(C#D) 3.(A#(B#C)#D 4.A#(B#C)#D) 5.A#(B#(C#D)把這些計(jì)算式都變成兩兩計(jì)算的情況，因此可以把一個(gè)計(jì)算式分成三個(gè)由兩個(gè)運(yùn)算數(shù)組合而成的計(jì)算式。其中的“#”可以是+、-、*、/ 中的任何一種運(yùn)算，并且可以重復(fù)。A、B、C、D不能重復(fù)。由于按照以上的方法，ABCD的順序固定，從而導(dǎo)致有一些情況不能被計(jì)算在內(nèi)，所以需要列舉出ABCD所有可能的排序狀況，再將A B C D所有的排列組合一

6、一按照上面的五個(gè)計(jì)算式計(jì)算。這樣就能把所有有可能的情況都包含進(jìn)去，不會(huì)漏掉某個(gè)有可能得到24點(diǎn)的算法。對(duì)四個(gè)數(shù)沒進(jìn)行完一次排序，則對(duì)新的排序序列進(jìn)行24點(diǎn)計(jì)算式比較，如果有計(jì)算式，則輸出所有的計(jì)算式，如果沒有，則輸出提示。現(xiàn)在程序外定義一些全局變量：cal r,w,t;/三個(gè)操作符類char data10;/輸入的數(shù)據(jù)int _data10;/把牌轉(zhuǎn)化為數(shù)字之后存放的數(shù)組bool find=false;/如果find為false，則代表沒有24點(diǎn)計(jì)算式，如果為true，則代表有主函數(shù)偽碼設(shè)計(jì)為：int main()tranput();/輸入數(shù)據(jù)；tran();/轉(zhuǎn)換數(shù)據(jù)；trandata();

7、/處理數(shù)據(jù)；if(find=false)/如果沒有能得到24點(diǎn)的計(jì)算式，輸出提示；return 0;定義4個(gè)函數(shù)，分別完成相對(duì)應(yīng)的功能。void tranput();/作用是讓用戶輸入選擇的牌；void tran();/把字符型的輸入轉(zhuǎn)換為對(duì)應(yīng)的數(shù)字，A代表1，J代表11，Q代表12，K代表13；void look();/對(duì)于4張牌的一個(gè)組合尋找能得出點(diǎn)的表達(dá)式；void trandata();/列出所選擇4張牌的所有可能排列情況，再對(duì)每種情況進(jìn)行l(wèi)ook()操作；2.2 偽碼設(shè)計(jì) 存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)，定義一個(gè)cal類，目的是重載操作符。重載函數(shù)返回經(jīng)過重載后操作符運(yùn)算的結(jié)果。cal類偽碼：clas

8、s cal /操作符類，重載操作符public:char s; /s為操作符cal()double operator()(double a,double b) /重載操作符switch(s)判斷s，對(duì)不同的s返回不同的結(jié)果；;tranput()函數(shù)偽碼：void tranput()for(int i=0;i<4;i+)輸入datai;定義一個(gè)判斷型數(shù)組judge；do把輸入的數(shù)與判斷型數(shù)組進(jìn)行一一比較，如果不屬于數(shù)組里面的，則輸出輸入錯(cuò)誤提示；while();for(int j=i-1;j>=0;j-)將正確的當(dāng)前輸入與之前輸入相比較，如果相同代表重復(fù)輸入，輸出錯(cuò)誤提示；look(

9、)函數(shù)偽碼：void look()定義數(shù)組char,存放+、-、*、/四種運(yùn)算符for(int i=0;i<4;i+)/不同組合的操作符 選擇一種運(yùn)算符；for(int i=0;i<4;i+)選擇一種運(yùn)算符；for(int i=0;i<4;i+)選擇一種運(yùn)算符；一一對(duì)五種表達(dá)式進(jìn)行判斷，如果行，則把find值為true；trandata()偽碼：void trandata() char temp10; for(int i=0;i<4;i+) 四重循環(huán)，對(duì)ABCD進(jìn)行排列組合，并對(duì)每一種排列進(jìn)行l(wèi)ook（）操作； 2.3 算法分析： 由于有4個(gè)輸入，且在計(jì)算的時(shí)候這4個(gè)數(shù)

10、不能重復(fù)出現(xiàn)，所有共有4！=4*3*2*1=24種排 列的情況。而對(duì)于操作符而言，共有+、-、*、/四種操作符，而在一個(gè)計(jì)算式里面操作符顯然可以重復(fù) 出重復(fù)出現(xiàn)。對(duì)操作符進(jìn)行全排列，4*4*4*一共有256種排列狀況?？傮w分析，在輸入一組數(shù)據(jù)后 后，如果要得出由這組數(shù)據(jù)形成的24點(diǎn)表達(dá)式，則要進(jìn)行256*24=6144次比較后才能得出所有的計(jì)算式。2.4 測試用例設(shè)計(jì) 1.K K 7 7; /錯(cuò)誤例子，用來檢測程序健壯性； 2.10 5 6 7; 3.A 6 9 K; 4.Q 7 9 K; 5.R 14 5 K; /錯(cuò)誤例子，用來檢測程序健壯性；3.程序調(diào)試1.剛開始調(diào)試時(shí)，輸入數(shù)據(jù)7，9，J

11、,K出現(xiàn)計(jì)算式：（K/（7/J）+9=24，表達(dá)式錯(cuò)誤，經(jīng)過檢查，發(fā)現(xiàn)在if(t(w(data0,r(data1,_data2),_data3)=24)24點(diǎn)判斷式中把_data0,data1寫成了data0,data1,改正后結(jié)果顯示：沒有相應(yīng)的表達(dá)式。2.剛開始直接定義一個(gè)整型數(shù)組（int data），結(jié)果由于輸入有可能是A J Q K字符型，所以不能通過整型數(shù)組來記錄所有的輸入。因此把int data改為char data,因?yàn)閏har型占一個(gè)字符，此時(shí)能夠正確記錄19和A、J、Q、K,但不能記錄10，每次輸入10的時(shí)候總是判斷為非法輸入。嘗試把char data換為string dat

12、a，結(jié)果出現(xiàn)： c:usersadministratordocumentsvisual studio 2008projects24點(diǎn)24點(diǎn)24點(diǎn).cpp(7) : error C2679: 二進(jìn)制“>>”: 沒有找到接受“std:string”類型的右操作 數(shù)的運(yùn)算符(或沒有可接受的轉(zhuǎn)換) c:programfilesmicrosoftvisualstudio9.0vcincludeistream(1144): “std:basic_istream<_Elem,_Traits>&std:operator >><std:char_traits&l

13、t;char>>(std:basic_istream<_Elem,_Traits> &,signed char *)” with _Elem=char, _Traits=std:char_traits<char> 不知道怎么調(diào)試，所以只能在輸入的時(shí)候提示用戶用#來代表10的輸入；例如：輸入5，7，#，K（5，7，10，K） 得到下列的結(jié)果：(5-K)*(7-#)=24 (7-#)*(5-K)=24 (#-7)*(K-5)=24(K-5)*(#-7)=243.因?yàn)檫\(yùn)算符有交換率，不同的表達(dá)式有可能表達(dá)相同的意思。所以在程序的輸出中有很大一部分結(jié)果是重復(fù)

14、的。例如，輸入3，7，9，K,結(jié)果為：（7*9)-(K*3)=24 (7*9)-(3*K)=24(9*7)-(K*3)=24(9*7)-(3*K)=24 這四個(gè)表達(dá)式代表相同的意思，可以用其中任意一個(gè)計(jì)算式代表其他，但目前為止還沒有想出來好的辦法來進(jìn)行重復(fù)計(jì)算式的判斷。4.實(shí)驗(yàn)結(jié)果與分析1.K K 7 7 結(jié)果為：結(jié)果分析：輸入第一個(gè)K，符合要求，輸入第二個(gè)K，與第一個(gè)重復(fù)，輸出錯(cuò)誤提示，后面同理。程序繼續(xù)等待輸入正確數(shù)字。 2.10 5 6 7（#，5，6，7）; 結(jié)果為： 結(jié)果分析：為正確輸入，沒有相應(yīng)的24點(diǎn)計(jì)算式。3.A 6 9 K;結(jié)果為： 結(jié)果分析：有相當(dāng)多的計(jì)算式，不過其中有很多

15、重復(fù)。4.Q 7 9 K;結(jié)果為： 結(jié)果分析：和第二組數(shù)據(jù)一樣，沒有相應(yīng)的24點(diǎn)計(jì)算式。5.R 14 5 K 結(jié)果為：結(jié)果分析：由于R和14不在輸入范圍里面，所以導(dǎo)致錯(cuò)誤提示。程序繼續(xù)等待輸入正確數(shù)字。5.經(jīng)驗(yàn)和體會(huì) 這次的的課程設(shè)計(jì)使我收獲了很多平時(shí)上課和做練習(xí)不能得到的經(jīng)驗(yàn)，并且讓我對(duì)編程有了更加深入的了解，激發(fā)了我對(duì)編程的興趣。1.程序設(shè)計(jì)要求程序員要有很清晰的思路和很好的耐心。在拿到題目后，首先應(yīng)該對(duì)題目進(jìn)行仔細(xì)的分析，清楚的明白題目的要求、約束條件等等。然后再進(jìn)行算法的設(shè)計(jì)。2在進(jìn)行算法的設(shè)計(jì)時(shí)，往往會(huì)有很多不同的思路來解決相同的一個(gè)問題。此時(shí)要對(duì)比這些思路，看看哪一個(gè)更適用于目前的算法，哪一個(gè)更簡潔，更容易理解，綜合所有的分析來選擇一個(gè)相對(duì)來說更好的算法來進(jìn)行編程。這樣不僅能夠節(jié)省大量的編程、調(diào)試時(shí)間，而且更容易理解，更能提升自己對(duì)編程的興趣。3.在編程時(shí)候應(yīng)該很仔細(xì)，很小心，對(duì)于一般的語法錯(cuò)誤應(yīng)該盡量避免。同時(shí)對(duì)于一些模棱兩可的想法應(yīng)該盡快查閱書本