八皇后問題課程設(shè)計

1、<p><b>　　八皇后問題課程設(shè)計</b></p><p><b>　　1設(shè)計背景</b></p><p>　　1．1課程設(shè)計的目的</p><p>　　本課程設(shè)計的目的在于提高學(xué)生對數(shù)據(jù)結(jié)構(gòu)和C++語言課程的運(yùn)用能力，并能使學(xué)生加深對數(shù)據(jù)結(jié)構(gòu)和編程工作的理解。書本知識轉(zhuǎn)化成個人能力，最終還是要靠不斷地付諸實

2、踐，課程設(shè)計恰為這種時間提供了一個很好的平臺。</p><p>　　1.2課程設(shè)計任務(wù)與要求</p><p>　　程序啟動后顯示一張8*8的棋盤，然后游戲者可以用坐標(biāo)輸入方式在棋盤上布下棋子。如果布下的棋子合法，則增加10分并可以繼承布下一個棋子。如果布下的棋子不合法，給出游戲者的得分?jǐn)?shù)。</p><p>　　若無錯誤布下8顆棋子，則給與滿分100分。（由于本學(xué)期我

3、們尚未學(xué)習(xí)圖形界面的有關(guān)類容，所以課程設(shè)計中的有關(guān)圖形界面的內(nèi)容進(jìn)行了修改。）</p><p>　　游戲規(guī)則要求不能在同一行或同一列或同一條對角線上放置二個或二個以上的棋子，但每行都必須放置一個棋子。</p><p><b>　　2 程序的實現(xiàn)過程</b></p><p>　　2.1設(shè)計思想、算法及實現(xiàn)要點(diǎn)</p><p&g

4、t;　　程序編寫都是由簡單到復(fù)雜的，接到任務(wù)以后，就在腦子里有了一個大概的框架。一個while（1）的打循環(huán)里嵌套一個界面輸入程序，通過用戶不斷地輸入來控制游戲的循環(huán)的繼續(xù)和跳出，并且在設(shè)計一個自動跳出的判斷語句。這樣，玩家就能在循環(huán)體里不斷布棋，直到玩家想終止游戲或者游戲過關(guān)成功。</p><p>　　關(guān)于下棋系統(tǒng)，首先要處理的就是棋盤，我把棋盤用賦值為0或1的二維數(shù)組來模擬國際象棋棋盤。</p>

5、<p>　　0代表無棋子，1代表已下的棋子。這樣就比較方便我以后判斷棋盤橫豎斜有且只有一個棋子，只需將橫豎斜的元素累加，結(jié)果等于1即可。</p><p>　　由于沒有真正的圖形界面，下棋的方法就只能依靠用戶輸入橫豎坐標(biāo)了，輸入坐標(biāo)后，系統(tǒng)自動將該坐標(biāo)位置的元素賦值為1。</p><p>　　關(guān)于打分細(xì)則，我的設(shè)計是給一個基準(zhǔn)分20分，正確下一個棋就加10分，這樣，當(dāng)游戲過關(guān)時恰

6、好是100分。</p><p>　　具體到實際編程時，又考慮到，游戲程序的可玩性問題，我又在之前的的簡單框架上補(bǔ)充了悔棋的功能，并且能一次性悔多步棋子，這樣，打分細(xì)則又改變了：</p><p>　　起評分20分下對一顆棋子獎勵10分，若要悔棋，悔棋一步扣除15分。由于棧的特點(diǎn)是先進(jìn)后出，后進(jìn)先出，正好符合后下的棋子先悔，先下的棋后悔，于是我就很自然的想到建立一個簡單棧來存儲每一步玩家所走的

7、棋子。棧的內(nèi)容很簡單，只有壓入和彈出的函數(shù)，沒有過多防范數(shù)組越界、溢出等錯誤的處理。出錯問題由程序員負(fù)責(zé)。</p><p>　　剩下的就簡單了，用一個int類型的數(shù)記錄悔棋次數(shù)，評分系統(tǒng)就做好了。</p><p><b>　　2.2 程序的函數(shù)</b></p><p>　　程序主要有這幾個函數(shù)構(gòu)成void display()用來輸出模擬的八皇后

