А. шень Издание шестое, дополненное Москва
 Скачать 1.62 Mb.
|
|
6.1.2. Как упростится программа, если известно, что в последова- тельности могут быть только круглые скобки? Решение. В этом случае от стека остаётся лишь его длина, и мы фак- 100 6. Типы данных тически приходим к такому утверждению: последовательность круг- лых скобок правильна тогда и только тогда, когда в любом её началь- ном отрезке число закрывающихся скобок не превосходит числа откры- вающихся, а для всей последовательности эти числа равны. 6.1.3. Реализуйте с помощью одного массива два стека, суммар- ное количество элементов в которых ограничено длиной массива; все действия со стеками должны выполняться за время, ограниченное кон- стантой, не зависящей от длины стеков. Решение. Стеки должны расти с концов массива навстречу друг другу: первый должен занимать места Содержание[1] . . . Содержание[Длина1], а второй | Содержание[n] . . . Содержание[n-Длина2+1] (вершины обоих стеков записаны последними). 6.1.4. Реализуйте k стеков с элементами типа T, общее количество элементов в которых не превосходит n, с использованием массивов сум- марной длины 𝐶(n + k), затрачивая на каждое действие со стеками (кроме начальных действий, делающих все стеки пустыми) время не более некоторой константы 𝐶. (Как говорят, общая длина массивов должна быть 𝑂(m + n), a время на каждую операцию | 𝑂(1).) Решение. Применяемый метод называется «ссылочной реализацией». Он использует три массива: Содержание: array [1..n] of T; Следующий: array [1..n] of 0..n; Вершина: array [1..k] of 0..n. Удобно изображать массив Содержание как n ячеек с номера- ми 1 . . . n, каждая из которых содержит элемент типа T. Массив Следующий изобразим в виде стрелок, проведя стрелку из i в j, ес- ли Следующий[i]=j. (Если Следующий[i]=0, стрелок из i не прово- дим.) Содержимое s-го стека (s ∈ 1 . . . k) хранится так: вершина равна Содержание[Вершина[s]], остальные элементы s-го стека можно найти, идя по стрелкам | до тех пор, пока они не кончатся. При этом (s-й стек пуст) ⇔ Вершина[s]=0. 6.1. Стеки 101 Стрелочные траектории, выходящие из Вершина[1], . . . , Вершина[k] (из тех, которые не равны 0) не должны пересекаться. Помимо них, нам понадобится ещё одна стрелочная траектория, содержащая все не- используемые в данный момент ячейки. Её начало мы будем хранить в переменной Свободная (равенство Свободная = 0 означает, что пусто- го места не осталось). Вот пример: Вершина Содержание Свободная a p q d s t v w Содержание a p q d s t v w Следующий 3 0 6 0 0 2 5 4 Вершина 1 7 Свободная = 8 Стеки: первый содержит p, t, q, a (a | вершина); второй содержит s, v (v | вершина). procedure Начать_работу; {Делает все стеки пустыми} var i: integer; begin for i := 1 to k do begin Вершина [i]:=0; end; for i := 1 to n-1 do begin Следующий [i] := i+1; end; Следующий [n] := 0; 102 6. Типы данных Свободная:=1; end; function Есть_место: boolean; begin Есть_место := (Свободная <> 0); end; procedure Добавить (t: T; s: integer); {Добавить t к s-му стеку} var i: 1..n; begin {Есть_место} i := Свободная; Свободная := Следующий [i]; Следующий [i] := Вершина [s]; Вершина [s] :=i; Содержание [i] := t; end; function Пуст (s: integer): boolean; {s-ый стек пуст} begin Пуст := (Вершина [s] = 0); end; procedure Взять (var t: T; s: integer); {взять из s-го стека в t} var i: 1..n; begin {not Пуст (s)} i := Вершина [s]; t := Содержание [i]; Вершина [s] := Следующий [i]; Следующий [i] := Свободная; Свободная := i; end; function Вершина_стека (s: integer): T; {вершина s-го стека} begin Вершина_стека := Содержание[Вершина[s]]; end; 6.2. Очереди 103 6.2. Очереди Значениями типа «очередь элементов типа T», как и для стеков, явля- ются последовательности значений типа T. Разница состоит в том, что берутся элементы не с конца, а с начала (а добавляются по-прежнему в конец). Операции с очередями: ∙ Сделать пустой (var x: очередь элементов типа T); ∙ Добавить (t:T, var x: очередь элементов типа T); ∙ Взять (var t:T, var x: очередь элементов типа T); ∙ Пуста (x: очередь элементов типа T): boolean; ∙ Очередной (x: очередь элементов типа T): T. При выполнении команды «Добавить» указанный элемент добавля- ется в конец очереди. Команда «Взять» выполнима, лишь если очередь непуста, и забирает из неё первый (положенный туда раньше всех) эле- мент, помещая его в t. Значением функции «Очередной» (определённой для непустой очереди) является первый элемент очереди. Английские названия стеков | Last In First Out (последним во- шёл | первым вышел), а очередей | First In First Out (первым вошёл | первым вышел). Сокращения: LIFO, FIFO. Реализация очередей в массиве 6.2.1. Реализуйте операции с очередью ограниченной длины так, чтобы количество действий для каждой операции было ограничено кон- стантой, не зависящей от длины очереди. Решение. Будем хранить элементы очереди в соседних элементах массива. Тогда очередь будет прирастать справа и убывать слева. По- скольку при этом она может дойти до края, свернём массив в окруж- ность. Введём массив Содержание: array [0..n-1] of T и переменные Первый: 0..n-1, Длина : 0..n. 104 6. Типы данных При этом элементами очереди будут Содержание [Первый], Содержание [Первый+1], . . . , Содержание [Первый+Длина-1], где сложение выполняется по модулю n. (Предупреждение. Если вместо этого ввести переменные Первый и Последний, значения которых | вы- четы по модулю n, то пустая очередь может быть спутана с очередью из n элементов.) Операции выполняются так. Сделать пустой: Длина := 0; Первый := 0; Добавить элемент: {Длина < n} Содержание [(Первый + Длина) mod n] := элемент; Длина := Длина + 1; Взять элемент: {Длина > 0} элемент := Содержание [Первый]; Первый := (Первый + 1) mod n; Длина := Длина - 1; Пуста: Длина = 0 Очередной: Содержание [Первый] 6.2.2. (Сообщил А. Г. Кушниренко) Придумайте способ моделиро- вания очереди с помощью двух стеков (и фиксированного числа пере- менных типа T). При этом отработка n операций с очередью (начатых, когда очередь была пуста) должна требовать порядка n действий. Решение. Инвариант: стеки, составленные концами, образуют оче- редь. (Перечисляя элементы одного стека вглубь и затем элементы вто- рого наружу, мы перечисляем все элементы очереди от первого до по- следнего.) Ясно, что добавление сводится к добавлению к одному из 6.2. Очереди 105 стеков, а проверка пустоты | к проверке пустоты обоих стеков. Ес- ли мы хотим взять элемент, есть два случая. Если стек, где находится начало очереди, не пуст, то берём из него элемент. Если он пуст, то предварительно переписываем в него все элементы второго стека, ме- няя порядок (это происходит само собой при перекладывании из стека в стек) и сводим дело к первому случаю. Хотя число действий на этом шаге и не ограничено константой, но требование задачи выполнено, так как каждый элемент очереди может участвовать в этом процессе не более одного раза. 6.2.3. Деком называют структуру, сочетающую очередь и стек: класть и забирать элементы можно с обоих концов. Как реализовать дек ограниченного размера на базе массива так, чтобы каждая опера- ция требовала ограниченного числа действий? 6.2.4. (Сообщил А. Г. Кушниренко.) Имеется дек элементов типа T и конечное число переменных типа T и целого типа. В начальном со- стоянии в деке некоторое число элементов. Составьте программу, после исполнения которой в деке остались бы те же самые элементы, а их чи- сло было бы в одной из целых переменных. [Указание. (1) Элементы дека можно циклически переставлять, за- бирая с одного конца и помещая в другой. После этого, сделав столько же шагов в обратном направлении, можно вернуть всё на место. (2) Как понять, прошли мы полный круг или не прошли? Если бы какой-то эле- мент заведомо отсутствовал в деке, то можно было бы его подсунуть и ждать вторичного появления. Но таких элементов нет. Вместо этого можно для данного n выполнить циклический сдвиг на n дважды, под- сунув разные элементы, и посмотреть, появятся ли разные элементы через n шагов.] Применение очередей 6.2.5. Напечатайте в порядке возрастания первые n натуральных чисел, в разложение которых на простые множители входят только чи- сла 2, 3, 5. Решение. Введём три очереди x2, x3, x5, в которых будем хранить элементы, которые в 2 (3, 5) раз больше напечатанных, но ещё не на- печатаны. Определим процедуру procedure напечатать_и_добавить (t: integer); begin 106 6. Типы данных writeln (t); Добавить (2*t, x2); Добавить (3*t, x3); Добавить (5*t, x5); end; Вот схема программы: ...сделать x2, x3, x5 пустыми напечатать_и_добавить (1); k := 1; { k - число напечатанных } {инвариант: напечатано в порядке возрастания k минимальных членов нужного множества; в очередях элементы, вдвое, втрое и впятеро большие напечатанных, но не напечатанные, расположенные в возрастающем порядке} while k <> n do begin x := min (очередной(x2), очередной(x3), очередной(x5)); напечатать_и_добавить (x); k := k+1; ...взять x из тех очередей, где он был очередным; end; Пусть инвариант выполняется. Рассмотрим наименьший из ненапе- чатанных элементов множества; пусть это x. Тогда он делится нацело на одно из чисел 2, 3, 5, и частное также принадлежит множеству. Зна- чит, оно напечатано. Значит, x находится в одной из очередей и, сле- довательно, является в ней первым (меньшие напечатаны, а элементы очередей не напечатаны). Напечатав x, мы должны его изъять и доба- вить его кратные. Длины очередей не превосходят числа напечатанных элементов. Следующая задача связана с графами (к которым мы вернёмся в гла- ве 9 ). Пусть задано конечное множество, элементы которого называют вершинами, а также некоторое множество упорядоченных пар вершин, называемых рёбрами. В этом случае говорят, что задан ориентирован- ный граф. Пару ⟨𝑝, 𝑞⟩ называют ребром с началом 𝑝 и концом 𝑞; говорят также, что оно выходит из вершины 𝑝 и входит в вершину 𝑞. Обычно вершины графа изображают точками, а рёбра | стрелками, ведущими из начала в конец. (В соответствии с определением из данной верши- ны в данную ведёт не более одного ребра; возможны рёбра, у которых начало совпадает с концом.) 6.2.6. Известно, что ориентированный граф связен, т. е. из любой вершины можно пройти в любую по рёбрам. Кроме того, из каждой 6.2. Очереди 107 вершины выходит столько же рёбер, сколько входит. Докажите, что су- ществует замкнутый цикл, проходящий по каждому ребру ровно один раз. Составьте алгоритм отыскания такого цикла. Решение. Змеёй будем называть непустую очередь из вершин, в ко- торой любые две вершины соединены ребром графа (началом является та вершина, которая ближе к началу очереди). Стоящая в начале очере- ди вершина будет хвостом змеи, последняя | головой. На рисунке змея изобразится в виде цепи рёбер графа, стрелки ведут от хвоста к голо- ве. Добавление вершины в очередь соответствует росту змеи с головы, взятие вершины | отрезанию кончика хвоста. Вначале змея состоит из единственной вершины. Далее мы следуем такому правилу: while змея включает не все рёбра do begin if из головы выходит не входящее в змею ребро then begin удлинить змею этим ребром end else begin {голова змеи в той же вершине, что и хвост} отрезать конец хвоста и добавить его к голове {"змея откусывает конец хвоста"} end; end; Докажем, что мы достигнем цели. (1) Идя по змее от хвоста к голове, мы входим в каждую вершину столько же раз, сколько выходим. Так как в любую вершину входит столько же рёбер, сколько выходит, то невозможность выйти означает, что голова змеи в той же точке, что и хвост. (2) Змея не укорачивается, поэтому либо она охватит все рёбра, либо, начиная с некоторого момента, будет иметь постоянную длину. Во втором случае змея будет бесконечно «скользить по себе». Это воз- можно, только если из всех вершин змеи не выходит неиспользованных рёбер. В этом случае из связности следует, что змея проходит по всем рёбрам. Замечание по реализации на паскале. Вершинами графа будем счи- тать числа 1 . . . n. Для каждой вершины i будем хранить число Out[i] выходящих из неё рёбер, а также номера Num[i][1],. . . ,Num[i][Out[i]] тех вершин, куда эти рёбра ведут. В процессе построения змеи будем выбирать первое свободное ребро. Тогда достаточно хранить для ка- ждой вершины число выходящих из неё использованных рёбер | это будут рёбра, идущие в начале списка. 108 6. Типы данных 6.2.7. Докажите, что для всякого 𝑛 существует последовательность нулей и единиц длины 2 𝑛 со следующим свойством: если «свернуть её в кольцо» и рассмотреть все фрагменты длины 𝑛 (их число равно 2 𝑛 ), то мы получим все возможные последовательности нулей и единиц дли- ны 𝑛. Постройте алгоритм отыскания такой последовательности, тре- бующий не более 𝐶 𝑛 действий для некоторой константы 𝐶. [Указание. Рассмотрим граф, вершинами которого являются после- довательности нулей и единиц длины 𝑛 − 1. Будем считать, что из вер- шины 𝑥 ведёт ребро в вершину 𝑦, если 𝑥 может быть началом, а 𝑦 | концом некоторой последовательности длины 𝑛. Тогда из каждой вер- шины входит и выходит два ребра. Цикл, проходящий по всем рёбрам, и даст требуемую последовательность.] 6.2.8. Реализуйте 𝑘 очередей с ограниченной суммарной длиной 𝑛, используя память 𝑂(𝑛 + 𝑘) [= не более 𝐶(𝑛 + 𝑘) для некоторой кон- станты 𝐶], причём каждая операция (кроме начальной, делающей все очереди пустыми) должна требовать ограниченного константой числа действий. Решение. Действуем аналогично ссылочной реализации стеков: мы помним (для каждой очереди) первого, каждый участник очереди по- мнит следующего за ним (для последнего считается, что за ним стоит фиктивный элемент с номером 0). Кроме того, мы должны для каждой очереди знать последнего (если он есть) | иначе не удастся добавлять. Как и для стеков, отдельно есть цепь свободных ячеек. Заметим, что для пустой очереди информация о последнем элементе теряет смысл | но она и не используется при добавлении. Содержание: array [1..n] of T; Следующий: array [1..n] of 0..n; Первый: array [1..k] of 0..n; Последний: array [1..k] of 0..n; Свободная : 0..n; procedure Сделать_пустым; var i: integer; begin for i := 1 to n-1 do begin Следующий [i] := i + 1; end; Следующий [n] := 0; Свободная := 1; for i := 1 to k do begin 6.2. Очереди 109 Первый [i]:=0; end; end; function Есть_место : boolean; begin Есть_место := Свободная <> 0; end; function Пуста (номер_очереди: integer): boolean; begin Пуста := Первый [номер_очереди] = 0; end; procedure Взять (var t: T; номер_очереди: integer); var перв: integer; begin {not Пуста (номер_очереди)} перв := Первый [номер_очереди]; t := Содержание [перв] Первый [номер_очереди] := Следующий [перв]; Следующий [перв] := Свободная; Свободная := перв; end; procedure Добавить (t: T; номер_очереди: integer); var нов, посл: 1..n; begin {Есть_место } нов := Свободная; Свободная := Следующий [Свободная]; {из списка свободного места изъят номер нов} if Пуста (номер_очереди) then begin Первый [номер_очереди] := нов; Последний [номер_очереди] := нов; Следующий [нов] := 0; Содержание [нов] := t; end else begin посл := Последний [номер_очереди]; {Следующий [посл] = 0 } Следующий [посл] := нов; Следующий [нов] := 0; Содержание [нов] := t Последний [номер_очереди] := нов; end; end; 110 6. Типы данных function Очередной (номер_очереди: integer): T; begin Очередной := Содержание [Первый [номер_очереди]]; end; 6.2.9. Та же задача для деков вместо очередей. [Указание. Дек | структура симметричная, поэтому надо хранить ссылки в обе стороны (вперёд и назад). При этом удобно к каждому деку добавить фиктивный элемент, замкнув его в кольцо, и точно такое же кольцо образовать из свободных позиций.] В следующей задаче дек используется для хранения вершин вы- пуклого многоугольника. 6.2.10. На плоскости задано 𝑛 точек, пронумерованных слева на- право (а при равных абсциссах | снизу вверх). Составьте программу, которая строит многоугольник, являющийся их выпуклой оболочкой, за 𝑂(𝑛) [= не более чем 𝐶𝑛] действий. Решение. Будем присоединять точки к выпуклой оболочке одна за другой. Легко показать, что последняя присоединённая точка будет одной из вершин выпуклой оболочки. Эту вершину мы будем назы- вать выделенной. Очередная присоединяемая точка видна из выделен- ной (почему?). Дополним наш многоугольник, выпустив из выделенной вершины «иглу», ведущую в присоединяемую точку. Получится выро- жденный многоугольник, и остаётся ликвидировать в нём «впуклости». r r r r r r r r P P P P P P A A A A B B B B B B H H H H H H H Будем хранить вершины многоугольника в деке в порядке обхода его периметра по часовой стрелке. При этом выделенная вершина явля- ется началом и концом (головой и хвостом) дека. Присоединение «иглы» теперь состоит в добавлении присоединяемой вершины в голову и в 6.3. Множества 111 хвост дека. Устранение впуклостей несколько более сложно. Назовём подхвостом и подподхвостом элементы дека, стоящие за его хвостом. Устранение впуклости у хвоста делается так: while по дороге из хвоста в подподхвост мы поворачиваем у подхвоста влево ("впуклость") do begin выкинуть подхвост из дека end Таким же способом устраняется впуклость у головы дека. Замечание. Действия с подхвостом и подподхвостом не входят в определение дека, однако сводятся к небольшому числу манипуляций с деком (надо забрать три элемента с хвоста, сделать что надо и вер- нуть). Ещё одно замечание. Есть два вырожденных случая: если мы во- обще не поворачиваем у подхвоста (т. е. три соседние вершины лежат на одной прямой) и если мы поворачиваем на 180 ∘ (так бывает, если наш многоугольник есть двуугольник). В первом случае подхвост сто- ит удалить (чтобы в выпуклой оболочке не было лишних вершин), а во втором случае | обязательно оставить. 6.3. Множества Пусть T | некоторый тип. Существует много способов хранить (ко- нечные) множества элементов типа T; выбор между ними определяется типом T и набором требуемых операций. Подмножества множества {1 . . . 𝑛} 6.3.1. Как, используя память размера 𝑂(𝑛) [пропорциональную 𝑛], |