林厚從信息學(xué)奧賽課課通第7單元第8課棧的應(yīng)用課件

林厚從信息學(xué)奧賽課課通第7單元第8課棧的應(yīng)用課件第一頁，共14頁。第7單元第8課棧的應(yīng)用第二頁，共14頁。例1:括號匹配(check,1s,256MB)假設(shè)表達式中允許包含兩種括號：圓括號和方括號,其嵌套的順序隨意,即([]())或[([][])]等為正確的格式,[(]或([())或(()])均為不正確的格式.本題的任務(wù)是檢測一個給定表達式中的括號是否正確匹配.輸入一個只包含上述括號的字符串,判斷字符串中的括號是否匹配,匹配就輸出”O(jiān)K”,不匹配就輸出”Wrong”。第三頁，共14頁。輸入格式：一行字符，只含有圓括號和方括號，個數(shù)小于255。輸出格式：匹配就輸出一行文本“OK”，不匹配就輸出一行文本“Wrong”。輸入樣例：[（]）輸出樣例：Wrong第四頁，共14頁。問題分析一個匹配的括號序列，必定是左、右圓括號、方括號的數(shù)量一樣多。但是反過來，一樣多不一定是匹配的。定義一個字符型的棧來維護左括號，按順序處理括號序列：1）遇到左括號：將它入棧。2）遇到右括號：檢查棧頂元素與右括號是否匹配。如果匹配，將棧頂左括號出棧；否則，判斷出序列不匹配，結(jié)束。如果讀到了左括號，而棧為空，也不匹配。如果序列處理完畢，棧非空，也不匹配。第五頁，共14頁。例2：表達式求值(NOIP2013普及組復(fù)賽,expr,1s,256MB)題目描述給定一個只包含加法和乘法的算術(shù)表達式，請你編程計算表達式的值。輸入格式：輸入僅有一行，為需要你計算的表達式，表達式中只包含數(shù)字、加法運算符“+”和乘法運算符“*”，且沒有括號，所有參與運算的數(shù)字均為0到2^31-1之間的整數(shù)。輸入數(shù)據(jù)保證這一行只有0~9、+、*這12種字符。輸出格式：輸出只有一行，包含一個整數(shù)，表示這個表達式的值。注意：當(dāng)答案長度多于4位時，請只輸出最后4位，前導(dǎo)0不輸出。輸入輸出樣例輸入樣例1：輸入樣例2：輸入樣例3：1+1*3+41+1234567890*11+1000000003*1輸出樣例1：輸出樣例2：輸出樣例3：878914說明對于30%的數(shù)據(jù)，0≤表達式中加法運算符和乘法運算符的總數(shù)≤100；對于80%的數(shù)據(jù)，0≤表達式中加法運算符和乘法運算符的總數(shù)≤1000；對于100%的數(shù)據(jù)，0≤表達式中加法運算符和乘法運算符的總數(shù)≤100000。第六頁，共14頁。問題分析

由于只有加號和乘號，只要從左往右掃一遍，如果遇到乘號直接計算（做乘法）；如果遇到加號，若后面沒有符號或者后面一個符號也是加號，則直接計算（做加法）；否則，先把后面緊接著的連續(xù)的乘號算完，最后再加。算法實現(xiàn)中，只要設(shè)置一個棧保存沒有立即進行的加法，掃描結(jié)束后再一起處理棧中的加法運算；同時，因為把一個數(shù)字串轉(zhuǎn)換成數(shù)也需要單獨編寫一個子程序；最后，還要注意實現(xiàn)過程中及時對10000取模。第七頁，共14頁。例3：圖的深度優(yōu)先遍歷(graph_dfs,1s,256MB)問題描述：讀入一個用鄰接矩陣存儲的無向圖，輸出它的深度優(yōu)先遍歷序列。輸入格式：第1行，1個正整數(shù)n，表示圖中的頂點數(shù)，2<=n<=100。接下來的n行是一個n*n的鄰接矩陣，a[i][j]=1表示頂點i和頂點j之間有直接邊相連，a[i][j]=0表示沒有直接邊相連。保證i=j時，a[i][j]=0，并且a[i][j]=a[j][i]。輸出格式：輸出1~n的某一種排列，表示從頂點1開始，對該圖進行深度優(yōu)先遍歷得到的頂點序列，每兩個數(shù)之間用一個“-“分隔。第八頁，共14頁。輸入樣例：80110000010011000100000110100010001000100000110000010000100100010輸出樣例：1－2－4－6－5－3－7－8第九頁，共14頁。練習(xí)1：瓷磚(tile,1s,256MB)問題描述：在一個w*h的矩形廣場上,每一塊1*1的地面都鋪設(shè)了紅色或黑色的瓷磚。小謝同學(xué)站在某一塊黑色的瓷磚上，他可以從此處出發(fā)，移動到上、下、左、右四個相鄰的且是黑色的瓷磚上。現(xiàn)在他想知道，通過重復(fù)上述移動所能經(jīng)過的黑色瓷磚數(shù)。輸入格式：第1行為兩個數(shù)h和w,2<=w,h<=50，之間有一個空格隔開。以下為一個w行h列的二維字符矩陣，每個字符為“.”“#”“@”，分別表示該位置為黑色的瓷磚、紅色的瓷磚，以及小Y的初始位置。輸出格式：1行，一個整數(shù)，表示小Y從初始位置出發(fā)可以到達的瓷磚數(shù)。第十頁，共14頁。輸入樣例：輸出樣例：11959.#..........#.#######..#.#.....#..#.#..@#.#..#.#####.#..#.......#..#########............第十一頁，共14頁。練習(xí)2：最大黑區(qū)域(area,1s,256MB)問題描述：二值圖像是由黑白兩種像素組成的矩形點陣，圖像識別的一個操作是求出圖像中最大黑區(qū)域的面積。請設(shè)計一個程序完成二值圖像的這個操作。黑區(qū)域由黑像素組成，一個黑區(qū)域中的每個像素至少與該區(qū)域中的另一個像素相鄰，規(guī)定一個像素僅與其上、下、左、右的像素相鄰。兩個不同的黑區(qū)域沒有相鄰的像素。一個黑區(qū)域的面積是其所包含的像素的個數(shù)。第十二頁，共14頁。輸入格式：第1行兩個正整數(shù)n和m，1<=n,m<=100，分別表示二值圖像的行數(shù)和列數(shù)。后面緊跟著n行，每行含m個整數(shù)0或1，其中第i行表示圖像的第i行的m個像素，0表示白像