迷宮求解數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告(已修改)
2025-08-02 13:33 本頁面
【正文】 課程設(shè)計(jì)報(bào)告課題名稱： 迷宮問題 姓 名： xxx 學(xué) 號： 200816020239 專 業(yè)： 電氣與信息工程學(xué)院 班 級： 通信08102 指導(dǎo)教師： 目 錄第一部分 課程設(shè)計(jì)報(bào)告…………………………………………………………3第一章 課程設(shè)計(jì)目的…………………………………………………3第二章 課程設(shè)計(jì)內(nèi)容和要求…………………………………………4 問題描述………………………………………………4 設(shè)計(jì)要求………………………………………………4第三章 課程設(shè)計(jì)總體方案及分析……………………………………4 問題分析………………………………………………4 概要設(shè)計(jì)………………………………………………7 詳細(xì)設(shè)計(jì)………………………………………………7 調(diào)試分析………………………………………………10 測試結(jié)果………………………………………………10 參考文獻(xiàn)………………………………………………12第二部分 課程設(shè)計(jì)總結(jié)…………………………………………………………13附錄(源代碼)……………………………………………………………………14第二部分 課程設(shè)計(jì)報(bào)告第一章 課程設(shè)計(jì)目的僅僅認(rèn)識到隊(duì)列是一種特殊的線性表是遠(yuǎn)遠(yuǎn)不夠的，本次實(shí)習(xí)的目的在于使學(xué)生深入了解隊(duì)列的特征，以便在實(shí)際問題背景下靈活運(yùn)用它，同時(shí)還將鞏固這種數(shù)據(jù)結(jié)構(gòu)的構(gòu)造方法第二章 課程設(shè)計(jì)內(nèi)容和要求 ： 迷宮問題是取自心理學(xué)的一個(gè)古典實(shí)驗(yàn)。在該實(shí)驗(yàn)中，把一只老鼠從一個(gè)無頂大盒子的門放入，在盒子中設(shè)置了許多墻，對行進(jìn)方向形成了多處阻擋。盒子僅有一個(gè)出口，在出口處放置一塊奶酪，吸引老鼠在迷宮中尋找道路以到達(dá)出口。對同一只老鼠重復(fù)進(jìn)行上述實(shí)驗(yàn)，一直到老鼠從入口走到出口，而不走錯(cuò)一步。老鼠經(jīng)過多次試驗(yàn)最終學(xué)會走通迷宮的路線。設(shè)計(jì)一個(gè)計(jì)算機(jī)程序?qū)θ我庠O(shè)定的矩形迷宮如下圖A所示，求出一條從入口到出口的通路，或得出沒有通路的結(jié)論。 圖A：要求設(shè)計(jì)程序輸出如下：(1) 建立一個(gè)大小為mn的任意迷宮（迷宮數(shù)據(jù)可由用戶輸入或由程序自動生成），并在屏幕上顯示出來；（2）找出一條通路的二元組（i,j）數(shù)據(jù)序列，（i,j）表示通路上某一點(diǎn)的坐標(biāo)。（3）用一種標(biāo)志（如數(shù)字8）在迷宮中標(biāo)出該條通路；（4）在屏幕上輸出迷宮和通路；（5）上述功能可用菜單選擇。第三章 課程設(shè)計(jì)總體方案及分析 問題分析：：迷宮中存在通路和障礙，為了方便迷宮的創(chuàng)建，可用0表示通路，用1表示障礙，這樣迷宮就可以用0、1矩陣來描述，：迷宮是一個(gè)矩形區(qū)域，可以使用二維數(shù)組表示迷宮，這樣迷宮的每一個(gè)位置都可以用其行列號來唯一指定，但是二維數(shù)組不能動態(tài)定義其大小，我們可以考慮先定義一個(gè)較大的二維數(shù)組maze[M+2][N+2],然后用它的前m行n列來存放元素，即可得到一個(gè)mn的二維數(shù)組，這樣(0,0)表示迷宮入口位置，(m1,n1)表示迷宮出口位置。注：其中M，N分別表示迷宮最大行、列數(shù)，本程序M、N的缺省值為339，當(dāng)然，用戶也可根據(jù)需要，調(diào)整其大小。：首先從迷宮的入口開始，如果該位置就是迷宮出口，則已經(jīng)找到了一條路徑，搜索工作結(jié)束。否則搜索其上、下、左、右位置是否是障礙，若不是障礙，就移動到該位置，然后再從該位置開始搜索通往出口的路徑；若是障礙就選擇另一個(gè)相鄰的位置，并從它開始搜索路徑。為防止搜索重復(fù)出現(xiàn)，則將已搜索過的位置標(biāo)記為2，同時(shí)保留搜索痕跡，在考慮進(jìn)入下一個(gè)位置搜索之前，將當(dāng)前位置保存在一個(gè)隊(duì)列中，如果所有相鄰的非障礙位置均被搜索過，且未找到通往出口的路徑，則表明不存在從入口到出口的路徑。這實(shí)現(xiàn)的是廣度優(yōu)先遍歷的算法，如果找到路徑，則為最短路徑。以矩陣 0 0 1 0 1 為例，來示范
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號-1