2023年全國碩士研究生考試考研英語一試題真題(含答案詳解+作文范文)_第1頁
已閱讀1頁,還剩7頁未讀 繼續(xù)免費閱讀

下載本文檔

版權說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權,請進行舉報或認領

文檔簡介

1、<p><b>  計算機科學與技術系</b></p><p><b>  課程設計報告</b></p><p>  2010 ~2011 學年第2學期</p><p>  2011 年 6 月</p><p><b>  1、題目</b></p>&l

2、t;p>  名稱:馬攔過河卒問題</p><p><b>  內(nèi)容:</b></p><p>  棋盤上A點有一個過河卒,需要走到目標B點。卒行走的規(guī)則:可以向下、或者向右。同時在棋盤上C點有一個對方的馬,該馬所在的點和所有跳躍一步可達的點稱為對方馬的控制點。因此稱之為“馬攔過河卒”。</p><p>  棋盤用坐標表示,A點(0, 0)

3、、B點(n, m)(n, m為不超過13的整數(shù)),同樣馬的位置坐標是需要給出的。要求計算出卒從A點能夠到達B點的路徑的條數(shù),假設馬的位置是固定不動的,并不是卒走一步馬走一步。</p><p><b>  2、問題分析</b></p><p><b>  圖1-1 坐標軸</b></p><p>  A點有一個過河卒,需要走

4、到目標B點。卒行走的規(guī)則:可以向下、或者向右。同時在棋盤上的任一點有一個對方的馬(如上圖1-1的C點),該馬所在的點和所有跳躍一步可達的點稱為方馬的控制點。例如上圖C點上的馬可以控制9個點(圖中的P1,P2...P8和C)。卒不能通過對方的控制點。</p><p>  棋盤用坐標表示,A點(0,0)、B點(n, m)(n,m為不超過20的整數(shù),并由鍵盤輸入),同樣馬 的位置坐標是需要給出的(約定:C≠A,同時C≠

5、B)?,F(xiàn)在要求你計算出卒從A點能夠到達B點的路徑的條數(shù)。做一個表,記錄馬可以攻擊的位置,主要要包括馬本身的位置;然后從(0,0)開始每次遞歸(x+1,y)和(x,y+1),如何(x==n1&&y==n2)說明走到位置了,那么k++(路徑數(shù));如果大于邊界和等于馬可以攻擊的位置就return,這樣就可以了。不說考慮速度關系,我們可以加一個過程,即坐標一旦超出目標就return。</p><p>  

6、3、數(shù)據(jù)結構的選擇和概要設計</p><p>  做一個表,記錄馬可以攻擊的位置,主要要包括馬本身的位置;然后從(0,0)開始每次遞歸(x+1,y)和(x,y+1),如何(x==n1&&y==n2)說明走到位置了,那么k++(路徑數(shù));如果大于邊界和等于馬可以攻擊的位置就return,這樣就可以了。不說考慮速度關系,我們可以加一個剪枝過程,即坐標一旦超出目標就return。</p>

7、<p><b>  4、算法思想</b></p><p><b>  圖1-2 坐標軸</b></p><p>  1、卒行走的規(guī)則:可以向下、或者向右。</p><p>  2、計算馬的控制點 </p><p>  按照題意,對方的馬所在的點和所有跳躍一步可達的點稱為對方馬的控制點,卒不

8、能通過對方馬的控制點。在卒出發(fā)之前,必須計算對方馬的所有控制點。顯然,若(0,0)或(n,m)為控制點,則輸出路徑數(shù)為0。</p><p>  3、假設馬的位置是固定不動的,并不是卒走一步馬走一步。所以從這去計算路徑數(shù)。</p><p>  5、詳細設計和主要編碼段</p><p>  使用遞歸的方法,記錄馬可以攻擊的位置</p><p> 

9、 if(c<=X&&d<=Y) a[c][d]=0;</p><p>  if(c-1>=0) //馬不能在x坐標最邊緣的點</p><p><b>  {</b></p><p>  if(d+2<=Y) a[c-1][d+2]=0;</p><p&g

10、t;  if(d-2>=0) a[c-1][d-2]=0; //查看馬是否能夠攻擊到</p><p><b>  }</b></p><p>  if(c+1<=X) //馬向右移動一個坐標,判斷與x的關系</p><p><b>  {</b></p>

11、<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坐標為1的點<

12、;/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><p

13、>  if(c+2<=X) //馬向右移動2個坐標,判斷與x的關系</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; //查看馬是否能夠攻擊到<

14、;/p><p><b>  }</b></p><p>  6、上機調(diào)試情況記錄</p><p><b>  對算法的性能分析</b></p><p>  該算法在進行運算時,存儲結果用到一個二維數(shù)組,而且當使用完之后,就將初始化,因此不會像數(shù)組那樣浪費太多的空間,除此之外,還用到一個遞歸的思想,不過該

15、算法的時間復雜度有點小,,不是那么的大,函數(shù)中主要運用了遞歸語句,尤其是在一般情況運算中,用遞歸的方法,最終實現(xiàn)得到結果。時間復雜度為O(n^2)。</p><p>  在調(diào)試的時候遇到了一些問題:</p><p> ?。?)、程序調(diào)試過程中常會出現(xiàn)一些小錯誤,如少括號少分號等小問題都可以按照提示找到,然后改正。</p><p>  (2)、語句錯誤語句使用不當造成

