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

第十三课单行道问题排队由于前面有路，交警叔叔把路改成了单行道。所有的汽车只能在入口处一辆接一辆地进入单行道。她既不能超车(因为道路的宽度只能让一辆车通过)，也不能后退(因为后面有车)。只有当前面没有其他汽车时，她才能穿过单行道出去。现在楠楠的车也在单行道上。她想知道她是谁。你能用这个程序帮助她吗？例如，不同的字符串被用来代表不同的汽车。现在，有C、Bfd、G、H、Ns、DD、E、S、EG按上述顺序进入单行道。楠楠的车是H，这是第四辆离开单行道的车。分析(1)单行道上的所有这些汽车可以看作是由不同字符串组成的数据表。我们使用数组A来表示这个数据表，其中数据元素的下标可以表示它们进入单行道的顺序。上面的例子是：1=C，2=BFD，9(2)由于单行道上的汽车先进入，先出去，所以可以从数组的第一个元素开始扫描目标字符串，如果不是，则继续向下扫描。否则，输出元素下标，即请求。楠楠(H)CBfdGHNsDDESEG读入“楠楠”字符串读取数量至n对于i:=1至n do read ln(aI)；N:=楠楠？输出I的值参考计划程序p13_1。var a :阵列i.100的字符串；I，n :整数；nannan an : string；开始read ln(nan nan)；读入代表楠楠汽车的字符串read ln(n)；将总共n辆车读入单行道对于i:=1至n doread ln(a .I );学习第一辆进入单行道的车辆的字符串I :=0；重复从数组的第一个元素开始，逐一查看代表楠楠汽车的字符串I :=I 1；直到一个I=楠楠；write ln(I)；结束。返回和充电1.长队在现实生活中，我们必须排队上车，在超市买东西。这些是我们经常看到的队列。它们的特点是第一个队列在前，第二个队列在后。在编程时，我们也使用一种叫做“队列”的数据组织方法来模拟日常生活中的队列。队列的操作特征是先进先出、后进先出。所有的元素都从一端进入，从另一端出去，就像一辆汽车在单行道上行走一样，它只能从路的一端进入，从另一端出去。如图13-1所示，我们将输出端称为“前端”，将可访问端称为“后端”。排队外排队等候第一等的主动脉第二声a3一第一队，最后一队图13-1队列图2.循环排队如果数组a为1.n用于存储队列，数组的上限n是队列允许的最大容量。如图13-2所示，当使用最后一个位置an并且仍然有数据要排队时，将会发生“溢出”,但是由于元素去排队，前队列头可能会有大量剩余空间，从而浪费空间并且队列不能继续排队。排队外排队等候一第一队，最后一队图13-2队列溢出情况为了解决上述问题，我们使用我们面前的自由空间。对于一个有N个存储单元的队列，我们只使用前n-1个单元，最后一个位置用作一个提示指针，指向第一个位置，形成一个逻辑环形空间。这样，当前端或后端到达整个阵列的末端时，我们就可以回到起点。这种队列称为循环队列。如图13-3所示：图13-3循环队列示意图我们同意，如图13-3所示，后面表示后面元素当前位置的下一位，前面表示数组中队列中第一个元素的位置。前端和后端都可以在阵列中移动，队列中空出的空间可以重新使用。当前后的值大于数组的长度n时，我们使用余数运算将它们的值保持在1之间.n一直如此，正如时钟的指针总是在12点后的1点开始(例如17 mod 12=5)。如图1-4所示，当队列的头部和尾部重合，即前端=原因时，此时队列为空；如图13-5所示，当front=(原因mod n) 1时，队列已满；在剩余的时间里，队列中的元素数量是：(原因前端n) mod n。图13-3队列为空图13-4队列已满发现例1云云和楠正在打牌。他们总共有n张卡片。这些卡片被标记为1，2，n .云打开卡片。第一张牌是1。把它放在一边，然后把最上面的两张牌一张一张地移到最后一张。打开上面的一个，只有3个，把它放在一边。这种情况一直持续到最后一张打开的牌是n，然后把它放在一边。然后楠楠发现放在一边的卡片只是按照1，2，3的顺序排列.所以他想知道如何在开始时安排这些卡片，以便得到这样的结果。你能帮她写一个程序找出扑克的第一顺序吗？例如，当n=5时，原始排列是：1 4 5 2 3；当n=9时，原始排列是：1 8 6 2 9 4 5 3 7分析 (1)把n张卡看作1n个数字的队列，把它们存储在数组a中，并把h指向队列a的头。(2)使用数组B表示所需的原始排列。因为B中的入队元素来自A中的出队元素，所以有bi=ah。很明显，b1=a1，它们的值都是1，使得H 2的初始值。(3) T用于表示A团队的结束。如果一块从团队的头移动到团队的末端，那么团队的末端加上1，并且头值ah被分配给t；重复这个过程一次。(4)ah的当前值是在b队之外，并且是进入b队，用I指着b队的末尾，然后bi:=ah。(5)重复步骤(3)和(4)，直到取出所有的N张卡片。例如，当n=4时，求解过程如图13-6所示。123456789a1把1放在一边，把2移回来。423a14把4放在一边，把3移回来。32a143把3放在一边，留下最后一个。2a14最后一个，把它放在一边图13-6 4张扑克的解决方案流程参考计划progrm P13 _ 2；var a，b:array1.1000的整数；I，j，t，h，n :整数；开始写(N)；read ln(n)；读入队列的元素数量对于i:=1到n做一个I:=I；给数组赋值初始值，元素值和下标相同h :=2；t :=n；b1:=1；第一个进入队列的数量B对于i:=2到n do 还有2到n个数字要进入队列b开始对于j:=1至ido(将I张牌一张一张地移回)开始Inc(t)；at:=ah；从队列的前面开始，将我的卡一张一张地移到队列的后面Inc(h)；修改第一个指向的结束；bI:=ah；抛开这个iInc(h)；结束；对于i:=1至n写(bI)；writeln结束。这是一个典型队列的例子，请仔细理解队列开头和结尾的变化。例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)元素的下标用来表示猴子的数量。元素的值记录了其后猴子的数量。如果1=2，则意味着当前的猴子是1，后面跟着数字为2的猴子。因为猴子被排列成一个圆圈，所以有：n=1。例如，当n=5时，实际的排队情况如图13-7所示。2345112345图13-7 5只猴子的队列(3)可以通过模拟选举过程，将计数变量T设置为1，用变量P表示计数当前数目的猴子的数目，用Q表示计数前一数目的猴子的数目来解决。(4)当报告的猴子数量达到M的倍数时，当前报告该数量的猴子P脱离该圈，并且P的前一只猴子和后一只猴子成为邻居。它是用q:=ap实现的。(5)然后继续倒数，直到圆圈中只剩下一只猴子，即p=aq。参考计划程序P13 _ 3；常量数=50；var a:array1.整数的num ;I，p，q，t，m，n :整数；开始read ln(n . m)；对于i:=1到n-1做一个I:=I 1；用数组下标表示猴子数，用元素值记录下一只猴子的数目n:=1；因为猴子站成一圈，最后一只猴子和第一只猴子相邻q:=n。p :=n；t :=0；重复p :=ap；p表示从哪只猴子开始计数t:=t 1。t表示当前的报告数量和具体数量如果(t mod m0)，则q:=p 如果不计数为整数m倍，继续计数q:=p；否则，前一只猴子和后一只猴子会成为邻居直到(p=ap)；当前猴子和下一只猴子是同一只猴子时，循环结束writeln(总数：n :3)；writeln(呼叫：m:3的最大号码)；领袖：，著，第：6页；结束。这是一个典型的循环队列的例子，在许多书中还有其他的实现方法。示例3下面的矩形由数字0到9组成，其中数字0代表树，1到9代表猴子。被0或矩形边包围的任何区域代表该区域中的一群猴子。给定数字矩形，找出矩形中有多少组猴子。输入(猴入)在外4 10(代表矩形的行数和列数)4(以下四个颜色块代表四个猴子组)02345000670234500067103456050010345605002045600671204560067100000000890000000089分析 (1)读入矩阵数组，将其转换成布尔矩阵并存储在数组bz中。猴子的位置是真的，猴子的位置是假的。(2)沿着阵列bz矩阵从上到下，从左到右，找到第一只猴子。(3)将猴子的位置放入团队h中，并将猴子的位置放入团队中沿上、下、左、右四个方向，并将bz数组设置为false。(4)将H队队长带出队伍，沿上下左右方向的猴位进入队伍。进入团队后，bz数组设置为false。(5)重复