課程設(shè)計(jì)報(bào)告馬攔過(guò)河卒問(wèn)題

1、合肥學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系課程設(shè)計(jì)報(bào)告2010 2011 學(xué)年第2學(xué)期課程 數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)題目名稱馬攔過(guò)河卒問(wèn)題學(xué)生姓名xxx學(xué)號(hào)xxx專業(yè)班級(jí)xxx指導(dǎo)教師xxx2011 年 6 月1、題目名稱：馬攔過(guò)河卒問(wèn)題內(nèi)容：棋盤(pán)上a點(diǎn)有一個(gè)過(guò)河卒，需要走到目標(biāo)b點(diǎn)。卒行走的規(guī)則：可以向下、或者向右。同時(shí)在棋盤(pán)上c點(diǎn)有一個(gè)對(duì)方的馬，該馬所在的點(diǎn)和所有跳躍一步可達(dá)的點(diǎn)稱為對(duì)方馬的控制點(diǎn)。因此稱之為“馬攔過(guò)河卒”。棋盤(pán)用坐標(biāo)表示，a點(diǎn)(0, 0)、b點(diǎn)(n, m)(n, m為不超過(guò)13的整數(shù))，同樣馬的位置坐標(biāo)是需要給出的。要求計(jì)算出卒從a點(diǎn)能夠到達(dá)b點(diǎn)的路徑的條數(shù)，假設(shè)馬的位置是固定不動(dòng)的，并不

2、是卒走一步馬走一步。2、問(wèn)題分析圖1-1 坐標(biāo)軸a點(diǎn)有一個(gè)過(guò)河卒，需要走到目標(biāo)b點(diǎn)。卒行走的規(guī)則：可以向下、或者向右。同時(shí)在棋盤(pán)上的任一點(diǎn)有一個(gè)對(duì)方的馬（如上圖1-1的c點(diǎn)），該馬所在的點(diǎn)和所有跳躍一步可達(dá)的點(diǎn)稱為方馬的控制點(diǎn)。例如上圖c點(diǎn)上的馬可以控制9個(gè)點(diǎn)（圖中的p1，p2.p8和c）。卒不能通過(guò)對(duì)方的控制點(diǎn)。棋盤(pán)用坐標(biāo)表示，a點(diǎn)（0，0）、b點(diǎn)（n, m）(n,m為不超過(guò)20的整數(shù)，并由鍵盤(pán)輸入)，同樣馬 的位置坐標(biāo)是需要給出的（約定：ca，同時(shí)cb）?，F(xiàn)在要求你計(jì)算出卒從a點(diǎn)能夠到達(dá)b點(diǎn)的路徑的條數(shù)。做一個(gè)表，記錄馬可以攻擊的位置，主要要包括馬本身的位置；然后從（0，0）開(kāi)始每次遞歸（

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

4、turn。4、算法思想圖1-2 坐標(biāo)軸 1、卒行走的規(guī)則：可以向下、或者向右。2、計(jì)算馬的控制點(diǎn) 按照題意，對(duì)方的馬所在的點(diǎn)和所有跳躍一步可達(dá)的點(diǎn)稱為對(duì)方馬的控制點(diǎn)，卒不能通過(guò)對(duì)方馬的控制點(diǎn)。在卒出發(fā)之前，必須計(jì)算對(duì)方馬的所有控制點(diǎn)。顯然，若（0，0）或（n,m）為控制點(diǎn)，則輸出路徑數(shù)為0。3、假設(shè)馬的位置是固定不動(dòng)的，并不是卒走一步馬走一步。所以從這去計(jì)算路徑數(shù)。5、詳細(xì)設(shè)計(jì)和主要編碼段使用遞歸的方法，記錄馬可以攻擊的位置if(c<=x&&d<=y) acd=0; if(c-1>=0) /馬不能在x坐標(biāo)最邊緣的點(diǎn) if(d+2<=y) ac-1d+2=

