第13课单行道问题——队列

1、第13课 单行道问题 队列 由于前面修路，交警叔叔把路改成了单行道，所有的车只能在入口排好一辆一辆地进入单行公路，在单行道中不能超车（因为公路的宽度只能够让一辆车通过），也不能后退（因为后面有车退不动），只有当它前面没有其他车的时候才能通过单行道出去，现在楠楠的车也在单行道中，她想知道自己是第几个开出单行道的人，你能用程序来帮她吗？例如：用不同的字符串代表不同的车，现在有C,Bfd,G,H,Ns,DD,E,S,EG按上面的顺序进入了单行道，楠楠的车是H，刚好是第4部开出单行道的车。【分析】（1） 所有这些在单行道中的车可以看成是由不同字符串所组成的一个数据表，我们用数组a来表示这个数据表，其中

2、数据元素的下标，可以代表他们进入单行道时的顺序，如上例即是：a1='C',a2='Bfd',a9='EG'。（2） 由于在单行道中的车是先进入就先出去，所以可以从数组的第一个元素开始扫描查找目标字符串，如果没有找到，就继续向下扫描。否则就输出元素下标，即是所求。Nannan(H)CBfdGHNsDDESEG读入“楠楠“字串读入数量到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辆车进入了单行道 for i:=1 to n do readln(ai); 读入第i辆进入单行道中的车辆字符串 i:=0; repeat 从数组第一元素开始向后逐一查找代表楠楠车的字符串 i:=i+1; until ai=nannan; writeln(i); end.返回及进充电1、 队列在实际生活中上，我们坐公交车要排队上车，在超市买东西要排队付钱，这些就是我们常常见到的队列，它们的特点都是先到的排在前面，后到的排在后面。而在编程时，我们也用一种称为“队列”的数据组织

4、方式来模仿日常生活中的队列。 队列的操作特点是先进先出，后进后出，所有元素从一端进入，从另一端出去，就如汽车在单行道上行走时，只能在道路的一端进入，一端出去。我们把出去的一端称为“队首"(front),可以进入的一端称为“队尾”(rear)，如图13-1所示：出队列入队列a1a2a3an 队首 队尾 图13-1 队列示意图2、 循环队列如果用数组a1.n来存储队列时，数组的上界n即是队列所容许的最大容量，如图13-2所示，当最后一个位置an已使用而还有数据要入队时，则会产生“溢出”，但前面的队首可能因元素出队而空出很多空间，这样就会白白浪费空间，而且队列又不能继续入队。出队列入队列a

5、n 队首 队尾图13-2 队列可以产生溢出的情形为了解决上面问题，把前面空出来的可用空间利用起来，我们对有n个存储单元的队列，只利用前n-1个单元，而最后一个位置an用作提示指针，指向绕到第1个位置，形成逻辑上的环状空间，这样当front或rear到达整个数组的末尾时，又可以回到开头，这样的队列我们称它是循环队列。如图13-3所示：图13-3 循环队列示意图我们约定，如图13-3所示，队尾(rear)指示到当前队尾元素所在位置的下一位，队首(front)指示队列中第一元素在数组中的位置。队首(front)和队尾(rear)均可以环绕数组移动，队列中腾出的空间就可以再利用，当front和rear

6、的值大于了数组长度n时，我们就用求余运算使它们的值始终在1.n之间，就像时钟的指针经过了12点后总是又从1点开始一样(如17 mod 12=5).如图1-4所示，当队列的头尾重合，即front=rear时，这时队列为空;如图13-5所示，当front=(rear mod n)+1时，这时队列为满；其余时候，队列中的元素个数为：(rear-front+n) mod n。 图13-3 队列为空 图13-4 队列为满探索奥秘例1 芸芸和楠楠在玩扑克牌，她们共有n张扑克，这些扑克上分别记为1,2，n,芸芸打开扑克第一张是1，把它放在一边然后把最上面2张一张一张地依次移到最后，打开上面一张，刚好是3，放

7、在一边。如此继续下去，直至打开最后一张是n，放在一边，这时楠楠发现，放在一边的扑克刚好是按1,2，3n这样排列的，好想知道，在开始的时候应当怎样排放这些扑克，才能得到这样的结果，你能帮她写个程序求出扑克的最先排列顺序吗？例如：当n=5时，原排列是：1 4 5 2 3;当n=9时，原排列是：1 8 6 2 9 4 5 3 7分析(1)把n张牌看成是1n的n个数组成的队列，用数组a存放，用h指向队列a的队首。 (2)用数组b来表示要求的原排列，因为b中的入队元素来自a中的出队元素，所以有bi=ah,显然b1=a1，其值均为1，令h的初值为2。 (3)用t 表示a的队尾，从队首移动1张到队尾，则队尾