16、程序無法運行出正常的結果。</p><p>  (3)、一開始,不會出項了好多錯誤,沒有考慮到特殊情況。我的數(shù)據(jù)結構學的不好,后來問了幾個同學,又參考了借來的一些書后,才會,那個確實好難。</p><p> ?。?)、對于遞歸的一些運算,都會用到我們以前學到的C語言里的知識,因此還算簡單,程序能夠完成。 </p><p>  (5)我寫的這個程序可能過于簡單,程序量

17、很小,還請老師原諒。但都能實現(xiàn)任務書的要求。</p><p>  7、測試用例、結果及其分析</p><p>  圖2-1 運行后,程序調(diào)試</p><p>  運行程序,輸入數(shù)據(jù),運行成功。如圖2-1。</p><p>  圖2-2運行后,程序調(diào)試</p><p>  每次輸入數(shù)據(jù)都需要重新運行一下程序,所以在原來程

18、序的基礎上加入大循環(huán),可以多次使用,最后用判斷語句是否為0,來結束函數(shù)。見圖2-2。</p><p>  圖2-3 程序出現(xiàn)錯誤的情況</p><p>  用判斷語句是否為0,來結束函數(shù)。結果發(fā)現(xiàn)語句發(fā)錯誤,重新修改判斷函數(shù),見圖2-3。</p><p>  圖2-4 程序?qū)崿F(xiàn)所有的功能</p><p>  修改判斷語句函數(shù)成功,程序能夠?qū)崿F(xiàn)

19、功能。見圖2-4。</p><p><b>  8、用戶使用說明</b></p><p>  本程序運行過程時帶有提示性語句。由于本程序可以對任意一個符合條件的數(shù)進行計算</p><p>  ,所以運行開始時根據(jù)提示輸入要輸入的數(shù)據(jù)。注意在這里提醒一下,由于程序的時間復雜度很高所以為了比較快的得到結果,建議輸入的數(shù)據(jù)最好在10以下。本程序在運行

20、過程中可能出現(xiàn)一個問題,即輸入一個數(shù)據(jù)后程序一直在運行,請不要關閉該程序,此程序會在一段較長的時間的運算得到你要的結果。本程序運行過程時帶有提示性語句。由于本程序?qū)點到B點的路徑數(shù)計算,所以開始得輸入馬的坐標和B點的坐標(A點位坐標原點),本程序要求的B點的坐標a,b都不能 超過13.,輸入坐標時需注意。輸入坐標盡量考慮特殊情況,這樣可以知道程序的正確性。本程序基本還是很簡單,能夠快速運行。</p><p>&

21、lt;b>  9、參考文獻</b></p><p>  [1] 王昆侖,李紅. 數(shù)據(jù)結構與算法. 北京:中國鐵道出版社,2006年5月。</p><p>  [2] 徐孝凱.數(shù)據(jù)結構實用教程.北京:清華大學出版社。1999年12月第一版 。</p><p>  [3] Bjarne Stroustrup.C++程序設計語言(特別版)。機械工業(yè)出版社

22、。2002 年7月。</p><p><b>  [4] 其它。</b></p><p>  10、附錄(完整源程序)</p><p>  #include"stdio.h"</p><p>  int k=0,s1=1;</p><p>  int a[16][16];<

23、;/p><p>  int X,Y,c,d;</p><p>  void fun(int i,int j)</p><p><b>  {</b></p><p>  if(i==X&&j==Y)</p><p><b>  {</b></p>&

24、lt;p><b>  k++;</b></p><p><b>  }</b></p><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);

25、//馬不能到達 ,判斷i是否到達x,j是否到達y</p><p><b>  }</b></p><p>  int main()</p><p><b>  {</b></p><p><b>  int s,t;</b></p><p><b&

26、gt;  while(1){</b></p><p>  printf("卒的坐標是:");</p><p>  scanf("%d",&X);</p><p>  scanf("%d",&Y); //接收卒的坐標</p><p>

27、  printf("馬的坐標是:");</p><p>  scanf("%d",&c);</p><p>  scanf("%d",&d); //接收馬的坐標</p><p>  for(s=0;s<=X;s++)</p><p>  

28、for(t=0;t<=Y;t++)</p><p>  a[s][t]=1; //以(0,0)到點(x,y)所形成的矩形的點都賦值為1</p><p>  if(c<=X&&d<=Y) a[c][d]=0;</p><p>  if(c-1>=0) //馬不能在x坐標

29、最邊緣的點</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>  }</b></p><p>  if(c

30、+1<=X) //馬向右移動一個坐標,判斷與x的關系</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> 

31、 }</b></p><p>  if(c-2>=0) //馬不能在y坐標為1的點</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]=

32、0;</p><p><b>  }</b></p><p>  if(c+2<=X) //馬向右移動2個坐標,判斷與x的關系</p><p><b>  {</b></p><p>  if(d-1>=0) a[c+2][d-1]=0;</p>

33、<p>  if(d+1<=Y) a[c+2][d+1]=0;</p><p><b>  }</b></p><p><b>  fun(0,0);</b></p><p>  printf("路徑的條數(shù)為:");</p><p>  printf(&quo

34、t;%d\n",k);</p><p>  printf("是否繼續(xù)?0--退出\n");</p><p>  scanf("%d",&s);</p><p>  if(s==0) break;</p><p><b>  }</b></p><

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
  • 4. 未經(jīng)權益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 眾賞文庫僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
  • 6. 下載文件中如有侵權或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論