數(shù)據(jù)結(jié)構(gòu)編程《迷宮問題》.ppt
-
資源ID:8445672
資源大?。?span id="tkv5vy3" class="font-tahoma">732KB
全文頁(yè)數(shù):13頁(yè)
- 資源格式: PPT
下載積分:9.9積分
快捷下載
會(huì)員登錄下載
微信登錄下載
微信掃一掃登錄
友情提示
2、PDF文件下載后,可能會(huì)被瀏覽器默認(rèn)打開,此種情況可以點(diǎn)擊瀏覽器菜單,保存網(wǎng)頁(yè)到桌面,就可以正常下載了。
3、本站不支持迅雷下載,請(qǐng)使用電腦自帶的IE瀏覽器,或者360瀏覽器、谷歌瀏覽器下載即可。
4、本站資源下載后的文檔和圖紙-無(wú)水印,預(yù)覽文檔經(jīng)過(guò)壓縮,下載后原文更清晰。
5、試題試卷類文檔,如果標(biāo)題沒有明確說(shuō)明有答案則都視為沒有答案,請(qǐng)知曉。
|
數(shù)據(jù)結(jié)構(gòu)編程《迷宮問題》.ppt
迷宮問題 迷宮問題 主要內(nèi)容1 問題分析2 遞歸算法3 非遞歸算法 1 問題分析 1 問題分析 迷宮求解這是一個(gè)找出口的問題 自相似性表現(xiàn)在什么地方 每走一步的探測(cè)方式 由于計(jì)算機(jī)很傻 只能通過(guò)窮舉方式找出口 怎么找法 沿著一個(gè)方向走下去 如果走不通 則換個(gè)方向走 四個(gè)方向都走不通 則回到上一步的地方 換個(gè)方向走 依次走下去 直到走到出口 1 問題分析 描述迷宮 1 設(shè)置迷宮為二維數(shù)組 數(shù)組的值是 1 代表墻0 代表未走過(guò)的路徑1 代表走不通的路徑2 代表路徑 1 問題分析 1 問題分析 2 設(shè)置搜索方向順序是東 南 西 北 x y x 1 y x y 1 x y 1 x 1 y 東 北 2 遞歸算法 明確遞歸函數(shù)的意義每一步的走法intnext intarr 10 Pointcur Pointend 迷宮求解 每走一步 1 如果當(dāng)前位置 出口 結(jié)束2 否則 假設(shè)當(dāng)前位置為路徑 如果東面未走過(guò) 向東走一步如果南面未走過(guò) 向南走一步如果西面未走過(guò) 向西走一步如果北面未走過(guò) 向北走一步設(shè)置當(dāng)前位置走不通 回溯 intnext intarr 10 Pointcur Pointend if cur x end x 3 非遞歸算法 程序步驟 1 當(dāng)前位置入棧2 判斷下一步是否可通 可通 則返回步驟1 不可通 換方向繼續(xù)探索 3 若四周 均無(wú)通路 則當(dāng)前位置出棧 從前一位置換方向搜索 voidMasePath intarr 10 Pointstart Pointend StackPointStack PointP start arr P x P y 2 do PointStack Push P if arr P x P y 1 0 arr P x P y 2 elseif arr P x 1 P y 0 arr P x P y 2 elseif arr P x P y 1 0 arr P x P y 2 elseif arr P x 1 P y 0 arr P x P y 2 else P PointStack Pop arr P x P y 1 P PointStack Pop while P x end x P y end y 輔助函數(shù) 打印迷宮voidPrintPath intarr 10 for inti 0 i 10 i for intj 0 j 10 j if arr i j 1 cout elseif arr i j 2 cout elsecout cout endl cout endl