數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告--馬攔過河卒問題

1、<p><b>　　計(jì)算機(jī)科學(xué)與技術(shù)系</b></p><p><b>　　課程設(shè)計(jì)報(bào)告</b></p><p>　　2013 ～2014 學(xué)年第(二) 學(xué)期</p><p><b>　　2013 年6月</b></p><p>　　數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)報(bào)告</p

2、><p>　　目 錄</p><p><b>　　課程設(shè)計(jì)目的</b></p><p><b>　　內(nèi)容概要</b></p><p><b>　　關(guān)鍵詞</b></p><p><b>　　正文</b></p&

3、gt;<p><b>　　1、問題分析和任務(wù)</b></p><p>　　數(shù)據(jù)結(jié)構(gòu)的選擇和概要設(shè)計(jì)</p><p><b>　　詳細(xì)設(shè)計(jì)和編碼</b></p><p><b>　　上機(jī)調(diào)試</b></p><p><b>　　測(cè)試結(jié)果及其分析</b

4、></p><p><b>　　用戶使用說明</b></p><p><b>　　參考文獻(xiàn)</b></p><p><b>　　附錄</b></p><p><b>　　心得體會(huì)</b></p><p><b>　　

5、鳴謝 </b></p><p><b>　　課程設(shè)計(jì)目的:</b></p><p>　　“數(shù)據(jù)結(jié)構(gòu)與算法”精品課程建設(shè)組根據(jù)“數(shù)據(jù)結(jié)構(gòu)與算法”課程教學(xué)大綱的要求，精心選擇了一批課程設(shè)計(jì)題目，要求學(xué)生選擇其中的題目，通過獨(dú)立解決這些問題，在數(shù)據(jù)結(jié)構(gòu)的邏輯特性和物理表示、數(shù)據(jù)結(jié)構(gòu)的選擇應(yīng)用、算法的設(shè)計(jì)及其實(shí)現(xiàn)等方面加深對(duì)課程基本內(nèi)容的理解和綜合運(yùn)用，按“課、程

6、設(shè)計(jì)教學(xué)大綱”的要求完成“數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)報(bào)告”。使學(xué)生深刻理、解、牢固掌握數(shù)據(jù)結(jié)構(gòu)和算法設(shè)計(jì)技術(shù)，提高分析和解決實(shí)際問題的能力。在程序設(shè)計(jì)方法以及上機(jī)操作等基本技能和科學(xué)作風(fēng)方面受到比較系統(tǒng)和嚴(yán)格的訓(xùn)練</p><p><b>　　內(nèi)容概要: </b></p><p>　　棋盤上A點(diǎn)有一個(gè)過河卒，需要走到目標(biāo)B點(diǎn)。卒行走的規(guī)則：可以向下、或者向右。同時(shí)在棋盤上

7、C點(diǎn)有一個(gè)對(duì)方的馬，該馬所在的點(diǎn)和所有跳躍一步可達(dá)的點(diǎn)稱為對(duì)方馬的控制點(diǎn)。因此稱之為“馬攔過河卒”。</p><p>　　棋盤用坐標(biāo)表示，A點(diǎn)(0, 0)、B點(diǎn)(n, m)(n, m為不超過13的整數(shù))，同樣馬的位置坐標(biāo)是需要給出的。要求計(jì)算出卒從A點(diǎn)能夠到達(dá)B點(diǎn)的路徑的條數(shù)，假設(shè)馬的位置是固定不動(dòng)的，并不是卒走一步馬走一步。</p><p>　　關(guān)鍵詞:馬過河,遞歸法,回溯法,數(shù)組…….

8、</p><p><b>　　正文:</b></p><p>　　一、問題分析和任務(wù)定義</p><p><b>　　圖1-1 坐標(biāo)軸</b></p><p>　　A點(diǎn)有一個(gè)過河卒，需要走到目標(biāo)B點(diǎn)。卒行走的規(guī)則：可以向下、或者向右。同時(shí)在棋盤上的任一點(diǎn)有一個(gè)對(duì)方的馬（如上圖1-1的C點(diǎn)），該馬所在