5、0; if(d-2>=0) ac-1d-2=0; /查看馬是否能夠攻擊到 if(c+1<=x) /馬向右移動(dòng)一個(gè)坐標(biāo)，判斷與x的關(guān)系 if(d+2<=y) ac+1d+2=0; if(d-2>=0) ac+1d-2=0; /查看馬是否能夠攻擊到 if(c-2>=0) /馬不能在y坐標(biāo)為1的點(diǎn) if(d-1>=0) ac-2d-1=0; if(d+1<=y) ac-2d+1=0; /查看馬是否能夠攻擊到 if(c+2<=x) /馬向右移動(dòng)2個(gè)坐標(biāo)，判斷與x的關(guān)系 if(d-1>=0) ac+2d-1=0; if(d+1<=y) ac+2

6、d+1=0; /查看馬是否能夠攻擊到 6、上機(jī)調(diào)試情況記錄對(duì)算法的性能分析該算法在進(jìn)行運(yùn)算時(shí)，存儲(chǔ)結(jié)果用到一個(gè)二維數(shù)組，而且當(dāng)使用完之后，就將初始化，因此不會(huì)像數(shù)組那樣浪費(fèi)太多的空間，除此之外，還用到一個(gè)遞歸的思想，不過(guò)該算法的時(shí)間復(fù)雜度有點(diǎn)小，不是那么的大，函數(shù)中主要運(yùn)用了遞歸語(yǔ)句，尤其是在一般情況運(yùn)算中，用遞歸的方法，最終實(shí)現(xiàn)得到結(jié)果。時(shí)間復(fù)雜度為o（n2）。在調(diào)試的時(shí)候遇到了一些問(wèn)題：（1）、程序調(diào)試過(guò)程中常會(huì)出現(xiàn)一些小錯(cuò)誤，如少括號(hào)少分號(hào)等小問(wèn)題都可以按照提示找到，然后改正。（2）、語(yǔ)句錯(cuò)誤語(yǔ)句使用不當(dāng)造成程序無(wú)法運(yùn)行出正常的結(jié)果。（3）、一開(kāi)始，不會(huì)出項(xiàng)了好多錯(cuò)誤，沒(méi)有考慮到特殊情況

7、。我的數(shù)據(jù)結(jié)構(gòu)學(xué)的不好，后來(lái)問(wèn)了幾個(gè)同學(xué)，又參考了借來(lái)的一些書(shū)后，才會(huì)，那個(gè)確實(shí)好難。（4）、對(duì)于遞歸的一些運(yùn)算，都會(huì)用到我們以前學(xué)到的c語(yǔ)言里的知識(shí)，因此還算簡(jiǎn)單，程序能夠完成。 (5)我寫(xiě)的這個(gè)程序可能過(guò)于簡(jiǎn)單，程序量很小，還請(qǐng)老師原諒。但都能實(shí)現(xiàn)任務(wù)書(shū)的要求。7、測(cè)試用例、結(jié)果及其分析圖2-1 運(yùn)行后，程序調(diào)試運(yùn)行程序，輸入數(shù)據(jù)，運(yùn)行成功。如圖2-1。圖2-2運(yùn)行后，程序調(diào)試每次輸入數(shù)據(jù)都需要重新運(yùn)行一下程序，所以在原來(lái)程序的基礎(chǔ)上加入大循環(huán)，可以多次使用，最后用判斷語(yǔ)句是否為0，來(lái)結(jié)束函數(shù)。見(jiàn)圖2-2。圖2-3 程序出現(xiàn)錯(cuò)誤的情況用判斷語(yǔ)句是否為0，來(lái)結(jié)束函數(shù)。結(jié)果發(fā)現(xiàn)語(yǔ)句發(fā)錯(cuò)誤，重新

