第13課單行道問題——隊(duì)列

1、第13課 單行道問題 隊(duì)列 由于前面修路，交警叔叔把路改成了單行道，所有的車只能在入口排好一輛一輛地進(jìn)入單行公路，在單行道中不能超車（因?yàn)楣返膶挾戎荒軌蜃屢惠v車通過），也不能后退（因?yàn)楹竺嬗熊囃瞬粍?dòng)），只有當(dāng)它前面沒有其他車的時(shí)候才能通過單行道出去，現(xiàn)在楠楠的車也在單行道中，她想知道自己是第幾個(gè)開出單行道的人，你能用程序來幫她嗎？例如：用不同的字符串代表不同的車，現(xiàn)在有C,Bfd,G,H,Ns,DD,E,S,EG按上面的順序進(jìn)入了單行道，楠楠的車是H，剛好是第4部開出單行道的車?！痉治觥浚?） 所有這些在單行道中的車可以看成是由不同字符串所組成的一個(gè)數(shù)據(jù)表，我們用數(shù)組a來表示這個(gè)數(shù)據(jù)表，其中

2、數(shù)據(jù)元素的下標(biāo)，可以代表他們進(jìn)入單行道時(shí)的順序，如上例即是：a1='C',a2='Bfd',a9='EG'。（2） 由于在單行道中的車是先進(jìn)入就先出去，所以可以從數(shù)組的第一個(gè)元素開始掃描查找目標(biāo)字符串，如果沒有找到，就繼續(xù)向下掃描。否則就輸出元素下標(biāo)，即是所求。Nannan(H)CBfdGHNsDDESEG讀入“楠楠“字串讀入數(shù)量到nFor i:=1 to n do readln(ai);Nai:=nannan？輸出i的值參考程序Program p13_1; Var a:arrayi.100 of string; i,n:integer; nan

3、nan:string; begin readln(nannan); 讀入代表楠楠的車的字串 readln(n); 讀入共有n輛車進(jìn)入了單行道 for i:=1 to n do readln(ai); 讀入第i輛進(jìn)入單行道中的車輛字符串 i:=0; repeat 從數(shù)組第一元素開始向后逐一查找代表楠楠車的字符串 i:=i+1; until ai=nannan; writeln(i); end.返回及進(jìn)充電1、 隊(duì)列在實(shí)際生活中上，我們坐公交車要排隊(duì)上車，在超市買東西要排隊(duì)付錢，這些就是我們常常見到的隊(duì)列，它們的特點(diǎn)都是先到的排在前面，后到的排在后面。而在編程時(shí)，我們也用一種稱為“隊(duì)列”的數(shù)據(jù)組織

4、方式來模仿日常生活中的隊(duì)列。 隊(duì)列的操作特點(diǎn)是先進(jìn)先出，后進(jìn)后出，所有元素從一端進(jìn)入，從另一端出去，就如汽車在單行道上行走時(shí)，只能在道路的一端進(jìn)入，一端出去。我們把出去的一端稱為“隊(duì)首"(front),可以進(jìn)入的一端稱為“隊(duì)尾”(rear)，如圖13-1所示：出隊(duì)列入隊(duì)列a1a2a3an 隊(duì)首 隊(duì)尾 圖13-1 隊(duì)列示意圖2、 循環(huán)隊(duì)列如果用數(shù)組a1.n來存儲(chǔ)隊(duì)列時(shí)，數(shù)組的上界n即是隊(duì)列所容許的最大容量，如圖13-2所示，當(dāng)最后一個(gè)位置an已使用而還有數(shù)據(jù)要入隊(duì)時(shí)，則會(huì)產(chǎn)生“溢出”，但前面的隊(duì)首可能因元素出隊(duì)而空出很多空間，這樣就會(huì)白白浪費(fèi)空間，而且隊(duì)列又不能繼續(xù)入隊(duì)。出隊(duì)列入隊(duì)列a

