算法實驗報告：羅密歐與朱麗葉迷宮求解(共13頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)河南科技大學課程設計報告課程名稱：課程名稱：算法設計與分析 設計題目設計題目：羅密歐與朱麗葉迷宮求解問題 院院 系：系： 電子信息工程學院 專專 業(yè)：業(yè)： 計算機科學與技術 班班 級：級： 計算機 092 班 學生姓名學生姓名: : 學學 號號:09* 起止日期起止日期: 2011 年 5 月 28 日 - 2011 年 6 月 3 日 指導教師指導教師: 孫士保、張明川、冀治航 精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)課程設計題目羅密歐與朱麗葉的迷宮問題姓名*學號*班級092 班系別電子信息工程學院專業(yè)計算機科學與技術組別1 人組長*組員*指導教師

2、姓名孫士保、張明川、冀治航課程設計目的進一步鞏固 C 程序設計和算法設計與分析的基礎知識，提升結(jié)構(gòu)化程序、模塊化程序設計的方法和能力， 深入理解數(shù)據(jù)結(jié)構(gòu)的基本理論，掌握數(shù)據(jù)存儲結(jié)構(gòu)的設計方法，掌握基于數(shù)據(jù)結(jié)構(gòu)的各種操作的實現(xiàn)方法，訓練對基礎知識和基本方法的綜合運用能力，增強對算法的理解能力，提高軟件設計能力。在實踐中培養(yǎng)獨立分析問題和解決問題的作風和能力。設計環(huán)境1. PC 兼容機 2Windows 2000/XP 操作系統(tǒng)3TC 集成開發(fā)環(huán)境或其他 C 語言開發(fā)環(huán)境課程設計要求和任務要求：1熟練掌握回溯法，能夠利用回溯法解決實際問題；2使用文件進行存儲和管理。程序啟動時可從文件中讀取信息，或

3、從鍵盤輸入信息；運行過程中也可對文件進行存??；退出前可選擇將部分信息保存到文件中；3不同的功能使用不同的函數(shù)實現(xiàn)（模塊化） ，對每個函數(shù)的功能和調(diào)用接口要注釋清楚。對程序其它部分也進行必要的注釋。4對系統(tǒng)進行功能模塊分析、畫出總流程圖和各模塊流程圖；5用戶界面要求使用方便、簡潔明了、美觀大方、格式統(tǒng)一。所有功能可以反復使用，最好使用菜單；6通過命令行相應選項能直接進入某個相應菜單選項的功能模塊；7所有程序需調(diào)試通過。任務：完成羅密歐與朱麗葉的迷宮問題.設計內(nèi)容包括：1確定能對給定的任何位置的羅密歐都能夠找到一條通向朱麗葉的路線；2程序能夠演示一條羅密歐找到朱麗葉的路線過程等。課程設計工作進度計

4、劃序 號起止日期工 作 內(nèi) 容1下發(fā)任務書，分組，選定課題，查閱相關資料2總體設計，劃分模塊3編制源程序4上機調(diào)試，修改、完善系統(tǒng)5程序檢查6撰寫說明書精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)河南科技大學課程設計任務書 課程名稱課程名稱：算法設計與分析 題題 目目：羅密歐與朱麗葉迷宮求解問題院院 系：系： 電子信息工程學院 班班 級：級： 計算機科學與技術 092 班 學生姓名學生姓名: : * 指導教師指導教師: 孫士保、張明川、冀治航 起止日期起止日期: 2011 年 5 月 28 日 - 2011 年 6 月 3 日精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè) 目錄目錄.22.3 函數(shù)之

5、間的關系.3第三章編寫代碼及運行程序.33.1 源程序.33.2 操作及運行結(jié)果.63.3 設計的心得體會.7精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)第一章第一章 需求分析需求分析1.1 課程設計題目課程設計題目對于給定的羅密歐與朱麗葉的迷宮，編程計算羅密歐通向朱麗葉的所有最少彎道路程序能夠演示一條羅密歐找到朱麗葉的路線過程等1.2 課程設計任務及要求課程設計任務及要求羅密歐與朱麗葉的迷宮。羅密歐與朱麗葉身處一個 mn 的迷宮中，如圖所示。每一個方格表示迷宮中的一個房間。這 mn 個房間中有一些房間是封閉的，不允許任何人進入。在迷宮中任 何位置均可沿 8 個方向進入未封閉的房間。羅密歐位于迷

6、宮的。 (p，q)方格中，他必須找出一條通向朱麗葉所在的(r，s)方格的路。在抵達朱麗葉之前，他必須走遍所有未封閉的房間各一次，而且要使到達朱麗葉的轉(zhuǎn)彎次數(shù)為最少。每改變一次前進方向算作轉(zhuǎn)彎一次。請設計一個算法幫助羅密歐找出這樣一條路。1.3 軟硬件軟硬件運行環(huán)境及開發(fā)工具運行環(huán)境及開發(fā)工具硬件：裝有 windows 操作系統(tǒng)的計算機軟件：Visual C+6.0 精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè) 第二章第二章 程序概要設計程序概要設計 2.1 系統(tǒng)流程圖系統(tǒng)流程圖 2.2 函數(shù)的劃分：函數(shù)的劃分： （1）函數(shù) 1：bool trackback (int x,int y) 遞歸調(diào)用

