羅密歐與朱麗葉迷宮求解問題

1、河南科技大學課 程 設 計 說 明 書課程名稱 軟件專題訓練 題 目 羅密歐與朱麗葉迷宮求解問題院 系 電子信息工程學院計算機系班 級 計算機科學與技術103班學生姓名 指導教師 孫士保、冀治航 日 期 2012.5.212012.5.27河南科技大學課 程 設 計 任 務 書課程名稱 算法設計與分析 題 目 羅密歐與朱麗葉的迷宮問題 院 系 電子信息工程學院計算機系班 級 計算機103班學生姓名 魏 鵬 超指導教師 孫士保、冀治航 日 期 2012.5.212012.5.27 羅密歐與朱麗葉的迷宮問題課程設計題目羅密歐與朱麗葉的迷宮問題姓名學號班級計算機10級系別計算機科學與技10級專業(yè)計算

2、機科學與技術組別組長組員指導教師姓名孫士保、冀治航課程設計目的進一步鞏固c程序設計和算法設計與分析的基礎知識，提升結構化程序、模塊化程序設計的方法和能力，深入理解數(shù)據(jù)結構的基本理論，掌握數(shù)據(jù)存儲結構的設計方法，掌握基于數(shù)據(jù)結構的各種操作的實現(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) 容12012.5.21下發(fā)任務書，分組，選定課題，查閱相關資料22012.5.22總體設計，劃分模塊，編制源程序32012.5.23上機調(diào)試，修改、完善系統(tǒng)42012.5.25程序檢查，撰寫說明書，上交報告河南科技大學課程設計報告課程名稱 軟件專題訓練 題 目 羅密歐與朱麗葉的迷宮問題 院 系： 電子信息工程學院計算機系 專 業(yè)： 計算機科學與技術 班 級： 計算機10級 學生姓名: 學 號: 起止日期: 2012年5月21日 2012年5月27日 指導教師: 孫士保、冀治航 4羅密歐與朱麗葉的迷宮問題目錄第一章 需求分析41.1課程設計題目41.2 課程設計

5、任務及要求41.3運行環(huán)境及開發(fā)工具4第二章 概要設計 52.1系統(tǒng)流程圖 5第三章 詳細設計63.1函數(shù)劃分63.2函數(shù)之間的關系6第四章 系統(tǒng)調(diào)試與操作說明74.1系統(tǒng)調(diào)試及操作說明7第五章 課程設計總結體會85.1課程設計總結85.2致謝85.3參考文獻8第一章 需求分析1.1課程設計題目羅密歐與朱麗葉的迷宮問題1.2 課程設計任務及要求1、 對于給定的羅密歐與朱麗葉的迷宮，編程計算羅密歐通向朱麗葉的所有最少轉(zhuǎn)彎道路2、程序能夠演示一條羅密歐找到朱麗葉的路線過程等羅密歐與朱麗葉的迷宮。羅密歐與朱麗葉身處一個mn的迷宮中，如圖所示。每一個方格表示迷宮中的一個房間。這mn個房間中有一些房間是

6、封閉的，不允許任何人進入。在迷宮中任何位置均可沿8 個方向進入未封閉的房間。羅密歐位于迷宮的 (p，q)方格中，他必須找出一條通向朱麗葉所在的(r，s)方格的路。在抵達朱麗葉之前，他必須走遍所有未封閉的房間各一次，而且要使到達朱麗葉的轉(zhuǎn)彎次數(shù)為最少。每改變一次前進方向算作轉(zhuǎn)彎一次。請設計一個算法幫助羅密歐找出這樣一條路。1.3運行環(huán)境及開發(fā)工具硬件：裝有windows操作系統(tǒng)的計算機軟件：visual c+6.0第二章 概要設計2.1系統(tǒng)流程圖輸入m,n,k,x,y,x1,y1-1-dirs best-1000 count-0dep=m*n-k&x=x1&y=y1&dirs=best是 否 否

7、dirsi1-jbestbij=boardijj+1-j直到ji直到icountreturndep=m*n-k|x=x1&y=y1|dirsbest是 否 1-ip=x+dxiq=y+dyix0&x0&ydirs直到 idirs boardpq=0;boardpq=dep+1di!=i dirs+1-dirs直到 i=8 輸出best,count*bestb第三章 詳細設計3.1函數(shù)劃分（1）函數(shù)1：bool stepok(int x,int y) 判斷是（x,y）否越界。（2）函數(shù)2：void save() 保存一條轉(zhuǎn)彎最少的路徑（3）函數(shù)3：void search(int dep,int

8、x,int y,int di) 在當前位置（x,y）按照八個方向搜索，dep用于標記已經(jīng)走過的房間數(shù),di表示八個方向。（4）函數(shù)4：void main() 主函數(shù)初始化迷宮數(shù)組，并調(diào)用search函數(shù)輸出一條迷宮路線。3.2函數(shù)之間的關系：主函數(shù)調(diào)用search函數(shù)，search函數(shù)調(diào)用stepok和save函數(shù)完成搜索。如下圖： main函數(shù) save函數(shù) 調(diào)用search函數(shù) 遞歸調(diào)用search函數(shù) 調(diào)用stepok函數(shù) 輸出結果第四章 系統(tǒng)調(diào)試與操作說明4.1系統(tǒng)調(diào)試及操作說明先是輸入迷宮中的各個參數(shù)： （1）、迷宮的行列數(shù)及封閉房間個數(shù)m,n,k分別是3，4，2。 （2）、2個封閉

