




版權(quán)說(shuō)明:本文檔由用戶(hù)提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、1,棧與隊(duì)列上機(jī)題講解,一、 表達(dá)式的后綴式計(jì)算(9較難),二、 回文游戲,三、 地圖四染色(8,選做),四、 n皇后問(wèn)題(6),五、 k階斐波那契序列(5),2,表達(dá)式 := (操作數(shù)) + (運(yùn)算符) + (操作數(shù)) 操作數(shù) := 簡(jiǎn)單變量 | 表達(dá)式 簡(jiǎn)單變量 :=標(biāo)識(shí)符 | 無(wú)符號(hào)整數(shù),二元運(yùn)算符的表達(dá)式的三種標(biāo)識(shí)方法,3,表達(dá)式的三種標(biāo)識(shí)方法:,設(shè) Exp = S1 + OP + S2,則稱(chēng) OP + S1 + S2 為前綴表示法,S1 + OP + S2 為中綴表示法,S1 + S2 + OP 為后綴表示法,4,例如: Exp = a b + (c d / e) f 前綴式: 中綴
2、式: 后綴式:,結(jié)論:,1)操作數(shù)之間的相對(duì)次序不變;,2)運(yùn)算符的相對(duì)次序不同;,3)中綴式丟失了括弧信息, 致使運(yùn)算的次序不確定;,+ a b c / d e f a b + c d / e f a b c d e / f +,5,5)后綴式的運(yùn)算規(guī)則為: 每個(gè)運(yùn)算符和在它之前出現(xiàn) 且緊靠它 的兩個(gè)操作數(shù)構(gòu)成一個(gè)最小表達(dá)式; 運(yùn)算符在表達(dá)式中出現(xiàn)的順序恰為表達(dá)式的運(yùn)算順序。,4)前綴式的運(yùn)算規(guī)則為: 連續(xù)出現(xiàn)的兩個(gè)操作數(shù)和在它們之前且緊靠它們的運(yùn)算符構(gòu)成一個(gè)最小表達(dá)式;,6,如何從后綴式求值?,先找運(yùn)算符, 再找操作數(shù),例如: a b c d e / f +,ab,d/e,c-d/e,(c
3、-d/e)f,7,如何從原表達(dá)式求得后綴式?,每個(gè)運(yùn)算符的運(yùn)算次序要由它之后的一個(gè)運(yùn)算符來(lái)定,在后綴式中,優(yōu)先數(shù)高的運(yùn)算符領(lǐng)先于優(yōu)先數(shù)低的運(yùn)算符。,分析 “原表達(dá)式” 和 “后綴式”中的運(yùn)算符: 原表達(dá)式: a + b c d / e f 后綴式: a b c + d e / f ,8,從原表達(dá)式求得后綴式的規(guī)律為:,1) 設(shè)立運(yùn)算符棧;,2) 設(shè)表達(dá)式的結(jié)束符為“#”, 預(yù)設(shè)運(yùn)算符棧的棧底為“#”;,3) 若當(dāng)前字符是操作數(shù), 則直接發(fā)送給后綴式。,9,4) 若當(dāng)前運(yùn)算符的優(yōu)先數(shù)高于棧頂運(yùn)算符,則進(jìn)棧;,5) 否則,退出棧頂運(yùn)算符發(fā)送給后綴式;,6) “(” 對(duì)它之前后的運(yùn)算符起隔離作用,“
4、)”可視為自相應(yīng)左括弧開(kāi)始的表達(dá)式的結(jié)束符。,從原表達(dá)式求得后綴式的規(guī)律為:,10,例如: Exp = a b + (c d / e) f#,后綴式: Suffix =,a,d,c,f,+,b,+,(,-,e,/,/,11,void transform(char suffix , char exp ) /從原表達(dá)式求得后綴式 /s是運(yùn)算符棧,s棧底預(yù)設(shè) #,OP是運(yùn)算符集合 / CrtExptree,InitStack(S); Push(S, #); p = exp; ch = *p; while (!StackEmpty(S) if (!IN(ch, OP) / 若ch是操作數(shù) Pass(
5、Suffix, ch); else A: / 若ch是運(yùn)算符 if ( ch!= # ) p+; ch = *p; else Pop(S, ch); Pass(Suffix, ch); / while, ,12,A: switch (ch) case ( : Push(S, ch); break; case ) : Pop(S, c); while (c!= ( ) Pass( Suffix, c); Pop(S, c) break; defult : while(Gettop(S, c) / switch,若ch的優(yōu)先級(jí)比c低,為真,13,1) 設(shè)立操作數(shù)棧S;,2) 設(shè)表達(dá)式的結(jié)束符為“#
6、”;,3)讀入表達(dá)式一個(gè)字符,若當(dāng)前字符是操作數(shù),則壓入棧中,轉(zhuǎn)4)。,求后綴式的值:,14,若當(dāng)前字符是運(yùn)算符optr,從棧中彈出2個(gè)數(shù),將運(yùn)算結(jié)果再壓入棧,即: x2=POP(S); x1=POP(S); PUSH(S,(x1 optr x2);,讀下一字符,重復(fù)3)和4)直至讀到結(jié)束符#;,棧頂,x=POP(S)即后綴式相應(yīng)的表達(dá)式的值。,15,int cal(char suffix-exp ) /求后綴式表達(dá)式的值 /s是運(yùn)算數(shù)棧,OP是運(yùn)算符集合 /cal,InitStack(S); i = 0; ch = suffix-exp0; while (ch#) if (!IN(ch, O
7、P) / 若ch是操作數(shù) Push( S, ch); else / 若ch是運(yùn)算符 x2=POP(S); x1=POP(S);/取出兩個(gè)操作數(shù) PUSH(S,(x1 ch x2); i+; ch= suffix-expi; / while,16,算法思路: 1.讀入字符串 2.去掉空格(原串) 3.壓入棧 4.原串字符與出棧字符依次比較 若不等,非回文 若直到??斩枷嗟龋匚?字符串:“madam im adam”,回文游戲: 順讀與逆讀字符串一樣(不含空格),17,int IsHuiwen( char *S), SeqStack T; int i , n; char t1; InitStac
8、k( / 比較完畢均相等則返回 1 ,18,地圖四染色問(wèn)題,“四染色”定理是計(jì)算機(jī)科學(xué)中著名的定理之一。 使地圖中相鄰的國(guó)家或行政區(qū)域不重色,最少可用四種顏色對(duì)地圖著色。 證明此定理的結(jié)論,利用棧采用回溯法對(duì)地圖著色。 思想:對(duì)每個(gè)行政區(qū)編號(hào):1-7 對(duì)顏色編號(hào);a、b、c、d; 從第一號(hào)行政區(qū)開(kāi)始逐一染色,每一個(gè)區(qū)域逐次用四種顏色進(jìn)行試探,若所取顏色與周?chē)恢?,則用棧記下來(lái)該區(qū)域的色數(shù),否則依次用下一色數(shù)進(jìn)行試探。若出現(xiàn)a-d均與周?chē)l(fā)生重色,則需退?;厮荩薷漠?dāng)前棧頂?shù)纳珨?shù)。,19,1,2,2,3,4,1,4,3,3,4,2,3,1# 紫色 2# 黃色 3# 紅色 4# 藍(lán)色,地圖四染色舉
9、例,SK,20,Void mapcolor(int R,int n,int s), s1=1; / 1號(hào)區(qū)域染1色 a=2; J=1; / a為區(qū)域號(hào),J為染色號(hào) while ( a4) a=a-1; J=sa+1 /回溯,修改顏色 ,21,設(shè)n皇后問(wèn)題的解為 (x1, x2, x3, ,xn), 約束條件為:其中任意兩個(gè)xi 和xj不能位于棋盤(pán)的同行、同列及同對(duì)角線(xiàn)。,如何表示棋盤(pán)中放置的棋子? 由于每行、列及對(duì)角線(xiàn)上只能有一個(gè)棋子,因而對(duì)每列來(lái)說(shuō),只需記錄該列中棋子所在的行號(hào),故用一維數(shù)組即可。,皇后問(wèn)題求解,22,設(shè)四皇后問(wèn)題的解為 (x1, x2, x3, x4), 其中: xi (i
10、=1,2,3,4) Si=1, 2, 3, 4 約束條件為:其中任意兩個(gè)xi 和xj不能位于棋盤(pán)的同行、同列及同對(duì)角線(xiàn)。,按回溯法的定義,皇后問(wèn)題求解過(guò)程為: 解的初始值為空;首先添加 x1=1, 之后添加滿(mǎn)足條件的 x2=3,由于對(duì)所有的 x31,2, 3, 4都不能找到滿(mǎn)足約束條件的部分解(x1, x2, x3), 則回溯到部分解(x1), 重新添加滿(mǎn)足約束條件的x2=4, 依次類(lèi)推(按行存列號(hào))。,按四皇后問(wèn)題求解舉例,23,24,void queen(int i, int n) / 進(jìn)入本函數(shù)時(shí),在nn棋盤(pán)前i-1行已放置了互不攻 / 擊的i-1個(gè)棋子?,F(xiàn)從第 i 行起繼續(xù)為后續(xù)棋子選
11、擇 / 滿(mǎn)足約束條件的位置。當(dāng)求得(in)的一個(gè)合法布局 / 時(shí),輸出之。 if (in) 輸出棋盤(pán)的當(dāng)前布局; else for (j=1; j=n; +j) 在第 i 行第 j 列放置一個(gè)棋子; if (當(dāng)前布局合法) queen(i+1, n); 移去第 i 行第 j 列的棋子; / trial,25,#include #define n 8 / n為皇后個(gè)數(shù),m為擺法計(jì)數(shù) int m=0,an; / ai存放第i個(gè)皇后放置的行號(hào), int ok(int i, int j) /檢查(i,j)上能否放棋子 j1=j; i1=i; ok1=1; /1. 檢查第i行上能否放棋子 while(
12、(j11) return ok1 ,26,Void queen(int j) /從第j列開(kāi)始逐個(gè)試探 if (jn) m+; printf(m=%d ,m); for (i=1;i=n;i+) printf( %d,ai); printf(“n”); else for( i=1; i=n;i+) if(ok(i,j) /檢查(i,j)上能否放棋子 aj=i; /在(i,j)上放一個(gè)棋子 queen(j+1) ; main() queen(1);,27,k階斐波那契序列,試?yán)醚h(huán)隊(duì)列編寫(xiě)求k階斐波那契序列中前n+1項(xiàng)(f0, f1 , f2 , fn )的算法,要求滿(mǎn)足fn max而fn+1 max ,其中max為某個(gè)約定的常數(shù)。(注意本題所用循環(huán)隊(duì)列的容量?jī)H為k,則在算法執(zhí)行結(jié)束時(shí),留在循環(huán)隊(duì)列中的元素應(yīng)是k階斐波那契序列中的最后k項(xiàng)fn-k+1 , fn ) 。,28,f0=0 , f1=0 , , fk-2=0 , fk-1=1, fn = fn-1 + fn-2 + fn-k (n=k,k+1,),fi = fi-1 + fi-2 + fi-k fi+1 = fi + fi-1 + fi-2 + fi-k+1 兩式相減得: fi+1 = 2*fi - fi-k,k階斐波那契序列,29,void fb(int k,int max)
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶(hù)所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶(hù)上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶(hù)上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶(hù)因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 發(fā)動(dòng)機(jī)油品對(duì)性能影響研究考核試卷
- 供水設(shè)施維護(hù)考核試卷
- 田徑場(chǎng)地施工質(zhì)量控制考核試卷
- 機(jī)器學(xué)習(xí)在虛擬貨幣市場(chǎng)趨勢(shì)分析中的應(yīng)用考核試卷
- 公司出納工作總結(jié)合集14篇
- 兔年新春七言對(duì)聯(lián)
- 商務(wù)局機(jī)關(guān)黨支部自我剖析材料
- 武侯區(qū)人才日活動(dòng)方案
- 植樹(shù)節(jié)三月份活動(dòng)方案
- 法庭企業(yè)團(tuán)建活動(dòng)方案
- LNG接收站定量風(fēng)險(xiǎn)評(píng)價(jià)的開(kāi)題報(bào)告
- 工程部?jī)?nèi)部培訓(xùn)(一)項(xiàng)目經(jīng)理培訓(xùn)
- 《病歷書(shū)寫(xiě)基本規(guī)范》課件
- 【多旋翼無(wú)人機(jī)的組裝與調(diào)試分析6000字(論文)】
- 中學(xué)生反詐專(zhuān)題主題班會(huì)課件
- 塔式起重機(jī)安裝驗(yàn)收牌
- 幼兒園大班社會(huì)《偉大的起點(diǎn) 》 高清有聲課件
- 《義務(wù)教育地理新課程標(biāo)準(zhǔn)》(2022年版)新課標(biāo)初中地理解讀與梳理教學(xué)課件
- 工程倫理-核工程的倫理問(wèn)題
- 施工臨時(shí)設(shè)施驗(yàn)收表
- 2022年隴南市事業(yè)單位考試真題
評(píng)論
0/150
提交評(píng)論