7、trackback 函數(shù)求出最優(yōu)路徑。（2）函數(shù) 2：void isfull() 判斷房間是否全部走完（3）函數(shù)3：void main() 主函數(shù)初始化迷宮數(shù)組，并調(diào)用trackback函數(shù)輸出一條迷宮路線。 輸入 m,n,k,p,q,r,s -1-dirs count-0dep=m*n-k&x=r&y=s&dirsbest是 否 dirscountbest=dirs;count=1;1-.i 1-jbestwij=boardij+1-j直到 ji直到iip=x+diri0q=y+diri1x0&x0&ydirs boardpq=0;boardpq=de

8、p+1 di!=idirs+1-dis 直到ri=8 輸出 best ,count *bestw精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)2.3函數(shù)之間的關系函數(shù)之間的關系： 如下圖： main 函數(shù) isfull 函數(shù) 調(diào)用 trackbask 函數(shù) 遞歸調(diào)用 trackbask 函數(shù) 輸出結(jié)果 第三章第三章 編寫代碼及運行程序編寫代碼及運行程序3.1 源程序源程序#include int m,n,k;/m*n 迷宮，k 個封閉房間int x,y;/迷宮中 封閉房間的坐標int p,q,r,s;/羅密歐與朱麗葉的坐標int *square;/存儲迷宮int *dir;/用來記錄每一步的方向i

9、nt level(0);/記錄正在探測第幾步int finalLevel(0);/初始化為零int *result;/記錄結(jié)果int *path;int turn(999);/記錄最小拐彎數(shù)int dirx8=0,0,1,1,1,-1,-1,-1;/8 個方向變量int diry8=1,-1,-1,0,1,-1,0,1;bool trackback(int p,int q );bool IsFull();void main()int i, j;cin m n k;精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)result = new int *2;result0 = new int n*m;res

10、ult1 = new int n*m;path = new int *2;path0 = new int n*m;path1 = new int n*m;dir = new int m*n;square = new int *m+2;/m+2 是為了方便邊界處理for ( i=0; im+2; i+ )squarei=new int n+2;/n+2 是也是為了方便邊界處理for(i=0; im+2; i+)/初始化 square 迷宮for(j=0; jn+2; j+)squareij=0;for(i=0; ixy;squarexy=-1;/=邊界處理=for ( i=0, j=0; im+

11、2; i+ )squareij = 1;for ( i=0, j=0; jn+2; j+ )squareij = 1;for ( i=m+1,j=0; jn+2; j+ )squareij = 1;for ( j=n+1,i=0; ipqrs;dir0 = -1;/方向初始化trackback( p, q );/回溯cout turn - 1 endl;/輸出轉(zhuǎn)彎數(shù)for ( i = 0; i finalLevel; i+ )精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)squareresult0iresult1i = i + 1;for ( i = 1; i m + 1; i+)/打印迷宮for

12、( int j = 1; j n + 1; j+)cout squareij ;cout endl; bool trackback(int p,int q )/回溯過程/=將 p、q 放入 path 中=path0level=p;path1level=q;level+;/走出一步squarepq = 1;/標記起點已經(jīng)走過/=if ( p = r & q = s )/找到朱麗葉后求轉(zhuǎn)彎數(shù)，最小者保存之if ( IsFull() )/如果所有房間已經(jīng)走過int count(0);for ( int i = 1; i level; i+ )if ( diri != diri-1 ) cou

13、nt+;/若下一次的方向不同于上一次的方向，判定為一次轉(zhuǎn)彎if ( count turn )/找出最小轉(zhuǎn)彎數(shù)并保存之finalLevel = level;/記錄最后的步數(shù)turn = count;for ( int i = 0; i level; i+ )/保存最優(yōu)路徑result0i = path0i;result1i = path1i;squarepq = 0;/若已經(jīng)找到朱麗葉房間未走完，則重新置起點為 0level-;/后退return false;/該路徑不是答案，剪掉該子樹/退出找到朱麗葉的狀態(tài)精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)for ( int i = 0; i 8; i

14、+ )/以下是未找到朱麗葉的狀態(tài) 向八個方向搜索int x, y;x = p + dirxi;y = q + diryi;if ( squarexy = 0 ) /若該房間沒進入過，則標記其方向并進一步搜索dirlevel = i;trackback( x, y);squarepq = 0; /回到上一步level-;/回到上一步return true;/不需剪掉該子樹bool IsFull()/判斷是否走滿每個房間for ( int i = 1; i = m; i+ )for ( int j= 1; j = n; j+ )if ( squareij = 0 )return false;ret

15、urn true;3.2 操作及運作結(jié)果操作及運作結(jié)果輸入輸出并顯示迷宮結(jié)果如下：精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)3.4 設計的心得體會設計的心得體會 通過本次課程設計的訓練，增加了我學習算法的興趣，雖然還不是很明白其中的具體內(nèi)容，但已發(fā)現(xiàn)算法分析與程序設計的樂趣。老師給了我們四個題目供選擇，從選題到完成程序一步步操作實驗不僅對題目有了深入的了解，還達到了熟練使用 C 語言編程的能力。雖然還有很多復雜的問題是我們的能力所不及的，但我相信通過一次次實際的訓練操作會使我們的解決問題的能力一步步有所提高。這次程序設計是讓我們學到了好多知識，但也暴露了我們在程序設計中的不足。讓我們更深一步體會到了上機實訓的重要性。學校給我們安排實訓是為培養(yǎng)學生在實踐中培養(yǎng)獨立分析問題和解決問題的作風和能力，提高實際操作水。讓我們了解到除了學習基礎知識之外上機實驗也是必不可少的，只有通過多次的操作實驗才能夠提高自己的解決問題能力精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)計算機系課程設計指導教師評分表課程設計題目姓名學號專業(yè)班級指導教師評語指導教師評語