8、8*8棋盤； void display(int ,int)這是對上一個函數(shù)的重載，這樣就允許先將一個特定位置的元素賦值為1，然后在輸出；bool deal()對棋盤進(jìn)行橫、豎、斜等方面的處理，將棋盤的橫、豎、斜三條線上元素求和，當(dāng)這些和里面有值大于1時，說明至少有一對換后發(fā)生沖突，此時返回false,反之則返回true; v

9、oid Main()是整個游戲的核心函數(shù)，里面設(shè)計了一個while（k），k是走棋的個數(shù)，所以k>0,該循環(huán)通常情況下無法終止，所以提示用戶下棋的頁面會一直循環(huán)出現(xiàn)，知道玩家成功闖關(guān)或者玩家提示想終止程序。</p><p><b>　　2.3系統(tǒng)測試</b></p><p>　　系統(tǒng)測試的階段我主要做的就是進(jìn)行錯誤處理的工作，比如：</p><

10、;p>　　如果玩家輸入了不存在的錯誤坐標(biāo)，系統(tǒng)會提示：“坐標(biāo)錯誤！請您輸入1~8整數(shù)?！比缓笙到y(tǒng)會讓玩家更改輸入坐標(biāo)，如果輸入了如重復(fù)的坐標(biāo)，系統(tǒng)將會提示：“輸入坐標(biāo)重復(fù)，請重新輸入?！敝钡酵婕逸斎胝_的坐標(biāo)位置；在悔棋的時候，如果輸入的悔棋步數(shù)超過當(dāng)前步數(shù)，系統(tǒng)也會提示用戶正確輸入。并且各種提示信息都伴隨一個喇叭發(fā)音，引起玩家注意。</p><p>　　為了使界面看起來更加簡潔，每一次更新棋盤元素并輸出棋

11、盤之前，我都用了一個system(“CLS”)；的語句，使得整個游戲過程不會很撩人。</p><p><b>　　3 操作說明</b></p><p>　　整個游戲操作，用戶只需用數(shù)字鍵輸入棋子的坐標(biāo)或悔棋的步數(shù)，以及用N/Y鍵判斷是否悔棋。輸入錯誤數(shù)據(jù)都會有系統(tǒng)伴隨喇叭發(fā)音的提示，N/Y鍵也對大小寫進(jìn)行了處理。玩家可以很輕松的進(jìn)行游戲，不必?fù)?dān)心錯誤的輸入造成整個游戲

12、系統(tǒng)的崩潰。</p><p><b>　　4 總 結(jié)</b></p><p>　　通過這一個星期的編程，覺得自己對于對數(shù)據(jù)結(jié)構(gòu)和C++的編程運(yùn)用能力有了很大的提高，不僅對堆棧有了切身的體會，了解了它的方便與麻煩之處，也同時把C++語言重新溫習(xí)了一遍，鞏固了上學(xué)期所學(xué)的知識。</p><p>　　這次課程設(shè)計更令我意識到了數(shù)據(jù)結(jié)構(gòu)這一課程的

13、重要性，一個好的算法可依然程序更加簡單明了高效，試想如果是在上個學(xué)期然我們來編寫相同的程序，估計那程序可以想象會有多么的凌亂無序低效。</p><p><b>　　參考文獻(xiàn)</b></p><p>　　嚴(yán)蔚敏,吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語言版）[M].北京:清華大學(xué)出版社.1997:44-58</p><p>　　H.M.Deitel,P.J.Dei

14、tel.C++程序設(shè)計教程（第4版）[M].北京：清華大學(xué)出版社.2004:1-792</p><p><b>　　附錄</b></p><p><b>　　源程序如下：</b></p><p>　　#include <iostream></p><p>　　using namespac

15、e std;</p><p>　　///////////////建立一個簡單的棧/////////////////////////////////////////////////</p><p>　　class Stack</p><p><b>　　{</b></p><p>　　int mark[8];</p&