9、房間的坐(p,q)分別是（1，2），（3，4）。 （3）、羅密歐與朱麗葉的坐標(x,y),(x1,y1)分別是（1，1），（2，2）。 輸出： 輸出一條迷宮路線：(1,1)(2,1) (3,1) (3,2) (2,3) (1,4) (1,3) (2,4) (3,3) (2,2) 1 -1 7 6 2 10 5 8 3 4 9 -1 第五章 課程設計總結體會5.1課程設計總結通過本次課程設計的訓練，增加了我學習算法的興趣，雖然還不是很明確其中的具體內(nèi)容，但已發(fā)現(xiàn)算法分析與程序設計的樂趣。老師給了我們四個題目供選擇，從選題到完成程序一步步操作實驗不僅對題目有了深入的了解，還達到了熟練使用c語言編程

10、的能力。雖然還有很多復雜的問題是我們的能力所不及的，但我相信通過一次次實際的訓練操作會使我們的解決問題的能力一步步有所提高。本次程序不是很復雜，只要對算法的有深入的認識與掌握就可以得到輸出的結果。但程序中涉及到了多個參數(shù)，在上機實驗過程中通過一次次實驗對算法一步步執(zhí)行中，徹底弄明白其中的各個參數(shù)及函數(shù)的作用及用法，特別是對回溯法有了更深的理解。在程序的編寫輸入輸出的過程中雖然其中遇到了很多錯誤與困難，但正是在解決這些錯誤與困難的過程中才會使我們的能力有所提高，知識有所更深入的理解，并進一步鞏固了c程序設計和算法設計與分析的基礎知識，增強對算法的理解能力，提高軟件設計能力，熟練掌握了回溯法，能夠

11、利用回溯法解決實際問題。雖然只是短短一星期但同學們都在努力學習與實踐，我知道只靠這些時間來練習遠遠不夠的，只有平時多練習，才會達到老師對我們的要求。這次程序設計是讓我們學到了好多知識，但也暴露了我們在程序設計中的不足。讓我們更深一步體會到了上機實訓的重要性。學校給我們安排實訓是為培養(yǎng)學生在實踐中培養(yǎng)獨立分析問題和解決問題的作風和能力，提高實際操作水。讓我們了解到除了學習基礎知識之外上機實驗也是必不可少的，只有通過多次的操作實驗才能夠提高自己的解決問題能力。5.2 致謝感謝本次試驗中給予技術等指導的孫士保、冀治航老師，因為他們的指導，本次試驗中的部分問題都得到了解決，并且學到了很多東西。感謝張強

12、，于文帥等同學的幫助，和他們探討問題，解決問題，不但學會了更多的東西，更加深了同學之間的友誼。5.3參考文獻計算機算法設計與分析教材（第三版）c/c+程序設計教程（第二版）數(shù)據(jù)結構（c語言）教材源碼#includeusing namespace std;int dir92=0,0,0,1,0,-1,1,0,-1,0,1,1,1,-1,-1,1,-1,-1;/行走的路線int count;int dirs,best;int board2020,bestw2020;int m,n,k;int lx,ly,zx,zy;bool comp(int x,int y) /判斷是坐標是否越界if(x0&x0

13、&y=m&boardxy=0) return true;else return false;static void save()/保存一條轉(zhuǎn)彎最少的路徑int i,j;for(i=1;i=n;i+) for(j=1;j=m;j+) bestwij=boardij;void search(int dep,int x,int y,int di)if(dep=m*n-k&x=zx&y=zy&dirs=best)/dep用于標記已經(jīng)走過的房間數(shù) di表示八個方向 if(dirsbest) return; else for(int i=1;i=8;i+) if(comp(x+diri0,y+diri1)

14、 boardx+diri0y+diri1=dep+1; if(di!=i) dirs+; search(dep+1,x+diri0,y+diri1,i); if(di!=i) dirs-; boardx+diri0y+diri1=0; int main() coutn; coutendl;coutm; coutendl;coutk;coutendl;int i,j;int c,d;memset(board,0,sizeof(board); for(i=0;ik;i+)/設置封鎖的房間位置cout請設置封鎖的第i+1cd; boardcd=-1;coutlxly;coutzxzy;boardlxly=1;best=m*n;dirs=-1;cout迷宮初始化如下：endl;cout其中0表示未到的房間，-1表示封閉的房間endl;for(i=0;in;i+) for(j=0;jm;j+) coutboardi+1j+1 ; coutendl;search(1,lx,ly,0); /輸出一條迷宮路線。cout最少轉(zhuǎn)彎次數(shù)：best 次endl;cout有不同的最少轉(zhuǎn)彎次數(shù)：count次endl;cout其中迷宮的一條最少轉(zhuǎn)彎道路如下：endl;for(i=1;i=n;i+) for(j=1;j=m;j+) coutbestwij ; coutendl;課程