5、n 隊(duì)首 隊(duì)尾圖13-2 隊(duì)列可以產(chǎn)生溢出的情形為了解決上面問題，把前面空出來的可用空間利用起來，我們對(duì)有n個(gè)存儲(chǔ)單元的隊(duì)列，只利用前n-1個(gè)單元，而最后一個(gè)位置an用作提示指針，指向繞到第1個(gè)位置，形成邏輯上的環(huán)狀空間，這樣當(dāng)front或rear到達(dá)整個(gè)數(shù)組的末尾時(shí)，又可以回到開頭，這樣的隊(duì)列我們稱它是循環(huán)隊(duì)列。如圖13-3所示：圖13-3 循環(huán)隊(duì)列示意圖我們約定，如圖13-3所示，隊(duì)尾(rear)指示到當(dāng)前隊(duì)尾元素所在位置的下一位，隊(duì)首(front)指示隊(duì)列中第一元素在數(shù)組中的位置。隊(duì)首(front)和隊(duì)尾(rear)均可以環(huán)繞數(shù)組移動(dòng)，隊(duì)列中騰出的空間就可以再利用，當(dāng)front和rear

6、的值大于了數(shù)組長度n時(shí)，我們就用求余運(yùn)算使它們的值始終在1.n之間，就像時(shí)鐘的指針經(jīng)過了12點(diǎn)后總是又從1點(diǎn)開始一樣(如17 mod 12=5).如圖1-4所示，當(dāng)隊(duì)列的頭尾重合，即front=rear時(shí)，這時(shí)隊(duì)列為空;如圖13-5所示，當(dāng)front=(rear mod n)+1時(shí)，這時(shí)隊(duì)列為滿；其余時(shí)候，隊(duì)列中的元素個(gè)數(shù)為：(rear-front+n) mod n。 圖13-3 隊(duì)列為空 圖13-4 隊(duì)列為滿探索奧秘例1 蕓蕓和楠楠在玩撲克牌，她們共有n張撲克，這些撲克上分別記為1,2，n,蕓蕓打開撲克第一張是1，把它放在一邊然后把最上面2張一張一張地依次移到最后，打開上面一張，剛好是3，放

7、在一邊。如此繼續(xù)下去，直至打開最后一張是n，放在一邊，這時(shí)楠楠發(fā)現(xiàn)，放在一邊的撲克剛好是按1,2，3n這樣排列的，好想知道，在開始的時(shí)候應(yīng)當(dāng)怎樣排放這些撲克，才能得到這樣的結(jié)果，你能幫她寫個(gè)程序求出撲克的最先排列順序嗎？例如：當(dāng)n=5時(shí)，原排列是：1 4 5 2 3;當(dāng)n=9時(shí)，原排列是：1 8 6 2 9 4 5 3 7分析(1)把n張牌看成是1n的n個(gè)數(shù)組成的隊(duì)列，用數(shù)組a存放，用h指向隊(duì)列a的隊(duì)首。 (2)用數(shù)組b來表示要求的原排列，因?yàn)閎中的入隊(duì)元素來自a中的出隊(duì)元素，所以有bi=ah,顯然b1=a1，其值均為1，令h的初值為2。 (3)用t 表示a的隊(duì)尾，從隊(duì)首移動(dòng)1張到隊(duì)尾，則隊(duì)尾

