課程名稱: 通訊工程專業方向設計
設計名稱: 求迷宮中從入口到出口的路徑
姓名恆跡
學號班級
指導教師
起止日期
方向設計任務書
學生班級學生姓名學號
設計名稱: 求迷宮中從入口到出口的路徑
起止日期指導教師
方向設計學生日誌
課程設計評語表
求迷宮中從入口到出口的路徑
一、 摘要
用c語言程式設計實現從迷宮入口到出口的路徑,通常採用堆疊或佇列的形式來記錄所走過的路徑,而這裡採用的是與地圖同等大小的二維陣列來記錄路徑。從迷宮入口開始,採用向右、向下、向左、向上的先後優先遍歷順序逐個遍歷地圖,途中經過的路徑標記為*,如果遍歷途中遇到死角,則返回上一步繼續遍歷直到迷宮出口,那麼從迷宮入口到出口的路徑就是這個與地圖同等大小的二維陣列中*所表示的路徑。
二、 設計目的和意義
通過這個題目,不僅可以鍛鍊和提高學生的**能力,還可以提高學生的邏輯思維能力。隨著無人機械人的發展,可以把這個演算法思路加入到機械人裡面,對於乙個陌生的環境或者一些特殊環境可以先讓機械人探測一下路況。總之,這個題目具有很好的理論和現實意義。
三、 設計原理
這個題目實際上是乙個尋路題,只需要從入口開始逐個遍歷地圖,如果可以從入口遍歷到出口則表示有通路,如果不能從入口遍歷到出口,則表示沒有通路。
首先應該完成的是題目中所要求的迷宮從入口到出口的路徑,然後在次基礎之上實現手動輸入矩陣並實現從入口到出口的路徑。最後所有功能都實現之後,可以考慮一下**的優化。
這個題目總的來說不是很難,關鍵在於從迷宮入口到出口的遍歷過程。由於題目沒有任何比較苛刻的要求,這裡採取了簡單粗暴的方法。這裡按照右、下、左、上的優先順序先後檢測,如果向右為通路,則向右移一格,然後繼續檢測四周的通路情況;如果向右為障礙物,則向下檢測是否為通路,若向下為通路,則向下移一格,然後繼續檢測四周的通路情況;如果向下為障礙物,則向左檢測是否為通路,如向左為通路,則向左移一格,然後繼續檢測四周的通路情況;如果向左為障礙物,則向上檢測是否為通路,如向上為通路,則向上移一格,然後繼續檢測四周的通路情況。
如果四周都是障礙物,沒有通路,則向後退一步,重複上述檢測,直到到達迷宮出口為止。如果迷宮沒有從入口到出口的路徑,最後會回到起始點,則輸出提示該迷宮沒有從入口到出口的路徑。
四、 詳細設計步驟
1、 在電腦上安裝vc++6.0軟體。
2、 開啟軟體並建立乙個空白工程。
3、 寫出整個工程的框架程式。
function: find_route
description: 尋找從迷宮入口到出口的路徑。遍歷方式採取右、下、左、上的優先順序。
void find_path(void)
function: result
description: 輸出結果。
void result(void)
function: main
description: 主函式。
int main()
4、 實現題目中的迷宮從入口到出口的路徑。
function: example
description: 用特定地圖檢驗是否正確。
void example(void)
6、 優化程式。
總程式見附錄。
五、 設計結果及分析
如圖1所示,為示例迷宮從入口到出口的路徑。
圖1 示例迷宮從入口到出口的路徑
如圖2所示,為手動輸入乙個4*4矩陣迷宮,實現了從迷宮入口到出口路徑的遍歷。
圖2 手動輸入矩陣迷宮並實現從迷宮入口到出口路徑的遍歷
如圖3所示,為手動輸入的乙個沒有通路的3*3的矩陣迷宮,輸出提示為「there is no way to out!!!」。
圖3 手動輸入乙個沒有通路的矩陣迷宮
六、 總結
這個題目總的來說不是很難,關鍵在於從迷宮入口到出口的遍歷過程。由於題目沒有任何比較苛刻的要求,這裡採取了簡單粗暴的方法。雖然完成了題目的要求,但從迷宮入口到出口的路徑並不是最優路徑,要想得到最優路徑還有很多地方需要優化,最直接的暴力法是肯定行不通的,至於需要用什麼演算法,還需要更深入的學習。
七、 體會
通過這個題目的練習,我深刻的體會到理論聯絡實際的重要性。在真正動手寫程式之前,我以為這個題很簡單,可以一口氣直接寫出來,結果在寫的過程中碰到了很多問題,不得不多次停下來認真思考,一邊想著怎麼寫,一邊想著怎麼優化。最後經過不懈努力總算是完成了題目的要求。
八、 參考文獻
[1]譚浩強著. c程式設計(第四版).北京:清華大學出版社,2010
[2]劉汝佳著.演算法競賽入門經典.北京:清華大學出版社,2009
九、 附錄
file name: 尋找迷宮出口
description: 用乙個矩陣來表示迷宮,矩陣值為1表示此處有障礙,不能通過;矩陣值為0表示此處為通路。若迷宮沒有出路則輸出「there is no way to out!!!
」否則輸出整個迷宮以及從迷宮入口到出口的通路。
date: 2014/12/30
other: 無
#include ""
#include ""
#include ""
/* m、n表示迷宮大小;trance[100]記錄遍歷資訊;flag標記是使用示例地圖還是手動輸入地圖。
maze[10][10]用於儲存迷宮資訊;ans[10][10]用於儲存結果資訊; */
int m, n, flag, result, trance[100];
char maze[11][11], ans[11][11];
function: in_put_maze
description: 先輸入兩個數字 m 、n (m、n均大於3且小於10),表示迷宮的大小為 m 行 n 列;然後輸入乙個 m * n 的矩陣,要求輸入值為0或1, 1表示此處有障礙,不能通過;0表示此處為通路。
void in_put(void)
printf("\n請輸入乙個%d * %d 大小的迷宮:\n\n", m, n);
for(i = 0; i < m; i++)
}/* 把最右邊一列和最後一行賦值為1,表示邊界不能通過。 */
for(i = 0; i < m; i++)
for(i = 0; i< n; i++)
for(i = 0; i < 100; i++)
}function: find_route
description: 尋找從迷宮入口到出口的路徑。遍歷方式採取右、下、左、上的優先順序。
void find_path(void)
{ int i, j, k, flag;
i = j = k = 0;
《電氣專業方向設計》報告模版
西南科技大學 電氣工程及其自動化專業 方向設計報告 設計名稱 姓名學號 班級指導教師 起止日期 西南科技大學資訊工程學院制 方向設計任務書 學生班級學生姓名學號 設計名稱 起止日期指導教師 方向設計學生日誌 某電機修造廠變電所設計 摘要 150 關鍵詞 3 5個 英文題目 英文摘要 150 英文關鍵...
人力資源管理專業方向課程設計報告
湖南工程學院 系部 管理學院 班級學號 姓名完成日期 指導老師曹哲文 成績評定 課題一管理的困境 1 主要涉及薪酬管理這一領域。2 相關理論 1 影響組織制定薪酬的主要因素 主要有組織發展階段 組織文化 員工學歷 員工工齡 員工能力和工種,及外部公平 內部公平 政策等諸方面因素。對以上因素考慮程度的...
日語專業就業方向調查報告
職位一 助理軟體開發工程師 日語方向 職位說明 學習日常工作中主要應用的技術並對專案的整體流程及其對客戶的作用進行了解 根據技術文件中詳細描述的實現方式,完成簡單的軟體功能的開發和測試,將所學的技術應用到實踐中並嘗試理解為什麼要如此實現 在專案開發的過程中及開發後期整理相關的文件,做好工作記錄,並按...