16、gt;<p><b>　　int *top;</b></p><p>　　// int *base;</p><p><b>　　public:</b></p><p><b>　　Stack()</b></p><p><b>　　{</

17、b></p><p>　　for(int i(0);i<=7;i++)mark[i]=-1;</p><p><b>　　top=mark;</b></p><p><b>　　} </b></p><p>　　void push(int e){*++top=e;}//向棧壓入一個元

18、素 </p><p>　　int get(){</p><p><b>　　int temp;</b></p><p>　　temp=*top;</p><p>　　*top--=-1;</p><p>　　return temp;}//彈出棧的一個元素 </p><p>

19、<b>　　};</b></p><p>　　////////////////////////////將棋盤轉(zhuǎn)換為一個二維數(shù)組////////////////////////////</p><p>　　int A[][8]={{0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0},</p><p

20、>　　{0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0},</p><p>　　{0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0}};</p><p>　　/////////////////////////////////////////////////////////////////////////////

21、///</p><p>　　void display();//輸出模擬的八皇后棋盤 </p><p>　　void display(int ,int);//display函數(shù)的重載 </p><p>　　void Main();//主體函數(shù) </p><p>　　bool deal();//對棋盤進(jìn)行橫、豎、斜等方面的處理</p>

22、<p>　　/////////////////////////主函數(shù)/////////////////////////////////////////////////</p><p>　　int main()</p><p><b>　　{ </b></p><p>　　display();</p><p&

23、gt;<b>　　Main();</b></p><p>　　system("pause");</p><p><b>　　return 0;</b></p><p><b>　　}</b></p><p>　　///////////////////////

24、////輸出象棋棋盤/////////////////////////////////////////</p><p>　　void display()</p><p><b>　　{</b></p><p>　　cout<<"當(dāng)前八皇后棋盤：\n";</p><p>　　for(int

25、i=0;i<=63;++i)//用一維方法處理二維數(shù)組</p><p><b>　　{</b></p><p>　　cout<<A[i/8][i%8]<<' ';</p><p>　　if(i%8==7)cout<<endl;</p><p><b>　

26、　}</b></p><p><b>　　}</b></p><p>　　///////////////////////////display函數(shù)的重載 ///////////////////////////////////</p><p>　　void display(int a,int b)</p><p&g

27、t;<b>　　{</b></p><p>　　cout<<"當(dāng)前八皇后棋盤：\n";</p><p>　　A[a][b]=1;</p><p>　　for(int i=0;i<=63;++i)//用一維方法處理二維數(shù)組 </p><p><b>　　{</b>

28、</p><p>　　cout<<A[i/8][i%8]<<' ';</p><p>　　if(i%8==7)cout<<endl;</p><p><b>　　}</b></p><p><b>　　}</b></p><p&

29、gt;　　//////////////////////////菜單函數(shù)//////////////////////////////////////////////</p><p>　　void Main()</p><p><b>　　{ </b></p><p>　　int k(1);//記錄當(dāng)前的步數(shù) </p><p&g

30、t;　　int x,y,judge(0);//橫豎坐標(biāo)及悔棋次數(shù) </p><p>　　Stack X,Y;//兩個棧分別記錄每次的橫豎坐標(biāo)輸入 </p><p><b>　　while(k){</b></p><p>　　while(1){//坐標(biāo)輸入及坐標(biāo)輸入的錯誤處理 </p><p>　　co

31、ut<<"請輸入第"<<k<<"個皇后的坐標(biāo)";</p><p>　　cin>>x>>y;</p><p>　　if((x<1||x>8)||(y<1||y>8))cout<<"\a坐標(biāo)錯誤！請您輸入1~8整數(shù)。\n";</p&g

32、t;<p>　　if(A[y-1][x-1]==1)cout<<"輸入坐標(biāo)重復(fù)，請重新輸入。\n";</p><p>　　else break;</p><p><b>　　}</b></p><p>　　X.push(x-1);</p><p>　　Y.push(y-1);