8、加1，將隊(duì)首值ah賦給at;重復(fù)這個(gè)過程i次。 (4)當(dāng)前值ah出隊(duì)，并要在b中入隊(duì)，用i指向b隊(duì)尾，則bi:=ah. (5)重復(fù)(3)(4)兩步，直到n張牌都拿出了為止。例如當(dāng)n=4時(shí)的求解過程如圖13-6所示：123456789a 1b 把1放在一邊，向后移動(dòng)兩張423a 14b 把4放在一邊，向后移動(dòng)三張32a 143b 把3放在一邊，剩下最后一張2a 14b 最后1張，直接放到一邊去 圖13-6 4張撲克的求解過程參考程序Progrm P13_2; var a,b:array1.1000 of integer; i,j,t,h,n:integer; beginwrite('N&

9、#39;); readln(n); 讀入隊(duì)列的元素個(gè)數(shù)for i:=1 to n do ai:=i; 給數(shù)組賦初值，元素值和下標(biāo)相同h:=2;t:=n;b1:=1; 第一個(gè)進(jìn)入隊(duì)列b的數(shù)for i:=2 to n do 還有2n個(gè)數(shù)要進(jìn)入隊(duì)列b begin for j:=1 to i do 把i張牌一張一張地移動(dòng)到后面 begin inc(t); at:=ah; 從隊(duì)列前面開始逐一把i個(gè)牌移動(dòng)到隊(duì)列后面 inc(h); 修改指向的第一張 end; bi:=ah; 把放在一邊的這一張i inc(h); end;for i:=1 to n do write(bi);writeln end. 這是一

10、個(gè)典型隊(duì)列的例子，請(qǐng)大家仔細(xì)體會(huì)在隊(duì)列操作過程中隊(duì)首和隊(duì)尾的變化。 例2 花果山今天可熱鬧了，猴子們打算選出一個(gè)自己的大王。經(jīng)過協(xié)商，決定選大王的規(guī)則如下：n只猴子圍成一圈，每只猴子只有一個(gè)編號(hào)，編號(hào)從1到n，現(xiàn)在從第一只開始報(bào)數(shù)，報(bào)到m的猴子出圈，下一只猴子接著又從1開始報(bào)數(shù)，報(bào)到m時(shí)又出圈，最后剩下來的就是大王。請(qǐng)你編程計(jì)算求最后剩下的猴子原來的編號(hào)k。例如：當(dāng)n=10，m=3時(shí)，k=4;當(dāng)n=20，m=3時(shí)，k=20。分析此題是由古羅馬著名史學(xué)家約瑟夫提出的問題演變而來的，所以通常稱為約瑟夫問題。(1) 首先考慮如何組織數(shù)據(jù)，要記錄n只猴子的狀態(tài)，可利用含n個(gè)元素的數(shù)組a來實(shí)現(xiàn)。(2)

11、利用元素下標(biāo)代表猴子的編號(hào)，元素的值記錄排在它后面猴子編號(hào)，如a1=2,則表示當(dāng)前猴子是1，其后面是編號(hào)為2的猴子。由于猴子排成的是一圈，所以有：an=1。如當(dāng)n=5時(shí)，實(shí)際排隊(duì)的情形如圖13-7所示：23451 a1 a2 a3 a4 a5 圖13-7 5只猴子的排隊(duì)情況(3) 可以采用模擬選舉過程的方法來求解，將報(bào)數(shù)變量t置為1，用變量P表示當(dāng)前報(bào)數(shù)的猴子的編號(hào)，用q表示之前的一個(gè)報(bào)數(shù)的猴子的編號(hào)。(4) 當(dāng)報(bào)數(shù)達(dá)到m的倍數(shù)時(shí)，當(dāng)前報(bào)數(shù)的猴子P出圈，p的前一個(gè)和后一個(gè)猴子變?yōu)猷従印Ｓ胊q:=ap實(shí)現(xiàn)。(5) 然后繼續(xù)往下報(bào)數(shù)，直到圈中只剩下一只猴子即p=aq時(shí)為止。參考程序Program

12、P13_3;const num=50;var a:array1.num of integer;i,p,q,t,m,n:integer; begin readln(n.m);for i:=1 to n-1 do ai:=i+1; 用數(shù)組下標(biāo)表示猴子編號(hào)，用元素的值記錄下一個(gè)猴子的編號(hào)an:=1; 由于猴子是站成一圈，所以最后第n只猴子與第一個(gè)猴子相鄰q:=n; p:=n; t:=0;repeat p:=ap; p表示從哪個(gè)猴子開始報(bào)數(shù) t:=t+1; t表示當(dāng)前報(bào)數(shù)和具體數(shù)字 if (t mod m<>0) then q:=p 沒有數(shù)到整數(shù)m倍時(shí)，則繼續(xù)數(shù)數(shù) else aq:=ap;

13、 否則前一猴子和后一猴子變成鄰居 until(p=ap); 當(dāng)前猴子和其下一個(gè)猴子都是同一只猴子時(shí)結(jié)束循環(huán) writeln('The total number:',n:3); writeln('The max number to call:',m:3); writeln('The leadger:',ap:6); end. 這是一個(gè)典型循環(huán)隊(duì)列的例子，不少書上還有其他一些實(shí)現(xiàn)方法。例3 下面這個(gè)矩形是由數(shù)字0到9組成，其中數(shù)字0代表樹，19代表是猴子，凡是由0或矩形邊圍起來的區(qū)域表示有一群猴子在這一帶，給定數(shù)字矩形，求矩形中有多少群猴子。輸入（m