9、的點(diǎn)和所有跳躍一步可達(dá)的點(diǎn)稱為方馬的控制點(diǎn)。例如上圖C點(diǎn)上的馬可以控制9個(gè)點(diǎn)（圖中的P1，P2...P8和C）。卒不能通過對(duì)方的控制點(diǎn)。</p><p>　　棋盤用坐標(biāo)表示，A點(diǎn)（0，0）、B點(diǎn)（n, m）(n,m為不超過13的整數(shù)，并由鍵盤輸入)，同樣馬 的位置坐標(biāo)是需要給出的（約定：C≠A，同時(shí)C≠B）?，F(xiàn)在要求你計(jì)算出卒從A點(diǎn)能夠到達(dá)B點(diǎn)的路徑的條數(shù)。做一個(gè)表，記錄馬可以攻擊的位置，主要要包括馬本身的位置；

10、然后從（0，0）開始每次遞歸（x+1,y）和（x，y+1），如何(x==n1&&y==n2)說明走到位置了，那么k++（路徑數(shù)）；如果大于邊界和等于馬可以攻擊的位置就return，這樣就可以了。不說考慮速度關(guān)系，我們可以加一個(gè)過程，即坐標(biāo)一旦超出目標(biāo)就return。</p><p>　　二、數(shù)據(jù)結(jié)構(gòu)的選擇和概要設(shè)計(jì)</p><p>　　做一個(gè)表，記錄馬可以攻擊的位置，主要要

11、包括馬本身的位置；然后從（0，0）開始每次遞歸（x+1,y）和（x，y+1），如何(x==n1&&y==n2)說明走到位置了，那么k++（路徑數(shù)）；如果大于邊界和等于馬可以攻擊的位置就return，這樣就可以了。不說考慮速度關(guān)系，我們可以加一個(gè)剪枝過程，即坐標(biāo)一旦超出目標(biāo)就return。</p><p><b>　　圖1-2 坐標(biāo)軸</b></p><p&

12、gt;<b>　　三、詳細(xì)設(shè)計(jì)和編碼</b></p><p>　　1、卒行走的規(guī)則：可以向下、或者向右。</p><p>　　2、計(jì)算馬的控制點(diǎn) </p><p>　　按照題意，對(duì)方的馬所在的點(diǎn)和所有跳躍一步可達(dá)的點(diǎn)稱為對(duì)方馬的控制點(diǎn)，卒不能通過對(duì)方馬的控制點(diǎn)。在卒出發(fā)之前，必須計(jì)算對(duì)方馬的所有控制點(diǎn)。顯然，若（0，0）或（n,m）為控制點(diǎn)，則

13、輸出路徑數(shù)為0。</p><p>　　3、假設(shè)馬的位置是固定不動(dòng)的，并不是卒走一步馬走一步。所以從這去計(jì)算路徑數(shù)。</p><p>　　使用遞歸的方法，記錄馬可以攻擊的位置</p><p>　　if(c<=X&&d<=Y) a[c][d]=0;</p><p>　　if(c-1>=0)

14、 //馬不能在x坐標(biāo)最邊緣的點(diǎn)</p><p><b>　　{</b></p><p>　　if(d+2<=Y) a[c-1][d+2]=0;</p><p>　　if(d-2>=0) a[c-1][d-2]=0; //查看馬是否能夠攻擊到</p><p><b>　　}<

15、/b></p><p>　　if(c+1<=X) //馬向右移動(dòng)一個(gè)坐標(biāo)，判斷與x的關(guān)系</p><p><b>　　{</b></p><p>　　if(d+2<=Y) a[c+1][d+2]=0;</p><p>　　if(d-2>=0) a[c+1][d-2]=

16、0; //查看馬是否能夠攻擊到</p><p><b>　　} </b></p><p>　　if(c-2>=0) //馬不能在y坐標(biāo)為1的點(diǎn)</p><p><b>　　{</b></p><p>　　if(d-1>=0) a[c-2][d-1]

17、=0;</p><p>　　if(d+1<=Y) a[c-2][d+1]=0; //查看馬是否能夠攻擊到</p><p><b>　　}</b></p><p>　　if(c+2<=X) //馬向右移動(dòng)2個(gè)坐標(biāo)，判斷與x的關(guān)系</p><p><b>　　{&