33、//橫縱坐標(biāo)入棧 </p><p>　　system("CLS");//清屏，使界面更加簡潔。 </p><p>　　display(y-1,x-1);</p><p>　　if(!deal()){</p><p>　　cout<<"游戲結(jié)束\n"<<"總得分：&quo

34、t;<<10*k+20-15*judge<<endl</p><p>　　<<"是否悔棋(Y/N)? (每步悔棋將扣除15分)\n";</p><p><b>　　char j;</b></p><p><b>　　cin>>j;</b></p>

35、;<p>　　if(j=='y'||j=='Y'){//輸入悔棋步數(shù)及錯誤處理 </p><p>　　cout<<"悔棋幾步？\n";</p><p><b>　　int i;</b></p><p><b>　　wh

36、ile(i){</b></p><p><b>　　cin>>i;</b></p><p>　　if(i>k||k<1)cout<<"\a請輸入1~"<<k<<"的悔棋數(shù)：\n";</p><p>　　else break;</

37、p><p>　　} </p><p><b>　　k=k-i;</b></p><p>　　for(int a(0);a<i;++a)//悔棋的實現(xiàn)，將坐標(biāo)置零 </p><p>　　A[Y.get()][X.get()]=0; </p><p>　　judge=judg

38、e+i; </p><p>　　system("CLS");</p><p>　　display();</p><p><b>　　}</b></p><p>　　else break;</p><p><b>　　};</b></p>&l

39、t;p><b>　　if(k==8){</b></p><p>　　cout<<"恭喜你過關(guān)，總得分："<<10*k+20-15*judge;</p><p><b>　　break;</b></p><p><b>　　}</b></p>

40、<p><b>　　k++;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　////////////////////////對棋盤進(jìn)行計算//////////////////////////////////////////&l

41、t;/p><p>　　bool deal()</p><p><b>　　{</b></p><p>　　int temp0[8]={0}/*橫排上元素之和*/,temp1[8]={0}/*豎直線上的元素之和*/,</p><p>　　temp2[15]={0}/*右斜線上的元素之和*/,temp3[15]={0}/*左斜線

42、上的元素之和*/;</p><p>　　//橫排上元素求和的實現(xiàn)</p><p>　　for(int i(0);i<=7;++i)</p><p>　　for(int j(0);j<=7;++j)</p><p>　　temp0[i]+=A[i][j];</p><p>　　//豎直線上求和計算的實現(xiàn) &l

43、t;/p><p>　　for(int i(0);i<=7;++i)</p><p>　　for(int j(0);j<=7;++j)</p><p>　　temp1[i]+=A[j][i];</p><p>　　//斜線上求和計算的實現(xiàn) </p><p>　　for(int i(0);i<=7;++i)&

44、lt;/p><p>　　for(int j(0);j<=7;++j)</p><p><b>　　{</b></p><p>　　//右斜線上求和計算的實現(xiàn) </p><p>　　if(j+i>=8);</p><p>　　else temp2[i]+= A[j+i][j];</p

45、><p>　　if(j>i||i>6);</p><p>　　else temp2[i+8]+=A[j][7-i+j]; </p><p>　　//左斜線上求和計算的實現(xiàn)</p><p><b>　　if(i<j);</b></p><p>

46、　　else temp3[i]+=A[i-j][j];</p><p>　　if(i+j+1>7);</p><p>　　else temp3[i+8]+=A[7-j][i+j+1]; </p><p><b>　　}</b></p><p>　　//如果橫、豎、斜排元素和有一個大于1，則當(dāng)前

47、皇后至少于之前一個皇后有沖突，返回false. </p><p>　　for(int i(0);i<=14;++i) </p><p><b>　　{</b></p><p>　　if(temp0[i/2]>1||temp1[i/2]>1||temp2[i]>1||temp3[i]>1)</p>&l

48、t;p>　　return false;</p><p><b>　　}</b></p><p>　　return true;</p><p><b>　　}</b></p><p>　　//////////////////////////////////////////////////////