[理學(xué)]第四章棧和隊(duì)列-資料下載頁
2024-10-16 21:31本頁面
【正文】 安全狀態(tài)判斷 (返回 1:安全， 0:不安全） int safe(int location) { if ((goat(location) == cabbage(location)) amp。amp。 (goat(location) != farmer(location))) return(0)。 //羊吃白菜 if ((goat(location) == wolf(location)) amp。amp。 (goat(location) != farmer(location))) return(0)。 //狼吃羊 return(1)。 //其它狀態(tài)為安全 } 問題變?yōu)?： 從 0000狀態(tài)出發(fā)，尋找全部由安全狀態(tài)構(gòu)成的狀態(tài)序列，以 1111為最終目標(biāo)。 狀態(tài)序列中每個(gè)狀態(tài)都可以從前一狀態(tài)通過農(nóng)夫（可以帶一樣?xùn)|西）劃船過河的動作到達(dá)。（序列中不能出現(xiàn)重復(fù)狀態(tài)） 如何由某種狀態(tài)提取所有可能的、安全的、未走過的狀態(tài)？ 算法 ： moveTo整數(shù)隊(duì)列 ，元素為可以安全到達(dá)的中間狀態(tài)。 route順序表 ，記錄各個(gè)狀態(tài)被訪問過的情況（狀態(tài) 16種，因此使用包含 16個(gè)元素的數(shù)組表示）： 1表示未被訪問，否則記錄前驅(qū)狀態(tài)值的下標(biāo)（表示該狀態(tài)已經(jīng)訪問過，由前驅(qū)到達(dá)）。最后，（ route[15]為非負(fù)值時(shí)）利用 route建立正確的狀態(tài)路徑。 前驅(qū)只有一個(gè)，后繼可多個(gè)。 因此： route數(shù)組記錄前驅(qū)狀態(tài)， 即：此狀態(tài)來自哪個(gè)狀態(tài)？ 實(shí)現(xiàn) ： p109~112 結(jié)果： p113 15, 6, 14, 2, 11, 1, 9, 0 0000 1001 0001 1011 0010 1110 0110 1111 1101 0100 while (!IsEmptyQueue_seq(moveTo) amp。amp。 route[15] 0) { //得到現(xiàn)在的狀態(tài) location = frontQueue_seq(moveTo)。 deQueue_seq(moveTo)。 //通過 location狀態(tài)由農(nóng)夫過河引起的所有可能的安全且尚未走過的狀態(tài)提取 for (movers = 1。 movers = 8。 movers = 1) //考慮所有可能的目標(biāo)移動 { //農(nóng)夫總是在移動，隨農(nóng)夫移動的東西必須與農(nóng)夫在 同側(cè) if (mover_location(location, movers) == mover_location(location, 0x08)) { //新位置 ，農(nóng)夫與要移動的東西同時(shí)過河 【 狀態(tài)改變 】 newlocation = location ^(0x08 | movers)。 //農(nóng)夫 +目標(biāo)狀態(tài)反轉(zhuǎn) if (safe(newlocation) amp。amp。 route[newlocation] 0) { //安全并且未訪問過 的狀態(tài) 【 入隊(duì)列 】 route[newlocation] = location。 enQueue_seq(moveTo, newlocation)。 } } } } 假定采用深度優(yōu)先搜索解決農(nóng)夫過河問題 ： 采用棧做輔助結(jié)構(gòu) ，把某狀態(tài)的所有后繼子狀態(tài)都放在棧中，如果某個(gè)狀態(tài)無后繼且不是最終狀態(tài)，退棧到上一層，進(jìn)入上一層的可能其它子狀態(tài)。如無，繼續(xù)退棧，直到?？栈虻竭_(dá)最終狀態(tài)為止。 對于每個(gè)狀態(tài)，只有其子狀態(tài)都測試后才能進(jìn)入下一可能狀態(tài)。 描述方法 ：四個(gè)目標(biāo)各采用一位（假定按照農(nóng)夫、狼、白菜、羊次序），目標(biāo)在河南位置： 0，河北： 1 任一時(shí)間的狀態(tài)采用四位 01碼表示，如 0101表示農(nóng)夫、白菜在河南，而狼、羊在河北（此狀態(tài)為不安全狀態(tài)） 實(shí)現(xiàn) ： 0000 1001 0001 1101 1011 0100 1011 1011 0010 1110 0110 1111 1011 0000 1001 1000 1010 1100 0001 0000 1011 1101 1001 重復(fù)狀態(tài) 不安全狀態(tài) 無法繼續(xù)狀態(tài) 1111 終止?fàn)顟B(tài) 0010 0001 0011 0100 0001 0101 1110 1010 1101 1110 1100 0100 0010 0110 1110 限制存取點(diǎn)的表 * 1. 雙端隊(duì)列 雙端隊(duì)列是一種特殊的線性表，對它所有的插入和刪除都限制在表的兩端進(jìn)行。 2. 雙棧 雙棧是一種加限制的雙端隊(duì)列，它規(guī)定從 end1插入的元素只能從 end1端刪除，而從 end2插入的元素只能從 end2端刪除。 底 end1 end2 end1 end2 3. 超隊(duì)列 超隊(duì)列是一種輸出受限的雙端隊(duì)列，即刪除限制在一端 (例如 end1) 4. 超棧是一種輸入受限的雙端隊(duì)列，即插入限制在一端（例如 end2）進(jìn)行，而刪除仍允許在兩端進(jìn)行。 end1 end2 end1 end2 小結(jié) 對于 棧的順序和鏈接表示以及在這兩種表示方式下基本運(yùn)算的實(shí)現(xiàn)應(yīng)熟練掌握，特別要注意棧滿和?？盏臈l件及描述；對于循環(huán)隊(duì)列和鏈接隊(duì)列及其基本運(yùn)算應(yīng)熟練掌握，特別要注意隊(duì)列滿和隊(duì)列空的條件及描述。 作業(yè) 復(fù)習(xí)： P114： 1 書面作業(yè)： P115: 9 上機(jī)作業(yè)： P116：應(yīng)用題 4（表達(dá)式求值） 思考：計(jì)算器模擬，更多的運(yùn)算 sin, cos, tan, sqrt, …….
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1