18、lt;/b></p><p>　　if(d-1>=0) a[c+2][d-1]=0;</p><p>　　if(d+1<=Y) a[c+2][d+1]=0; //查看馬是否能夠攻擊到</p><p><b>　　}</b></p><p>　　四、上機(jī)調(diào)試情況記錄</p><

19、;p><b>　　對(duì)算法的性能分析</b></p><p>　　該算法在進(jìn)行運(yùn)算時(shí)，存儲(chǔ)結(jié)果用到一個(gè)二維數(shù)組，而且當(dāng)使用完之后，就將初始化，因此不會(huì)像數(shù)組那樣浪費(fèi)太多的空間，除此之外，還用到一個(gè)遞歸的思想，不過該算法的時(shí)間復(fù)雜度有點(diǎn)小，，不是那么的大，函數(shù)中主要運(yùn)用了遞歸語句，尤其是在一般情況運(yùn)算中，用遞歸的方法，最終實(shí)現(xiàn)得到結(jié)果。時(shí)間復(fù)雜度為O（n^2）。</p>&l

20、t;p>　　在調(diào)試的時(shí)候遇到了一些問題：</p><p>　　（1）、程序調(diào)試過程中常會(huì)出現(xiàn)一些小錯(cuò)誤，如少括號(hào)少分號(hào)等小問題都可以按照提示找到，然后改正。</p><p>　?。?）、語句錯(cuò)誤語句使用不當(dāng)造成程序無法運(yùn)行出正常的結(jié)果。</p><p>　?。?）、一開始，不會(huì)出項(xiàng)了好多錯(cuò)誤，沒有考慮到特殊情況。我的數(shù)據(jù)結(jié)構(gòu)學(xué)的不好，后來問了幾個(gè)同學(xué)，又參考了

21、借來的一些書后，才會(huì)，那個(gè)確實(shí)好難。</p><p>　?。?）、對(duì)于遞歸的一些運(yùn)算，都會(huì)用到我們以前學(xué)到的C語言里的知識(shí)，因此還算簡(jiǎn)單，程序能夠完成。 </p><p>　　(5)我寫的這個(gè)程序可能過于簡(jiǎn)單，程序量很小，還請(qǐng)老師原諒。但都能實(shí)現(xiàn)任務(wù)書的要求。</p><p>　　五、測(cè)試用例、結(jié)果及其分析</p><p>　　圖2-1 運(yùn)行

22、后，程序調(diào)試</p><p>　　運(yùn)行程序，輸入數(shù)據(jù)，運(yùn)行成功。如圖2-1。</p><p>　　圖2-2運(yùn)行后，程序調(diào)試</p><p>　　每次輸入數(shù)據(jù)都需要重新運(yùn)行一下程序，所以在原來程序的基礎(chǔ)上加入大循環(huán)，可以多次使用，最后用判斷語句是否為0，來結(jié)束函數(shù)。見圖2-2。</p><p>　　圖2-3 程序出現(xiàn)錯(cuò)誤的情況</p>

23、;<p>　　用判斷語句是否為0，來結(jié)束函數(shù)。結(jié)果發(fā)現(xiàn)語句發(fā)錯(cuò)誤，重新修改判斷函數(shù)，見圖2-3。</p><p>　　圖2-4 程序?qū)崿F(xiàn)所有的功能</p><p>　　修改判斷語句函數(shù)成功，程序能夠?qū)崿F(xiàn)功能。見圖2-4。</p><p><b>　　六、用戶使用說明</b></p><p>　　本程序運(yùn)行過

24、程時(shí)帶有提示性語句。由于本程序可以對(duì)任意一個(gè)符合條件的數(shù)進(jìn)行計(jì)算</p><p>　　，所以運(yùn)行開始時(shí)根據(jù)提示輸入要輸入的數(shù)據(jù)。注意在這里提醒一下，由于程序的時(shí)間復(fù)雜度很高所以為了比較快的得到結(jié)果，建議輸入的數(shù)據(jù)最好在10以下。本程序在運(yùn)行過程中可能出現(xiàn)一個(gè)問題，即輸入一個(gè)數(shù)據(jù)后程序一直在運(yùn)行，請(qǐng)不要關(guān)閉該程序，此程序會(huì)在一段較長的時(shí)間的運(yùn)算得到你要的結(jié)果。本程序運(yùn)行過程時(shí)帶有提示性語句。由于本程序?qū)點(diǎn)到B點(diǎn)的