8、加1，将队首值ah赋给at;重复这个过程i次。 (4)当前值ah出队，并要在b中入队，用i指向b队尾，则bi:=ah. (5)重复(3)(4)两步，直到n张牌都拿出了为止。例如当n=4时的求解过程如图13-6所示：123456789a 1b 把1放在一边，向后移动两张423a 14b 把4放在一边，向后移动三张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); 读入队列的元素个数for i:=1 to n do ai:=i; 给数组赋初值，元素值和下标相同h:=2;t:=n;b1:=1; 第一个进入队列b的数for i:=2 to n do 还有2n个数要进入队列b begin for j:=1 to i do 把i张牌一张一张地移动到后面 begin inc(t); at:=ah; 从队列前面开始逐一把i个牌移动到队列后面 inc(h); 修改指向的第一张 end; bi:=ah; 把放在一边的这一张i inc(h); end;for i:=1 to n do write(bi);writeln end. 这是一

10、个典型队列的例子，请大家仔细体会在队列操作过程中队首和队尾的变化。 例2 花果山今天可热闹了，猴子们打算选出一个自己的大王。经过协商，决定选大王的规则如下：n只猴子围成一圈，每只猴子只有一个编号，编号从1到n，现在从第一只开始报数，报到m的猴子出圈，下一只猴子接着又从1开始报数，报到m时又出圈，最后剩下来的就是大王。请你编程计算求最后剩下的猴子原来的编号k。例如：当n=10，m=3时，k=4;当n=20，m=3时，k=20。分析此题是由古罗马著名史学家约瑟夫提出的问题演变而来的，所以通常称为约瑟夫问题。(1) 首先考虑如何组织数据，要记录n只猴子的状态，可利用含n个元素的数组a来实现。(2)

11、利用元素下标代表猴子的编号，元素的值记录排在它后面猴子编号，如a1=2,则表示当前猴子是1，其后面是编号为2的猴子。由于猴子排成的是一圈，所以有：an=1。如当n=5时，实际排队的情形如图13-7所示：23451 a1 a2 a3 a4 a5 图13-7 5只猴子的排队情况(3) 可以采用模拟选举过程的方法来求解，将报数变量t置为1，用变量P表示当前报数的猴子的编号，用q表示之前的一个报数的猴子的编号。(4) 当报数达到m的倍数时，当前报数的猴子P出圈，p的前一个和后一个猴子变为邻居。用aq:=ap实现。(5) 然后继续往下报数，直到圈中只剩下一只猴子即p=aq时为止。参考程序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; 用数组下标表示猴子编号，用元素的值记录下一个猴子的编号an:=1; 由于猴子是站成一圈，所以最后第n只猴子与第一个猴子相邻q:=n; p:=n; t:=0;repeat p:=ap; p表示从哪个猴子开始报数 t:=t+1; t表示当前报数和具体数字 if (t mod m<>0) then q:=p 没有数到整数m倍时，则继续数数 else aq:=ap;

13、 否则前一猴子和后一猴子变成邻居 until(p=ap); 当前猴子和其下一个猴子都是同一只猴子时结束循环 writeln('The total number:',n:3); writeln('The max number to call:',m:3); writeln('The leadger:',ap:6); end. 这是一个典型循环队列的例子，不少书上还有其他一些实现方法。例3 下面这个矩形是由数字0到9组成，其中数字0代表树，19代表是猴子，凡是由0或矩形边围起来的区域表示有一群猴子在这一带，给定数字矩形，求矩形中有多少群猴子。输入（m

14、onkey.in）输出（monkey.out）4 10 (表示矩形的行数和列数)(下面四个色块就代表四个猴群)分析(1)读入m×n矩阵阵列，将其转换为boolean矩阵存入数组bz中，有猴子的位置为true,没有猴子的位置的false。 （2）沿着数组 bz矩阵从上到下，从左到右，找到遇到的第一个猴子。 （3）将猴子的位置入队h,并沿其上、下、左、右四个方向上的猴子位置入队，入队后的位置bz数组置为false. (4)将h队的队头出队，沿其上、下、左、右四个方向上的猴子位置入队，入队后的位置bz数组置为false。 （5）重复（4），直至h队空为止，则此时找出了一个猴群。

15、（6）重复（2），直到矩阵找不到猴群。 （7）输出找到的猴群数。参考程序program P13_4; const dx:array1.4 of -1.1=(-1,0,1,0); dy:array1.4 of -1 .1=(0,1,0,-1); 定义常量数组，表示从四个方向搜索var pic:array1.50,1.79 of byte; 存放数字矩形 bz:array1.50,1.79 of boolean 用于存放转换过来的数字矩形 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 遇到的第一个猴子入队 repeat for i:=1 to 4 do 沿猴子的上下左右四个方向搜索猴子 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 猴子的入队 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; 初始化标志数组 assign(input,'monkey.in'); assign(output,'monkey.out'); reset(m,n);rewrite(output); 打开文件 read(m,n); 读入数字矩形并转换成布尔数组 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 根据是否为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); 调用子程序在数字矩阵中找猴子writeln('NUMBER of cells=',num);readln; close(output); close(input);end.展示实力1、选择题：（1）队列的操作特点是（ ）。 A.先进先出 B.先进后出 C.有时先进先出，有时先进后出 D.不能确定（2）已知队列（13，2，11，34，41，77，5，7，18，26，15）第一个进入队列的元素是13，则第五个出队列的元素是（ ）。 A.5 B.41 C.77 D.13 E.18(3)假设以数组am存放循环队列的元素，用front表示队头，用rear表示队尾，则当前队列中的元素个数为（ ）。A.(rear-front+m) m