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

第第 13 课课 单行道问题单行道问题 队列队列 由于前面修路 交警叔叔把路改成了单行道 所有的车只能在入口排好一辆一辆地进入单行公 路 在单行道中不能超车 因为公路的宽度只能够让一辆车通过 也不能后退 因为后面有车退不 动 只有当它前面没有其他车的时候才能通过单行道出去 现在楠楠的车也在单行道中 她想知道 自己是第几个开出单行道的人 你能用程序来帮她吗 例如 用不同的字符串代表不同的车 现在有 C Bfd G H Ns DD E S EG 按上面的顺序进入了 单行道 楠楠的车是 H 刚好是第 4 部开出单行道的车 分析 1 所有这些在单行道中的车可以看成是由不同字符串所组成的一个数据表 我们用 数组 a 来表示这个数据表 其中数据元素的下标 可以代表他们进入单行道时的 顺序 如上例即是 a 1 C a 2 Bfd a 9 EG 2 由于在单行道中的车是先进入就先出去 所以可以从数组的第一个元素开始扫描 查找目标字符串 如果没有找到 就继续向下扫描 否则就输出元素下标 即是 所求 参考程序 Program p13 1 Var a array i 100 of string i n integer nannan string begin readln nannan 读入代表楠楠的车的字串 readln n 读入共有 n 辆车进入了单行道 for i 1 to n do readln a i 读入第 i 辆进入单行道中的车辆字符串 i 0 repeat 从数组第一元素开始向后逐一查找代表楠楠车的字符串 i i 1 Nannan H C Bfd G H Ns DD E S EG 读入 楠楠 字串 读入数量到 n a i nannan For i 1 to n do readln a i 输出 i 的值 N until a i nannan writeln i end 返回 及进充电 1 队列 在实际生活中上 我们坐公交车要排队上车 在超市买东西要排队付钱 这些就是我们常常见到 的队列 它们的特点都是先到的排在前面 后到的排在后面 而在编程时 我们也用一种称为 队列 的数据组织方式来模仿日常生活中的队列 队列的操作特点是先进先出 后进后出先进先出 后进后出 所有元素从一端进入 从另一端出去 就如汽车在单 行道上行走时 只能在道路的一端进入 一端出去 我们把出去的一端称为 队首 front 可以进 入的一端称为 队尾 rear 如图 13 1 所示 a1a2a3 an 队首 队尾 图 13 1 队列示意图 2 循环队列 如果用数组 a 1 n 来存储队列时 数组的上界 n 即是队列所容许的最大容量 如图 13 2 所示 当 最后一个位置 an已使用而还有数据要入队时 则会产生 溢出 但前面的队首可能因元素出队而 空出很多空间 这样就会白白浪费空间 而且队列又不能继续入队 an 队首 队尾 图 13 2 队列可以产生溢出的情形 为了解决上面问题 把前面空出来的可用空间利用起来 我们对有 n 个存储单元的队列 只 利用前 n 1 个单元 而最后一个位置 an用作提示指针 指向绕到第 1 个位置 形成逻辑上的环状 空间 这样当 front 或 rear 到达整个数组的末尾时 又可以回到开头 这样的队列我们称它是循 环队列 如图 13 3 所示 移动方向 队首 front 队列 队尾 rear 图 13 3 循环队列示意图 出队列入队列 出队列入队列 我们约定 如图 13 3 所示 队尾 rear 指示到当前队尾元素所在位置的下一位 队首 front 指 示队列中第一元素在数组中的位置 队首 front 和队尾 rear 均可以环绕数组移动 队列中腾出的空间就可以再利用 当 front 和 rear 的值大于了数组长度 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 队首 front 队尾rear 队首 front 队尾rear 图 13 3 队列为空 图 13 4 队列为满 探索奥秘探索奥秘 例 1 芸芸和楠楠在玩扑克牌 她们共有 n 张扑克 这些扑克上分别记为 1 2 n 芸芸打 开扑克第一张是 1 把它放在一边然后把最上面 2 张一张一张地依次移到最后 打开 上面一张 刚好是 3 放在一边 如此继续下去 直至打开最后一张是 n 放 在一边 这时楠楠发现 放在一边的扑克刚好是按 1 2 3 n 这样排列的 好想知 道 在开始的时候应当怎样排放这些扑克 才能得到这样的结果 你能帮她写个程序 求出扑克的最先排列顺序吗 例如 当 n 5 时 原排列是 1 4 5 2 3 当 n 9 时 原排列是 1 8 6 2 9 4 5 3 7 分析 1 把 n 张牌看成是 1 n 的 n 个数组成的队列 用数组 a 存放 用 h 指向队列 a 的队 首 2 用数组 b 来表示要求的原排列 因为 b 中的入队元素来自 a 中的出队元素 所以 有 b i a h 显然 b 1 a 1 其值均为 1 令 h 的初值为 2 3 用 t 表示 a 的队尾 从队首移动 1 张到队尾 则队尾加 1 将队首值 a h 赋给 a t 重复这个过程 i 次 4 当前值 a h 出队 并要在 b 中入队 用 i 指向 b 队尾 则 b i a h 5 重复 3 4 两步 直到 n 张牌都拿出了为止 例如当 n 4 时的求解过程如图 13 6 所示 a b 把 1 放在一边 向后移动两张 a b 把 4 放在一边 向后移动三张 a b 把 3 放在一边 剩下最后一张 a b 最后 1 张 直接放到一边去 图 13 6 4 张扑克的求解过程 参考程序 Progrm P13 2 var a b array 1 1000 of integer i j t h n integer begin write N readln n 读入队列的元素个数 for i 1 to n do a i i 给数组赋初值 元素值和下标相同 h 2 t n b 1 1 第一个进入队列 b 的数 for i 2 to n do 还有 2 n 个数要进入队列 b begin for j 1 to i do 把 i 张牌一张一张地移动到后面 begin inc t a t a h 从队列前面开始逐一把 i 个牌移动到队列后面 inc h 修改指向的第一张 end 123456789 1 423 14 32 143 2 14 b i a h 把放在一边的这一张 i inc h end for i 1 to n do write b i writeln end 这是一个典型队列的例子 请大家仔细体会在队列操作过程中队首和队尾的变化 例 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 利用元素下标代表猴子的编号 元素的值记录排在它后面猴子编号 如 a 1 2 则表示 当前猴子是 1 其后面是编号为 2 的猴子 由于猴子排成的是一圈 所以有 a n 1 如当 n 5 时 实际排队的情形如图 13 7 所示 23451 a 1 a 2 a 3 a 4 a 5 图 13 7 5 只猴子的排队情况 3 可以采用模拟选举过程的方法来求解 将报数变量 t 置为 1 用变量 P 表示当前报数 的猴子的编号 用 q 表示之前的一个报数的猴子的编号 4 当报数达到 m 的倍数时 当前报数的猴子 P 出圈 p 的前一个和后一个猴子变为邻居 用 a q a p 实现 5 然后继续往下报数 直到圈中只剩下一只猴子即 p a q 时为止 参考程序 Program P13 3 const num 50 var a array 1 num of integer i p q t m n integer begin readln n m for i 1 to n 1 do a i i 1 用数组下标表示猴子编号 用元素的值记录下一 个猴子的编号 a n 1 由于猴子是站成一圈 所以最后第 n 只猴子与第一个猴子相邻 q n p n t 0 repeat p a p p 表示从哪个猴子开始报数 t t 1 t 表示当前报数和具体数字 if t mod m0 then q p 没有数到整数 m 倍时 则继续数数 else a q a p 否则前一猴子和后一猴子变成邻居 until p a p 当前猴子和其下一个猴子都是同一只猴子时结束循环 writeln The total number n 3 writeln The max number to call m 3 writeln The leadger a p 6 end 这是一个典型循环队列的例子 不少书上还有其他一些实现方法 例 3 下面这个矩形是由数字 0 到 9 组成 其中数字 0 代表树 1 9 代表是猴子 凡是由 0 或矩形 边围起来的区域表示有一群猴子在这一带 给定数字矩形 求矩形中有多少群猴子 输入 monkey 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 队空为止 则此时找出了一个猴群 6 重复 2 直到矩阵找不到猴群 7 输出找到的猴群数 参考程序 program P13 4 const dx array 1 4 of 1 1 1 0 1 0 dy array 1 4 of 1 1 0 1 0 1 定义常量数组 表示从四个方向搜索 var pic array 1 50 1 79 of byte 存放数字矩形 bz array 1 50 1 79 of boolean 用于存放转换过来的数字矩形 m n i j num integer h array 1 4000 1 2 of byte s string procedure doing p q integer var i t w x y integer begin inc num bz p q false 猴子离开原来的位置 t 1 w 1 h 1 1 p h 1 2 q 遇到的第一个猴子入队 repeat for i 1 to 4 do 沿猴子的上下左右四个方向搜索猴子 begin x h t 1 dx i y h t 2 dy i if x 0 and x0 and yw 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 pic i j ord s j ord 0 if pic i j 0 then bz i j false 根据是否为 o 修改布尔组 else bz i j true end end for i 1 to m do 从上到下 从左到右开始寻找 for j 1 to n do if bz i 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 假设以数组 a m 存放循环队列的元素 用 front 表示队头 用 rear 表示队尾 则当前队列中的 元素个数为 A rear front m mod m B rear front 1 C front rear