25、路徑數(shù)計(jì)算，所以開始得輸入馬的坐標(biāo)和B點(diǎn)的坐標(biāo)（A點(diǎn)位坐標(biāo)原點(diǎn)），本程序要求的B點(diǎn)的坐標(biāo)a,b都不能 超過13.，輸入坐標(biāo)時(shí)需注意。輸入坐標(biāo)盡量考慮特殊情況，這樣可以知道程序的正確性。本程序基本還是很簡(jiǎn)單，能夠快速運(yùn)行。</p><p><b>　　七、參考文獻(xiàn)</b></p><p>　　[1] 王昆侖，李紅. 數(shù)據(jù)結(jié)構(gòu)與算法. 北京：中國鐵道出版社，2006年5月

26、。</p><p>　　[2] 徐孝凱.數(shù)據(jù)結(jié)構(gòu)實(shí)用教程.北京：清華大學(xué)出版社。1999年12月第一版 。</p><p>　　[3] Bjarne Stroustrup.C++程序設(shè)計(jì)語言（特別版）。機(jī)械工業(yè)出版社。2002 年</p><p><b>　　[4] 其它。</b></p><p>　　八、附錄（完整源程

27、序）</p><p>　　#include"stdio.h"</p><p>　　int k=0,s1=1;</p><p>　　int a[16][16];</p><p>　　int X,Y,c,d;</p><p>　　void fun(int i,int j)</p><

28、p><b>　　{</b></p><p>　　if(i==X&&j==Y)</p><p><b>　　{</b></p><p><b>　　k++;</b></p><p><b>　　}</b></p><

29、p>　　if(i+1<=X&&a[i+1][j]) fun(i+1,j); </p><p>　　if(j+1<=Y&&a[i][j+1]) fun(i,j+1); //馬不能到達(dá) ，判斷i是否到達(dá)x，j是否到達(dá)y</p><p><b>　　}</b></p><p>　　in

30、t main()</p><p><b>　　{</b></p><p><b>　　int s,t;</b></p><p><b>　　while(1){</b></p><p>　　printf("卒的坐標(biāo)是:");</p><p&

31、gt;　　scanf("%d",&X);</p><p>　　scanf("%d",&Y); //接收卒的坐標(biāo)</p><p>　　printf("馬的坐標(biāo)是:");</p><p>　　scanf("%d",&c);</p>

32、<p>　　scanf("%d",&d); //接收馬的坐標(biāo)</p><p>　　for(s=0;s<=X;s++)</p><p>　　for(t=0;t<=Y;t++)</p><p>　　a[s][t]=1; //以（0，0）到點(diǎn)（x，y）所形成的矩形的點(diǎn)都

33、賦值為1</p><p>　　if(c<=X&&d<=Y) a[c][d]=0;</p><p>　　if(c-1>=0) //馬不能在x坐標(biāo)最邊緣的點(diǎn)</p><p><b>　　{</b></p><p>　　if(d+2<=Y) a[c-1][

34、d+2]=0;</p><p>　　if(d-2>=0) a[c-1][d-2]=0;</p><p><b>　　}</b></p><p>　　if(c+1<=X) //馬向右移動(dòng)一個(gè)坐標(biāo)，判斷與x的關(guān)系</p><p><b>　　{</b></

35、p><p>　　if(d+2<=Y) a[c+1][d+2]=0;</p><p>　　if(d-2>=0) a[c+1][d-2]=0;</p><p><b>　　}</b></p><p>　　if(c-2>=0) //馬不能在y坐標(biāo)為1的點(diǎn)</p><

36、;p><b>　　{</b></p><p>　　if(d-1>=0) a[c-2][d-1]=0;</p><p>　　if(d+1<=Y) a[c-2][d+1]=0;</p><p><b>　　}</b></p><p>　　if(c+2<=X)

37、 //馬向右移動(dòng)2個(gè)坐標(biāo)，判斷與x的關(guān)系</p><p><b>　　{</b></p><p>　　if(d-1>=0) a[c+2][d-1]=0;</p><p>　　if(d+1<=Y) a[c+2][d+1]=0;</p><p><b>　　}</b></p&g