14、onkey.in）輸出（monkey.out）4 10 (表示矩形的行數(shù)和列數(shù))(下面四個(gè)色塊就代表四個(gè)猴群)分析(1)讀入m×n矩陣陣列，將其轉(zhuǎn)換為boolean矩陣存入數(shù)組bz中，有猴子的位置為true,沒有猴子的位置的false。 （2）沿著數(shù)組 bz矩陣從上到下，從左到右，找到遇到的第一個(gè)猴子。 （3）將猴子的位置入隊(duì)h,并沿其上、下、左、右四個(gè)方向上的猴子位置入隊(duì)，入隊(duì)后的位置bz數(shù)組置為false. (4)將h隊(duì)的隊(duì)頭出隊(duì)，沿其上、下、左、右四個(gè)方向上的猴子位置入隊(duì)，入隊(duì)后的位置bz數(shù)組置為false。 （5）重復(fù)（4），直至h隊(duì)空為止，則此時(shí)找出了一個(gè)猴群。

15、（6）重復(fù)（2），直到矩陣找不到猴群。 （7）輸出找到的猴群數(shù)。參考程序program P13_4; const dx:array1.4 of -1.1=(-1,0,1,0); dy:array1.4 of -1 .1=(0,1,0,-1); 定義常量數(shù)組，表示從四個(gè)方向搜索var pic:array1.50,1.79 of byte; 存放數(shù)字矩形 bz:array1.50,1.79 of boolean 用于存放轉(zhuǎn)換過來的數(shù)字矩形 m,n,i,j,num:integer; h:array1.4000,1.2 of byte; s:string;procedure doing(p,q:int

16、eger); var i,t,w,x,y:integer; begin inc(num); bzp,q:=false; 猴子離開原來的位置 t:=1;w:=1; h1,1:=p h1,2:=q 遇到的第一個(gè)猴子入隊(duì) repeat for i:=1 to 4 do 沿猴子的上下左右四個(gè)方向搜索猴子 begin x:=ht,1+dxi; y:=ht,2+dyi; if (x>0) and (x<m) and (y>0) and (y<=n) and bzx,y then begin 猴子的入隊(duì) inc(w); hw,1:=x; hw,2:=y; bzx,y:=false;

17、end; end; inc(t); until t>w; end; begin 主程序 fillchar(bz,sizeof(bz),true);num:=0; 初始化標(biāo)志數(shù)組 assign(input,'monkey.in'); assign(output,'monkey.out'); reset(m,n);rewrite(output); 打開文件 read(m,n); 讀入數(shù)字矩形并轉(zhuǎn)換成布爾數(shù)組 for i:=1 to m do begin readln(s); for j:=1 to n do begin pici,j:=ord(sj)-ord(

18、'0'); if pici,j=0 then bzi,j:=false 根據(jù)是否為o修改布爾組 else bzi,j:=true; end; end; for i:=1 to m do 從上到下，從左到右開始尋找 for j:=1 to n do if bzi,j then doing(i,j); 調(diào)用子程序在數(shù)字矩陣中找猴子writeln('NUMBER of cells=',num);readln; close(output); close(input);end.展示實(shí)力1、選擇題：（1）隊(duì)列的操作特點(diǎn)是（ ）。 A.先進(jìn)先出 B.先進(jìn)后出 C.有時(shí)先進(jìn)先出，有時(shí)先進(jìn)后出 D.不能確定（2）已知隊(duì)列（13，2，11，34，41，77，5，7，18，26，15）第一個(gè)進(jìn)入隊(duì)列的元素是13，則第五個(gè)出隊(duì)列的元素是（ ）。 A.5 B.41 C.77 D.13 E.18(3)假設(shè)以數(shù)組am存放循環(huán)隊(duì)列的元素，用front表示隊(duì)頭，用rear表示隊(duì)尾，則當(dāng)前隊(duì)列中的元素個(gè)數(shù)為（ ）。A.(rear-front+m) m