合肥學院
電腦科學與技術系
課程設計報告
2010 ～2011 學年第2學期
2011 年 6 月
1、題目
名稱：馬攔過河卒問題
內容：棋盤上a點有乙個過河卒，需要走到目標b點。卒行走的規則：
可以向下、或者向右。同時在棋盤上c點有乙個對方的馬，該馬所在的點和所有跳躍一步可達的點稱為對方馬的控制點。因此稱之為「馬攔過河卒」。
棋盤用座標表示，a點(0, 0)、b點(n, m)(n, m為不超過13的整數)，同樣馬的位置座標是需要給出的。要求計算出卒從a點能夠到達b點的路徑的條數，假設馬的位置是固定不動的，並不是卒走一步馬走一步。
2、問題分析
圖1-1 座標軸
a點有乙個過河卒，需要走到目標b點。卒行走的規則：可以向下、或者向右。
同時在棋盤上的任一點有乙個對方的馬（如上圖1-1的c點），該馬所在的點和所有跳躍一步可達的點稱為方馬的控制點。例如上圖c點上的馬可以控制9個點（圖中的p1，p2...p8和c）。
卒不能通過對方的控制點。
棋盤用座標表示，a點（0，0）、b點（n, m）(n,m為不超過20的整數，並由鍵盤輸入)，同樣馬的位置座標是需要給出的（約定：c≠a，同時c≠b）。現在要求你計算出卒從a點能夠到達b點的路徑的條數。
做乙個表，記錄馬可以攻擊的位置，主要要包括馬本身的位置；然後從（0，0）開始每次遞迴（x+1,y）和（x，y+1），如何(x==n1&&y==n2)說明走到位置了，那麼k++（路徑數）；如果大於邊界和等於馬可以攻擊的位置就return，這樣就可以了。不說考慮速度關係，我們可以加乙個過程，即座標一旦超出目標就return。
3、資料結構的選擇和概要設計
做乙個表，記錄馬可以攻擊的位置，主要要包括馬本身的位置；然後從（0，0）開始每次遞迴（x+1,y）和（x，y+1），如何(x==n1&&y==n2)說明走到位置了，那麼k++（路徑數）；如果大於邊界和等於馬可以攻擊的位置就return，這樣就可以了。不說考慮速度關係，我們可以加乙個剪枝過程，即座標一旦超出目標就return。
4、演算法思想
圖1-2 座標軸
1、卒行走的規則：可以向下、或者向右。
2、計算馬的控制點
按照題意，對方的馬所在的點和所有跳躍一步可達的點稱為對方馬的控制點，卒不能通過對方馬的控制點。在卒出發之前，必須計算對方馬的所有控制點。顯然，若（0，0）或（n,m）為控制點，則輸出路徑數為0。
3、假設馬的位置是固定不動的，並不是卒走一步馬走一步。所以從這去計算路徑數。
5、詳細設計和主要編碼段
使用遞迴的方法，記錄馬可以攻擊的位置
if(c<=x&&d<=y) a[c][d]=0;
if(c-1>=0馬不能在x座標最邊緣的點
if(c+1<=x馬向右移動乙個座標，判斷與x的關係
if(c-2>=0馬不能在y座標為1的點
if(c+2<=x馬向右移動2個座標，判斷與x的關係
6、上機除錯情況記錄
對演算法的效能分析
該演算法在進行運算時，儲存結果用到乙個二維陣列，而且當使用完之後，就將初始化，因此不會像陣列那樣浪費太多的空間，除此之外，還用到乙個遞迴的思想，不過該演算法的時間複雜度有點小，，不是那麼的大，函式中主要運用了遞迴語句，尤其是在一般情況運算中，用遞迴的方法，最終實現得到結果。時間複雜度為o（n^2）。
在除錯的時候遇到了一些問題：
（1）、程式除錯過程中常會出現一些小錯誤，如少括號少分號等小問題都可以按照提示找到，然後改正。
（2）、語句錯誤語句使用不當造成程式無法執行出正常的結果。
（3）、一開始，不會出項了好多錯誤，沒有考慮到特殊情況。我的資料結構學的不好，後來問了幾個同學，又參考了借來的一些書後，才會，那個確實好難。
（4）、對於遞迴的一些運算，都會用到我們以前學到的c語言裡的知識，因此還算簡單，程式能夠完成。
(5)我寫的這個程式可能過於簡單，程式量很小，還請老師原諒。但都能實現任務書的要求。
7、測試用例、結果及其分析
圖2-1 執行後，程式除錯
執行程式，輸入資料，執行成功。如圖2-1。
圖2-2執行後，程式除錯
每次輸入資料都需要重新執行一下程式，所以在原來程式的基礎上加入大迴圈，可以多次使用，最後用判斷語句是否為0，來結束函式。見圖2-2。
圖2-3 程式出現錯誤的情況
用判斷語句是否為0，來結束函式。結果發現語句發錯誤，重新修改判斷函式，見圖2-3。
圖2-4 程式實現所有的功能
修改判斷語句函式成功，程式能夠實現功能。見圖2-4。
8、使用者使用說明
本程式執行過程時帶有提示性語句。由於本程式可以對任意乙個符合條件的數進行計算
，所以執行開始時根據提示輸入要輸入的資料。注意在這裡提醒一下，由於程式的時間複雜度很高所以為了比較快的得到結果，建議輸入的資料最好在10以下。本程式在執行過程中可能出現乙個問題，即輸入乙個資料後程式一直在執行，請不要關閉該程式，此程式會在一段較長的時間的運算得到你要的結果。
本程式執行過程時帶有提示性語句。由於本程式對a點到b點的路徑數計算，所以開始得輸入馬的座標和b點的座標（a點位座標原點），本程式要求的b點的座標a,b都不能超過13.，輸入座標時需注意。
輸入座標盡量考慮特殊情況，這樣可以知道程式的正確性。本程式基本還是很簡單，能夠快速執行。
9、參考文獻
[1] 王崑崙，李紅. 資料結構與演算法. 北京：中國鐵道出版社，2023年5月。
[2] 徐孝凱.資料結構實用教程.北京：清華大學出版社。2023年12月第一版 。
[3] bjarne stroustrup.c++程式語言（特別版）。機械工業出版社。2002 年7月。
[4] 其它。
10、附錄（完整源程式）
#include"stdio.h"
int k=0,s1=1;
int a[16][16];
int x,y,c,d;
void fun(int i,int j)
if(i+1<=x&&a[i+1][j]) fun(i+1,j);
if(j+1<=y&&a[i][j+1]) fun(i,j+1); //馬不能到達 ，判斷i是否到達x，j是否到達y
}int main()
if(c+1<=x馬向右移動乙個座標，判斷與x的關係
if(c-2>=0馬不能在y座標為1的點
if(c+2<=x馬向右移動2個座標，判斷與x的關係
fun(0,0);
printf("路徑的條數為:");
printf("%d\n",k);
printf("是否繼續？0--退出\n");
scanf("%d",&s);
if(s==0) break;
} return 0;}
校園導遊系統程式 課程設計 報告
設計乙個校園導遊系統程式，為來訪的客人提供各種服務的資訊查詢。1 設計工商學院校園無向圖，所含的景點不少於10個。以圖中頂點表示校內各景點，存放景點名稱 代號 簡介等資訊 以邊表示路徑，存放路徑長度等相關資訊。2 為來訪客人提供圖中任意景點相關資訊的查詢。3 為來訪客人提供圖中任意景點的問路查詢，即...
C語言課程設計報告投票程式足球先生
前言程式設計實踐是學習程式語言中的乙個重要環節，許多同學在學習了課程設計這門課程後往往來不及消化以及應用所學知識。為了提高同學程式設計能力，強化同學們的理論應用於實際的能力，提高分析問題與解決問題的能力，故開設程式設計的課程使同學們的程式設計能力上乙個新的台階。設計題目 投票程式 足球先生投票 一 ...
通訊錄課程設計報告及源程式
合肥學院 電腦科學與技術系 課程設計報告 2008 2009學年第二學期 2009年6月 一 題目 有理數運算程式。有理數是乙個可以化為乙個分數的數，例如2 3，533 920，12 49都是有理數。在c 中，並沒有預先定義有理數，該課程設計要求定義乙個有理數類，將有理數的分子和分母分別存放在兩個整...