38、t;<p><b>　　fun(0,0);</b></p><p>　　printf("路徑的條數(shù)為:");</p><p>　　printf("%d\n",k);</p><p>　　printf("是否繼續(xù)？0--退出\n");</p><p>

39、;　　scanf("%d",&s);</p><p>　　if(s==0) break;</p><p><b>　　}</b></p><p><b>　　return 0;</b></p><p><b>　　}</b></p>&

40、lt;p><b>　　心得體會(huì):</b></p><p>　　本次的數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)針對(duì)具體的實(shí)際項(xiàng)目來進(jìn)行問題分析，數(shù)據(jù)結(jié)構(gòu)的選擇和概要設(shè)計(jì)，詳細(xì)設(shè)計(jì)，測(cè)試分析等具體的步驟流程走下來，從中我收獲了很多 經(jīng)過一周的課程設(shè)計(jì)，有很多的心得體會(huì)。</p><p>　　首先，在編寫函數(shù)之前仔細(xì)的將本次課程設(shè)計(jì)的題目看懂，其次，根據(jù)題目要求考慮用數(shù)據(jù)結(jié)構(gòu)中的那個(gè)知識(shí)點(diǎn)來

41、實(shí)現(xiàn)題目的要求。此次，我的課程設(shè)計(jì)題目比較簡(jiǎn)單，很容易理解，但是一開始還是把題目要達(dá)到的結(jié)果想錯(cuò)了，后來經(jīng)過一個(gè)同學(xué)的提點(diǎn)發(fā)現(xiàn)自己錯(cuò)了。將題目理解后，雖然不能用棧的思想來解決這個(gè)為題，但是用其他的數(shù)據(jù)結(jié)構(gòu)思想既簡(jiǎn)單又容易理解。在此次過程中，我發(fā)現(xiàn)了一些自己的不足：拿來一個(gè)題目，對(duì)于問題理解的有些不全面與偏差，直到在網(wǎng)上查詢后在正確知道了問題的根本所在；發(fā)現(xiàn)我編的程序，太亂沒有條理性，當(dāng)我有不會(huì)的問題打算詢問同學(xué)時(shí)，說我編的太亂，所以必須

42、慢慢改正，使程序具有科學(xué)性、條理性。</p><p>　　通過這次課程設(shè)計(jì)，我深刻認(rèn)識(shí)到算法在程序設(shè)計(jì)中的重要性，發(fā)現(xiàn)一個(gè)程序設(shè)計(jì)就是算法與數(shù)據(jù)結(jié)構(gòu)的結(jié)合體，在一個(gè)完整的程序中總是由若干個(gè)函數(shù)構(gòu)成的，這些相應(yīng)的函數(shù)體現(xiàn)了算法的基本思想。通過完成整個(gè)程序設(shè)計(jì)，對(duì)棧的使用掌握的更加熟練，加深了對(duì)數(shù)據(jù)結(jié)構(gòu)的理解和認(rèn)識(shí)。同時(shí)，由于我以前對(duì)于函數(shù)的遞歸調(diào)用掌握的不太熟練，通過此程序的完成，更進(jìn)一步的了解了函數(shù)的遞歸調(diào)用。

43、</p><p>　　此次課程設(shè)計(jì)，獲得了很多寶貴的經(jīng)驗(yàn)，特別是怎樣將理論與實(shí)踐相結(jié)合，把書本上的內(nèi)容應(yīng)用到我的程序中。怎樣使各個(gè)子函數(shù)實(shí)施其詳細(xì)功能，特別是各個(gè)子函數(shù)之間的調(diào)用，一定要相當(dāng)清晰達(dá)到相互協(xié)調(diào)的作用，其實(shí)，我的程序相比較簡(jiǎn)單，函數(shù)調(diào)用主要是遞歸調(diào)用。 </p><p>　　總之，通過這次課程設(shè)計(jì)，我對(duì)于將課本上的知識(shí)運(yùn)用到實(shí)際生活中的整個(gè)過程深有體會(huì)了，不像之前對(duì)知識(shí)單純的停