8、修改判斷函數(shù)，見(jiàn)圖2-3。圖2-4 程序?qū)崿F(xiàn)所有的功能修改判斷語(yǔ)句函數(shù)成功，程序能夠?qū)崿F(xiàn)功能。見(jiàn)圖2-4。8、用戶使用說(shuō)明本程序運(yùn)行過(guò)程時(shí)帶有提示性語(yǔ)句。由于本程序可以對(duì)任意一個(gè)符合條件的數(shù)進(jìn)行計(jì)算，所以運(yùn)行開(kāi)始時(shí)根據(jù)提示輸入要輸入的數(shù)據(jù)。注意在這里提醒一下，由于程序的時(shí)間復(fù)雜度很高所以為了比較快的得到結(jié)果，建議輸入的數(shù)據(jù)最好在10以下。本程序在運(yùn)行過(guò)程中可能出現(xiàn)一個(gè)問(wèn)題，即輸入一個(gè)數(shù)據(jù)后程序一直在運(yùn)行，請(qǐng)不要關(guān)閉該程序，此程序會(huì)在一段較長(zhǎng)的時(shí)間的運(yùn)算得到你要的結(jié)果。本程序運(yùn)行過(guò)程時(shí)帶有提示性語(yǔ)句。由于本程序?qū)點(diǎn)到b點(diǎn)的路徑數(shù)計(jì)算，所以開(kāi)始得輸入馬的坐標(biāo)和b點(diǎn)的坐標(biāo)（a點(diǎn)位坐標(biāo)原點(diǎn)），本程序

9、要求的b點(diǎn)的坐標(biāo)a,b都不能 超過(guò)13.，輸入坐標(biāo)時(shí)需注意。輸入坐標(biāo)盡量考慮特殊情況，這樣可以知道程序的正確性。本程序基本還是很簡(jiǎn)單，能夠快速運(yùn)行。9、參考文獻(xiàn)1 王昆侖，李紅. 數(shù)據(jù)結(jié)構(gòu)與算法. 北京：中國(guó)鐵道出版社，2006年5月。2 徐孝凱.數(shù)據(jù)結(jié)構(gòu)實(shí)用教程.北京：清華大學(xué)出版社。1999年12月第一版 。3 bjarne stroustrup.c+程序設(shè)計(jì)語(yǔ)言（特別版）。機(jī)械工業(yè)出版社。2002 年7月。4 其它。10、附錄（完整源程序）#include"stdio.h"int k=0,s1=1;int a1616;int x,y,c,d;void fun(int

10、i,int j) if(i=x&&j=y) k+; if(i+1<=x&&ai+1j) fun(i+1,j); if(j+1<=y&&aij+1) fun(i,j+1); /馬不能到達(dá) ，判斷i是否到達(dá)x，j是否到達(dá)yint main() int s,t; while(1) printf("卒的坐標(biāo)是:"); scanf("%d",&x); scanf("%d",&y); /接收卒的坐標(biāo) printf("馬的坐標(biāo)是:"); scanf(&q

11、uot;%d",&c); scanf("%d",&d); /接收馬的坐標(biāo) for(s=0;s<=x;s+) for(t=0;t<=y;t+) ast=1; /以（0，0）到點(diǎn)（x，y）所形成的矩形的點(diǎn)都賦值為1 if(c<=x&&d<=y) acd=0; if(c-1>=0) /馬不能在x坐標(biāo)最邊緣的點(diǎn) if(d+2<=y) ac-1d+2=0; if(d-2>=0) ac-1d-2=0; if(c+1<=x) /馬向右移動(dòng)一個(gè)坐標(biāo)，判斷與x的關(guān)系 if(d+2<=y) ac+1d+2=0; if(d-2>=0) ac+1d-2=0; if(c-2>=0) /馬不能在y坐標(biāo)為1的點(diǎn) if(d-1>=0) ac-2d-1=0; if(d+1<=y) ac-2d+1=0; if(c+2<=x) /馬向右移動(dòng)2個(gè)坐標(biāo)，判斷與x的關(guān)系 if(d-1>=0) ac+2d-