А. Шень ðòïçòáííéòï÷áîéå ÔÅÏÒÅÍÙ É ÚÁÄÁÞÉ Издание седьмое, дополненное Москва

5.2. Ввод чисел
93
while (state <> Accept) or (state <> Error) do begin
if state = Initial then begin
if Next = ’ ’ then begin
state := Initial; Move;
end else if Digit(Next) then begin
state := IntPart; {после начала целой части}
Move;
end else begin
state := Error;
end;
end else if state = IntPart then begin
if Digit (Next) then begin
state := IntPart; Move;
end else if Next = ’.’ then begin
state := DecPoint; {после десятичной точки}
Move;
end else begin
state := Accept;
end;
end else if state = DecPoint then begin
if Digit (Next) then begin
state := FracPart; Move;
end else begin
state := Error; {должна быть хоть одна цифра}
end;
end else if state = FracPart then begin
if Digit (Next) then begin
state := FracPart; Move;
end else begin
state := Accept;
end;
end else if
{такого быть не может}
end;
end;
Заметьте, что присваивания state:=Accept и state:=Error не сопро-
вождаются сдвигом (символ, который не может быть частью числа, не
забирается).
Приведённая программа не запоминает значение прочитанного числа.
5.2.2. Решите предыдущую задачу с дополнительным требованием:
если прочитанный кусок является десятичной записью, то в перемен-
ную val:real следует поместить её значение.

94
5. Конечные автоматы и обработка текстов
Решение. При чтении дробной части переменная step хранит мно-
житель при следующей десятичной цифре.
state := Initial; val:= 0;
while (state <> Accept) or (state <> Error) do begin
if state = Initial then begin
if Next = ’ ’ then begin
state := Initial; Move;
end else if Digit(Next) then begin
state := IntPart; {после начала целой части}
val := DigitValue (Next); Move;
end else begin
state := Error;
end;
end else if state = IntPart then begin
if Digit (Next) then begin
state := IntPart; val := 10*val + DigitVal(Next);
Move;
end else if Next = ’.’ then begin
state := DecPoint; {после десятичной точки}
step := 0.1;
Move;
end else begin
state := Accept;
end;
end else if state = DecPoint then begin
if Digit (Next) then begin
state := FracPart;
val := val + DigitVal(Next)*step; step := step/10;
Move;
end else begin
state := Error; {должна быть хоть одна цифра}
end;
end else if state = FracPart then begin
if Digit (Next) then begin
state := FracPart;
val := val + DigitVal(Next)*step; step := step/10;
Move;
end else begin
state := Accept;
end;
end else if
{такого быть не может}
end;
end;

5.2. Ввод чисел
95
5.2.3. Та же задача, если перед числом может стоять знак - или
знак + (а может ничего не стоять).
Формат чисел в этой задаче обычно иллюстрируют такой картин-
кой:
+
-
⟨
цифра
⟩
.
⟨
цифра
⟩
-
-
-
5.2.4. Та же задача, если к тому же после числа может стоять
показатель степени десяти, как в 254E-4 (= 0.0254) или в 0.123E+9
(= 123 000 000). Нарисуйте соответствующую картинку.
5.2.5. Что надо изменить в приведённой выше программе, чтобы
разрешить пустые целую и дробную части (как в «1.», «.1» или да-
же «.» | последнее число считаем равным нулю)?
Мы вернёмся к конечным автоматам в главе
10
(Сравнение с образ-
цом).

6. ТИПЫ ДАННЫХ
6.1. Стеки
Пусть T | некоторый тип. Рассмотрим (отсутствующий в паскале)
тип «стек элементов типа T». Его значениями являются последователь-
ности значений типа T.
Операции:
•
Сделать пустым (var s: стек элементов типа T)
•
Добавить (t:T; var s: стек элементов типа T)
•
Взять (var t:T; var s: стек элементов типа T)
•
Пуст (s: стек элементов типа T): boolean
•
Вершина (s: стек элементов типа T): T
(Мы пользуемся обозначениями, напоминающими паскаль, хотя в
паскале типа «стек» нет.) Процедура «Сделать пустым» делает стек s
пустым. Процедура «Добавить» добавляет t в конец последовательно-
сти s. Процедура «Взять» применима, если последовательность s непу-
ста; она забирает из неё последний элемент, который становится зна-
чением переменной t. Выражение «Пуст(s)» истинно, если последова-
тельность s пуста. Выражение «Вершина(s)» определено, если последо-
вательность s непуста, и равно последнему элементу последовательно-
сти s.
Мы покажем, как моделировать стек в паскале и для чего он может
быть нужен.
Моделирование ограниченного стека в массиве
Будем считать, что количество элементов в стеке не превосходит
некоторого числа n. Тогда стек можно моделировать с помощью двух

6.1. Стеки
97
переменных:
Содержание: array [1..n] of T;
Длина: integer;
считая, что в стеке находятся элементы
Содержание [1],...,Содержание [Длина].
•
Чтобы сделать стек пустым, достаточно положить
Длина := 0
•
Добавить элемент t:
{Длина < n}
Длина := Длина+1;
Содержание [Длина] :=t;
•
Взять элемент в переменную t:
{Длина > 0}
t := Содержание [Длина];
Длина := Длина - 1;
•
Стек пуст, если Длина = 0.
•
Вершина стека равна Содержание [Длина].
Таким образом, вместо переменной типа стек в программе на па-
скале можно использовать две переменные Содержание и Длина. Можно
также определить тип stack, записав
const N = ...
type
stack = record
Содержание: array [1..N] of T;
Длина: integer;
end;
(Мы позволяем себе использовать имена переменных из русских букв,
хотя обычно паскаль этого не любит.) После этого могут быть | в со-
ответствии с правилами паскаля | описаны процедуры работы со сте-
ком. Например, можно написать
procedure Добавить (t: T; var s: stack);
begin
{s.Длина < N}
s.Длина := s.Длина + 1;
s.Содержание [s.Длина] := t;
end;

98
6. Типы данных
Использование стека
Будем рассматривать последовательности открывающихся и закры-
вающихся круглых и квадратных скобок ( ) [ ]. Среди всех таких
последовательностей выделим правильные | те, которые могут быть
получены по таким правилам:
•
пустая последовательность правильна.
•
если 𝐴 и 𝐵 правильны, то и 𝐴𝐵 правильна.
•
если 𝐴 правильна, то [𝐴] и (𝐴) правильны.
Пример. Последовательности (), [[ ]], [()[ ]()][ ] правильны, а
последовательности ], )(, (], ([)] | нет.
6.1.1. Проверьте правильность последовательности за время, не
превосходящее константы, умноженной на её длину. Предполагается,
что члены последовательности закодированы числами:
(
1
[
2
)
−
1
]
−
2
Решение. Пусть a[1]. . . a[n] | проверяемая последовательность.
Разрешим хранить в стеке открывающиеся круглые и квадратные скоб-
ки (т. е. 1 и 2).
Вначале стек делаем пустым. Далее просматриваем члены последо-
вательности слева направо. Встретив открывающуюся скобку (круглую
или квадратную), помещаем её в стек. Встретив закрывающуюся, про-
веряем, что вершина стека | парная ей скобка; если это не так, то
можно утверждать, что последовательность неправильна, если скобка
парная, то заберём её (вершину) из стека. Последовательность правиль-
на, если в конце стек оказывается пуст.
Сделать_пустым (s);
i := 0; Обнаружена_ошибка := false;
{прочитано i символов последовательности}
while (i < n) and not Обнаружена_ошибка do begin
i := i + 1;
if (a[i] = 1) or (a[i] = 2) then begin
Добавить (a[i], s);
end else begin {a[i] равно -1 или -2}

6.1. Стеки
99
if Пуст (s) then begin
Обнаружена_ошибка := true;
end else begin
Взять (t, s);
Обнаружена_ошибка := (t <> - a[i]);
end;
end;
end;
Правильно := (not Обнаружена_ошибка) and Пуст (s);
Убедимся в правильности программы.
(1) Если последовательность построена по правилам, то программа
даст ответ «да». Это легко доказать индукцией по построению пра-
вильной последовательности. Надо проверить для пустой, для после-
довательности 𝐴𝐵 в предположении, что для 𝐴 и 𝐵 уже проверено,
и, наконец, для последовательностей [𝐴] и (𝐴) | в предположении,
что для 𝐴 уже проверено. Для пустой очевидно. Для 𝐴𝐵 действия про-
граммы происходят как для 𝐴 и кончаются с пустым стеком; затем всё
происходит как для 𝐵. Для [𝐴] сначала помещается в стек открываю-
щая квадратная скобка и затем всё идёт как для 𝐴 | с той разницей,
что в глубине стека лежит лишняя скобка. По окончании 𝐴 стек ста-
новится пустым | если не считать этой скобки | а затем и совсем
пустым. Аналогично для (𝐴).
(2) Покажем, что если программа завершает работу с ответом «да»,
то последовательность правильна. Рассуждаем индукцией по длине по-
следовательности. Проследим за состоянием стека в процессе работы
программы. Если он в некоторый промежуточный момент пуст, то по-
следовательность разбивается на две части, для каждой из которых
программа даёт ответ «да»; остаётся воспользоваться предположением
индукции и определением правильности. Пусть стек всё время непуст.
Это значит, что положенная в него на первом шаге скобка будет выну-
та лишь на последнем шаге. Тем самым, первый и последний символы
последовательности | это парные скобки, и последовательность имеет
вид (𝐴) или [𝐴], а работа программы (кроме первого и последнего
шагов) отличается от её работы на 𝐴 лишь наличием лишней скобки
на дне стека (раз её не вынимают, она никак не влияет на работу про-
граммы). Снова ссылаемся на предположение индукции и определение
правильности.
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
writeln (t);

106
6. Типы данных
Добавить (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. Как, используя память размера 𝑂(𝑛) [пропорциональную 𝑛],
хранить подмножества множества
{
1 . . . 𝑛
}
?
Операции
Число действий
Сделать пустым
𝐶𝑛
Проверить принадлежность
𝐶
Добавить
𝐶
Удалить
𝐶
Минимальный элемент
𝐶𝑛
Проверка пустоты
𝐶𝑛
Решение. Храним множество как array [1..n] of Boolean.

112
6. Типы данных
6.3.2. То же, но проверка пустоты должна выполняться за время 𝐶.
Решение. Храним дополнительно количество элементов.
6.3.3. То же при следующих ограничениях на число действий:
Операции
Число действий
Сделать пустым
𝐶𝑛
Проверить принадлежность
𝐶
Добавить
𝐶
Удалить
𝐶𝑛
Минимальный элемент
𝐶
Проверка пустоты
𝐶
Решение. Дополнительно храним минимальный элемент множе-
ства.
6.3.4. То же при следующих ограничениях на число действий:
Операции
Число действий
Сделать пустым
𝐶𝑛
Проверить принадлежность
𝐶
Добавить
𝐶𝑛
Удалить
𝐶
Минимальный элемент
𝐶
Проверка пустоты
𝐶
Решение. Храним минимальный, а для каждого | следующий и пре-
дыдущий по величине.
Множества целых чисел
В следующих задачах величина элементов множества не ограничена,
но их количество не превосходит 𝑛.
6.3.5. Память 𝐶𝑛.
Операции
Число действий
Сделать пустым
𝐶
Число элементов
𝐶
Проверить принадлежность
𝐶𝑛
Добавить новый (заведомо отсутствующий)
𝐶
Удалить
𝐶𝑛
Минимальный элемент
𝐶𝑛
Взять какой-то элемент
𝐶

6.3. Множества
113
Решение. Множество представляем с помощью переменных
a:array [1..n] of integer, k: 0..n;
множество содержит k элементов a[1], . . . a[k]; все они различны. По
существу мы храним элементы множества в стеке (без повторений).
С тем же успехом можно было бы воспользоваться очередью вместо
стека.
6.3.6. Память 𝐶𝑛.
Операции
Число действий
Сделать пустым
𝐶
Проверить пустоту
𝐶
Проверить принадлежность
𝐶 log 𝑛
Добавить
𝐶𝑛
Удалить
𝐶𝑛
Минимальный элемент
𝐶
Решение. См. решение предыдущей задачи с дополнительным усло-
вием a[1] < . . . < a[k]. При проверке принадлежности используем дво-
ичный поиск.
В следующей задаче полезно комбинировать разные способы.
6.3.7. Используя описанные способы представления множеств, най-
дите все вершины ориентированного графа, доступные из данной по
рёбрам. (Вершины считаем числами 1 . . . n.) Время не больше 𝐶
·
(общее
число рёбер, выходящих из доступных вершин).
Решение. (Другое решение см. в главе о рекурсии, задача
7.4.6
)
Пусть num[i] | число рёбер, выходящих из i, а out[i][1], . . .
. . . , out[i][num[i]] | вершины, куда ведут рёбра из вершины i.
procedure Доступные (i: integer);
{напечатать все вершины, доступные из i, включая i}
var X: подмножество 1..n;
P: подмножество 1..n;
q, v, w: 1..n;
k: integer;
begin
...сделать X, P пустыми;
writeln (i);
...добавить i к X, P;
{(1) P = множество напечатанных вершин; P содержит i;

114
6. Типы данных
(2) напечатаны только доступные из i вершины;
(3) X - подмножество P;
(4) все напечатанные вершины, из которых выходит
ребро в ненапечатанную вершину, принадлежат X}
while X непусто do begin
...взять какой-нибудь элемент X в v;
for k := 1 to num [v] do begin
w := out [v][k];
if w не принадлежит P then begin
writeln (w);
добавить w в P;
добавить w в X;
end;
end;
end;
end;
Свойство (1) не нарушается, так как печать происходит одновре-
менно с добавлением в P. Свойство (2): раз v было в X, то v доступно,
поэтому w доступно. Свойство (3) очевидно. Свойство (4): мы удали-
ли из X элемент v, но все вершины, куда из v идут рёбра, перед этим
напечатаны.
6.3.8. Покажите, что можно использовать и другой инвариант: P |
напечатанные вершины; X
⊂
P; осталось напечатать вершины, доступ-
ные из X по ненапечатанным вершинам.
Оценка времени работы. Заметим, что изъятые из X элементы боль-
ше туда не добавляются, так как они в момент изъятия (и, следователь-
но, всегда позже) принадлежат P, а добавляются только элементы не
из P. Поэтому тело цикла while для каждой доступной вершины вы-
полняется не более, чем по разу, при этом тело цикла for выполняется
столько раз, сколько из вершины выходит рёбер.
Для X надо использовать представление со стеком или очередью
(см. выше), для P | булевский массив.
6.3.9. Решите предыдущую задачу, если требуется, чтобы доступ-
ные вершины печатались в таком порядке: сначала заданная вершина,
потом её соседи, потом соседи соседей (ещё не напечатанные) и т. д.
[Указание. Так получится, если использовать очередь для хранения X
в приведённом выше решении: докажите индукцией по 𝑘, что существу-
ет момент, в который напечатаны все вершины на расстоянии не боль-
ше 𝑘, а в очереди находятся все вершины, удалённые ровно на 𝑘.]

6.4. Разные задачи
115
Более сложные способы представления множеств будут разобраны
в главах
13
(хеширование) и
14
(деревья).
6.4. Разные задачи
6.4.1. Реализуйте структуру данных, которая имеет все те же опе-
рации, что массив длины n, а именно
•
начать работу;
•
положить в i-ю ячейку число x;
•
узнать, что лежит в i-й ячейке;
а также операцию
•
указать номер минимального элемента
(точнее, одного из минимальных элементов). Количество действий для
всех операций должно быть не более 𝐶 log n, не считая операции «начать
работу» (которая требует не более 𝐶n действий).
Решение. Используется приём, изложенный в разделе о сортировке
деревом. Именно, надстроим над элементами массива как над листьями
двоичное дерево, в каждой вершине которого храним минимум элемен-
тов соответствующего поддерева. Корректировка этой информации,
а также прослеживание пути из корня к минимальному элементу тре-
буют логарифмического числа действий.
6.4.2. Приоритетная очередь | это очередь, в которой важно не то,
кто встал последним (порядок помещения в неё не играет роли), а кто
главнее. Более точно, при помещении в очередь указывается приоритет
помещаемого объекта (будем считать приоритеты целыми числами),
а при взятии из очереди выбирается элемент с наибольшим приорите-
том (или один из таких элементов). Реализуйте приоритетную очередь
так, чтобы помещение и взятие элемента требовали логарифмического
числа действий (от размера очереди).
Решение. Следуя алгоритму сортировки деревом (в его окончатель-
ном варианте), будем размещать элементы очереди в массиве x[1..k],
поддерживая такое свойство: x[i] старше (имеет больший приоритет)
своих сыновей x[2i] и x[2i+1], если таковые существуют | и, сле-
довательно, всякий элемент старше своих потомков. (Сведения о при-
оритетах также хранятся в массиве, так что мы имеем дело с масси-
вом пар
⟨
элемент, приоритет
⟩
.) Удаление элемента с сохранением этого

116
6. Типы данных
свойства описано в алгоритме сортировки. Надо ещё уметь восстана-
вливать свойство после добавления элемента в конец. Это делается так:
t:= номер добавленного элемента
{инвариант: в дереве любой предок приоритетнее потомка,
если этот потомок - не t}
while t - не корень и t старше своего отца do begin
поменять t с его отцом
end;
Если очередь образуют граждане, стоящие в вершинах дерева,
т. е. за каждым стоит двое, а перед каждым (кроме первого) | один, то
смысл этого алгоритма ясен: встав в конец, приоритетный гражданин
начинает пробираться к началу, вытесняя впереди стоящих | пока не
встретит более приоритетного.
Замечание. Приоритетную очередь естественно использовать при
моделировании протекающих во времени процессов. При этом элемен-
ты очереди | это ожидаемые события, а их приоритет определяется
временем, когда они произойдут.

7. РЕКУРСИЯ
7.1. Примеры рекурсивных программ
При анализе рекурсивной программы возникает, как обычно, два
вопроса:
(а) почему программа заканчивает работу?
(б) почему она работает правильно, если заканчивает работу?
Для (б) достаточно проверить, что (содержащая рекурсивный вы-
зов) программа работает правильно, предположив, что вызываемая ею
одноимённая программа работает правильно. В самом деле, в этом слу-
чае в цепочке рекурсивно вызываемых программ все программы рабо-
тают правильно (убеждаемся в этом, идя от конца цепочки к началу).
Чтобы доказать (а), обычно проверяют, что с каждым рекурсивным
вызовом значение какого-то параметра уменьшается, и это не может
продолжаться бесконечно.
7.1.1. Напишите рекурсивную процедуру вычисления факториала
целого положительного числа 𝑛 (т. е. произведения 1
·
2
· · ·
𝑛, обознача-
емого 𝑛!).
Решение. Используем равенства 1! = 1, 𝑛! = (𝑛
−
1)!
·
𝑛.
procedure factorial (n: integer; var fact: integer);
{положить fact равным факториалу числа n}
begin
if n=1 then begin
fact:=1;
end else begin {n>1}
factorial (n-1, fact);
{fact = (n-1)!}
fact:= fact*n;
end;
end;

118
7. Рекурсия
С использованием процедур-функций можно написать так:
function factorial (n: integer): integer;
begin
if n=1 then begin
factorial:=1;
end else begin {n>1}
factorial:= factorial (n-1)*n;
end;
end;
Обратите внимание на некоторую двойственность использования име-
ни factorial внутри описания функции: оно обозначает как перемен-
ную, так и вызываемую рекурсивно функцию. К счастью, в нашем слу-
чае они различаются по скобкам после имени, но если бы функция была
без параметров, то дело было бы плохо. (Стандартная, но трудно нахо-
димая ошибка возникает, если автор программы на паскале полагает,
что он использует значение переменной, а компилятор в этом месте
видит рекурсивный вызов.)
7.1.2. Обычно факториал определяют и для нуля, считая, что 0! = 1.
Измените программы соответственно.
7.1.3. Напишите рекурсивную программу возведения в целую нео-
трицательную степень.
7.1.4. То же, если требуется, чтобы глубина рекурсии не превосхо-
дила 𝐶 log 𝑛, где 𝑛 | показатель степени.
Решение.
function power (a,n: integer): integer;
begin
if n = 0 then begin
power:= 1;
end else if n mod 2 = 0 then begin
power:= power(a*a, n div 2);
end else begin
power:= power(a, n-1)*a;
end;
end;

7.1. Примеры рекурсивных программ
119
7.1.5. Что будет, если изменить программу, приведённую в решении
предыдущей задачи, заменив строку
power:= power(a*a, n div 2)
на
power:= power(a, n div 2)* power(a, n div 2)?
Решение. Программа останется правильной. Однако она станет ра-
ботать медленнее. Дело в том, что теперь вызов может породить два
вызова (хотя и одинаковых) вместо одного | и число вызовов быстро
растёт с глубиной рекурсии. Программа по-прежнему имеет логариф-
мическую глубину рекурсии, но число шагов работы становится линей-
ным вместо логарифмического.
Этот недостаток можно устранить, написав
t:= power(a, n div 2);
power:= t*t;
или воспользовавшись функцией возведения в квадрат (sqr).
7.1.6. Используя команды write(x) лишь при x = 0 . . . 9, напишите
рекурсивную программу печати десятичной записи целого положитель-
ного числа 𝑛.
Решение. Здесь использование рекурсии облегчает жизнь (пробле-
ма была в том, что цифры легче получать с конца, а печатать надо
с начала).
procedure print (n:integer); {n>0}
begin
if n<10 then begin
write (n);
end else begin
print (n div 10);
write (n mod 10);
end;
end;
7.1.7. Игра «Ханойские башни» состоит в следующем. Есть три
стержня. На первый из них надета пирамидка из 𝑁 колец (большие
кольца снизу, меньшие сверху). Требуется переместить кольца на дру-
гой стержень. Разрешается перекладывать кольца со стержня на стер-
жень, но класть большее кольцо поверх меньшего нельзя. Составьте
программу, указывающую требуемые действия.

120
7. Рекурсия
Решение. Напишем рекурсивную процедуру перемещения i верхних
колец с m-го стержня на n-й (остальные кольца предполагаются боль-
шими по размеру и лежат на стержнях без движения).
procedure move(i,m,n: integer);
var s: integer;
begin
if i = 1 then begin
writeln (’сделать ход ’, m, ’->’, n);
end else begin
s:=6-m-n; {s - третий стержень: сумма номеров равна 6}
move (i-1, m, s);
writeln (’сделать ход ’, m, ’->’, n);
move (i-1, s, n);
end;
end;
(Сначала переносится пирамидка из i-1 колец на третью палочку. По-
сле этого i-е кольцо освобождается, и его можно перенести куда следу-
ет. Остаётся положить на него пирамидку.)
7.1.8. Напишите рекурсивную программу суммирования массива
a: array [1..n] of integer.
[Указание. Рекурсивно определяемая функция должна иметь допол-
нительный параметр | число складываемых элементов.]
7.2. Рекурсивная обработка деревьев
Двоичным деревом называется картинка вроде такой:
k
k
k
k
k
k
A
A
A
A
A
A
Нижняя вершина называется корнем. Из каждой вершины могут ид-
ти две линии: влево вверх и вправо вверх. Вершины, куда они ведут,

7.2. Рекурсивная обработка деревьев
121
называются левым и правым сыновьями исходной вершины. Вершина
может иметь двух сыновей, а может иметь только одного сына (левого
или правого). Она может и вовсе не иметь сыновей, и в этом случае
называется листом.
Пусть 𝑥 | какая-то вершина двоичного дерева. Она сама вместе
с сыновьями, внуками, правнуками и т. д. образует поддерево с корнем
в 𝑥 | поддерево потомков 𝑥.
В следующих задачах мы предполагаем, что вершины дерева прону-
мерованы целыми положительными числами, причём номера всех вер-
шин различны. Мы считаем, что номер корня хранится в переменной
root. Мы считаем, что имеются два массива
l,r: array [1..N] of integer
и левый и правый сын вершины с номером i имеют соответственно
номера l[i] и r[i]. Если вершина с номером i не имеет левого (или
правого) сына, то l[i] (соответственно r[i]) равно 0. (По традиции
при записи программ мы используем вместо нуля константу nil, рав-
ную нулю.)
Здесь N | достаточно большое натуральное число (номера всех вер-
шин не превосходят N). Отметим, что номер вершины никак не связан
с её положением в дереве и что не все числа от 1 до N обязаны быть
номерами вершин (и, следовательно, часть данных в массивах l и r |
это мусор).
7.2.1. Пусть N = 7, root = 3, массивы l и r таковы:
i 1 2 3 4 5 6 7
l[i] 0 0 1 0 6 0 7
r[i] 0 0 5 3 2 0 7
Нарисуйте соответствующее дерево.
Ответ.
3
1
5
6
2
A
A
A
A
A
A

122
7. Рекурсия
7.2.2. Напишите программу подсчёта числа вершин в дереве.
Решение. Рассмотрим функцию n(x), равную числу вершин в подде-
реве с корнем в вершине номер x. Считаем, что n(nil) = 0 (полагая со-
ответствующее поддерево пустым), и не заботимся о значениях nil(s)
для чисел s, не являющихся номерами вершин. Рекурсивная программа
для n такова:
function n(x:integer):integer;
begin
if x = nil then begin
n:= 0;
end else begin
n:= n(l[x]) + n(r[x]) + 1;
end;
end;
(Число вершин в поддереве над вершиной x равно сумме чисел вер-
шин над её сыновьями плюс она сама.) Глубина рекурсии конечна, так
как с каждым шагом высота соответствующего поддерева уменьша-
ется.
7.2.3. Напишите программу подсчёта числа листьев в дереве.
Ответ.
function n (x:integer):integer;
begin
if x = nil then begin
n:= 0;
end else if (l[x]=nil) and (r[x]=nil) then begin {лист}
n:= 1;
end else begin
n:= n(l[x]) + n(r[x]);
end;
end;
7.2.4. Напишите программу подсчёта высоты дерева (корень имеет
высоту 0, его сыновья | высоту 1, внуки | 2 и т. п.; высота дерева |
это максимум высот его вершин).
[Указание. Рекурсивно определяется функция f(x) = высота под-
дерева с корнем в x.]
7.2.5. Напишите программу, которая по заданному n считает число
всех вершин высоты n (в заданном дереве).

7.3. Порождение комбинаторных объектов, перебор
123
Вместо подсчёта количества вершин того или иного рода можно
просить напечатать список этих вершин (в том или ином порядке).
7.2.6. Напишите программу, которая печатает (по одному разу) все
вершины дерева.
Решение. Процедура print subtree(x) печатает все вершины под-
дерева с корнем в x по одному разу; главная программа содержит вызов
print subtree(root).
procedure print_subtree (x:integer);
begin
if x = nil then begin
{ничего не делать}
end else begin
writeln (x);
print_subtree (l[x]);
print_subtree (r[x]);
end;
end;
Данная программа печатает сначала корень поддерева, затем подде-
рево над левым сыном, а затем над правым. Три строки в else-части
могут быть переставлены 6 способами, и каждый из этих способов даёт
свой порядок печати вершин.
7.3. Порождение комбинаторных объектов,
перебор
Рекурсивные программы являются удобным способом порождения
комбинаторных объектов заданного вида. Мы решим заново несколько
задач соответствующей главы.
7.3.1. Напишите программу, которая печатает по одному разу все
последовательности длины n, составленные из чисел 1 . . . k (их количе-
ство равно kn).
Решение. Программа будет оперировать с массивом a[1] . . . a[n]
и числом t. Рекурсивная процедура generate печатает все последо-
вательности, начинающиеся на a[1] . . . a[t]; после её окончания t и
a[1] . . . a[t] имеют то же значение, что и в начале:
procedure generate;
var i,j : integer;

124
7. Рекурсия
begin
if t = n then begin
for i:=1 to n do begin
write(a[i]);
end;
writeln;
end else begin {t < n}
for j:=1 to k do begin
t:=t+1;
a[t]:=j;
generate;
t:=t-1;
end;
end;
end;
Основная программа теперь состоит из двух операторов:
t:=0; generate;
Замечание. Команды t:=t+1 и t:=t-1 для экономии можно вынести
из цикла for.
7.3.2. Напишите программу, которая печатала бы все перестановки
чисел 1 . . . n по одному разу.
Решение. Программа оперирует с массивом a[1] . . . a[n], в котором
хранится перестановка чисел 1 . . . n. Рекурсивная процедура generate
в такой ситуации печатает все перестановки, которые на первых t по-
зициях совпадают с перестановкой a; по выходе из неё переменные t
и a имеют те же значения, что и до входа. Основная программа такова:
for i:=1 to n do begin a[i]:=i; end;
t:=0;
generate;
Вот описание процедуры:
procedure generate;
var i,j : integer;
begin
if t = n then begin
for i:=1 to n do begin
write(a[i]);
end;
writeln;

7.3. Порождение комбинаторных объектов, перебор
125
end else begin {t < n}
for j:=t+1 to n do begin
поменять местами a[t+1] и a[j]
t:=t+1;
generate;
t:=t-1;
поменять местами a[t+1] и a[j]
end;
end;
end;
7.3.3. Напечатайте все последовательности из n нулей и единиц, со-
держащие ровно k единиц (по одному разу каждую).
7.3.4. Напечатайте все возрастающие последовательности длины k,
элементами которых являются натуральные числа от 1 до n. (Предпо-
лагается, что k
6
n, иначе таких последовательностей не существует.)
Решение. Программа оперирует с массивом a[1] . . . a[k] и целой пе-
ременной t. Предполагая, что a[1] . . . a[t] | возрастающая последо-
вательность натуральных чисел из отрезка 1 . . . n, рекурсивно опреде-
лённая процедура generate печатает все её возрастающие продолжения
длины k. (При этом t и a[1] . . . a[t] в конце такие же, как в начале.)
procedure generate;
var i: integer;
begin
if t = k then begin
печатать a[1]..a[k]
end else begin
t:=t+1;
for i:=a[t-1]+1 to t-k+n do begin
a[t]:=i;
generate;
end;
t:=t-1;
end;
end;
Замечание. Цикл for мог бы иметь верхней границей n (вместо
t
−
k + n). Наш вариант экономит часть работы, учитывая тот факт,
что предпоследний ((k-1)-й) член не может превосходить n-1, (k-2)-й
член не может превосходить n-2 и т. п.

126
7. Рекурсия
Основная программа теперь выглядит так:
t:=1;
for j:=1 to 1-k+n do begin
a[1]:=j;
generate;
end;
Можно было бы добавить к массиву a слева фиктивный элемент a[0] =
= 0, положить t = 0 и ограничиться единственным вызовом процедуры
generate.
7.3.5. Перечислите все представления положительного целого чи-
сла n в виде суммы последовательности невозрастающих целых поло-
жительных слагаемых.
Решение. Программа оперирует с массивом a[1..n] (максимальное
число слагаемых равно n) и с целой переменной t. Предполагая, что
a[1] . . . a[t] | невозрастающая последовательность целых чисел, сум-
ма которых не превосходит n, процедура generate печатает все пред-
ставления требуемого вида, продолжающие эту последовательность.
Для экономии вычислений сумма a[1] + . . . + a[t] хранится в специ-
альной переменной s.
procedure generate;
var i: integer;
begin
if s = n then begin
печатать последовательность a[1]..a[t]
end else begin
for i:=1 to min(a[t], n-s) do begin
t:=t+1;
a[t]:=i;
s:=s+i;
generate;
s:=s-i;
t:=t-1;
end;
end;
end;
Основная программа при этом может быть такой:
t:=1;
for j:=1 to n do begin
a[1]:=j

7.4. Другие применения рекурсии
127
s:=j;
generate;
end;
Замечание. Можно немного сэкономить, вынеся операции увеличе-
ния и уменьшения t из цикла, а также не возвращая s каждый раз
к исходному значению (увеличивая его на 1 и возвращая к исходному
значению в конце). Кроме того, добавив фиктивный элемент a[0] = n,
можно упростить основную программу:
t:=0; s:=0; a[0]:=n; generate;
7.3.6. Напишите рекурсивную программу обхода дерева (используя
те же команды и проверки, что и в главе
3
(Обход дерева).
Решение. Процедура обработать над обрабатывает все листья над
текущей вершиной и заканчивает работу в той же вершине, что и на-
чала. Вот её рекурсивное описание:
procedure обработать_над;
begin
if есть_сверху then begin
вверх_налево;
обработать_над;
while есть_справа do begin
вправо;
обработать_над;
end;
вниз;
end else begin
обработать;
end;
end;
7.4. Другие применения рекурсии
Топологическая сортировка. Представим себе 𝑛 чиновников, каж-
дый из которых выдаёт справки определённого вида. Мы хотим полу-
чить все эти справки, соблюдая установленные ограничения: у каждого
чиновника есть список справок, которые нужно собрать перед обраще-
нием к нему. Дело безнадёжно, если схема зависимостей имеет цикл
(справку 𝐴 нельзя получить без 𝐵, 𝐵 без 𝐶,. . . , 𝑌 без 𝑍 и 𝑍 без 𝐴).

128
7. Рекурсия
Предполагая, что такого цикла нет, требуется составить план, указы-
вающий один из возможных порядков получения справок.
Изображая чиновников точками, а зависимости | стрелками, при-
ходим к такой формулировке. Имеется 𝑛 точек, пронумерованных от 1
до 𝑛. Из каждой точки ведёт несколько (возможно, 0) стрелок в другие
точки. (Такая картинка называется ориентированным графом.) Циклов
нет. Требуется расположить вершины графа (точки) в таком порядке,
чтобы конец любой стрелки предшествовал её началу. Эта задача на-
зывается топологической сортировкой.
7.4.1. Докажите, что это всегда возможно.
Решение. Из условия отсутствия циклов вытекает, что есть верши-
на, из которой вообще не выходит стрелок (иначе можно двигаться по
стрелкам, пока не зациклимся). Её будем считать первой. Выкидывая
эту вершину и все соседние стрелки, мы сводим задачу к графу с мень-
шим числом вершин и продолжаем рассуждение по индукции.
7.4.2. Предположим, что ориентированный граф без циклов хранит-
ся в такой форме: для каждого i от 1 до n в num[i] хранится число вы-
ходящих из i стрелок, в adr[i][1], . . . , adr[i][num[i]] | номера вер-
шин, куда эти стрелки ведут. Составьте (рекурсивный) алгоритм, кото-
рый производит топологическую сортировку не более чем за 𝐶
·
(n + m)
действий, где m | число рёбер графа (стрелок).
Замечание. Непосредственная реализация приведённого выше дока-
зательства существования не даёт требуемой оценки; её приходится
немного подправить.
Решение. Наша программа будет печатать номера вершин. В мас-
сиве
printed: array[1..n] of boolean
мы будем хранить сведения о том, какие вершины напечатаны (и кор-
ректировать их одновременно с печатью вершины). Будем говорить,
что напечатанная последовательность вершин корректна, если ника-
кая вершина не напечатана дважды и для любого номера i, входящего
в эту последовательность, все вершины, в которые ведут стрелки из i,
напечатаны, и притом до i.
procedure add (i: 1..n);
{дано: напечатанное корректно;}
{надо: напечатанное корректно и включает вершину i}

7.4. Другие применения рекурсии
129
begin
if printed [i] then begin {вершина i уже напечатана}
{ничего делать не надо}
end else begin
{напечатанное корректно}
for j:=1 to num[i] do begin
add(adr[i][j]);
end;
{напечатанное корректно, все вершины, в которые из
i ведут стрелки, уже напечатаны - так что можно
печатать i, не нарушая корректности}
if not printed[i] then begin
writeln(i); printed [i]:= TRUE;
end;
end;
end;
Основная программа:
for i:=1 to n do begin
printed[i]:= FALSE;
end;
for i:=1 to n do begin
add(i)
end;
К оценке времени работы мы вскоре вернёмся.
7.4.3. В приведённой программе можно выбросить проверку, заме-
нив
if not printed[i] then begin
writeln(i); printed [i]:= TRUE;
end;
на
writeln(i); printed [i]:= TRUE;
Почему? Как изменится спецификация процедуры?
Решение. Спецификацию можно выбрать такой:
дано: напечатанное корректно
надо: напечатанное корректно и включает вершину i;
все вновь напечатанные вершины доступны из i.

130
7. Рекурсия
7.4.4. Где использован тот факт, что граф не имеет циклов?
Решение. Мы опустили доказательство конечности глубины рекур-
сии. Для каждой вершины рассмотрим её «глубину» | максимальную
длину пути по стрелкам, из неё выходящего. Условие отсутствия циклов
гарантирует, что эта величина конечна. Из вершины нулевой глубины
стрелок не выходит. Глубина конца стрелки по крайней мере на 1 мень-
ше, чем глубина начала. При работе процедуры add(i) все рекурсивные
вызовы add(j) относятся к вершинам меньшей глубины.
Вернёмся к оценке времени работы. Сколько вызовов add(i) воз-
можно для какого-то фиксированного i? Прежде всего ясно, что пер-
вый из них печатает i, остальные сведутся к проверке того, что i уже
напечатано. Ясно также, что вызовы add(i) индуцируются «печата-
ющими» (первыми) вызовами add(j) для тех j, из которых в i ведёт
ребро. Следовательно, число вызовов add(i) равно числу входящих в i
рёбер (стрелок). При этом все вызовы, кроме первого, требуют 𝑂(1)
операций, а первый требует времени, пропорционального числу исходя-
щих из i стрелок. (Не считая времени, уходящего на выполнение add(j)
для концов j выходящих рёбер.) Отсюда видно, что общее время про-
порционально числу рёбер (плюс число вершин).
Связная компонента графа. Неориентированный граф | набор то-
чек (вершин), некоторые из которых соединены линиями (рёбрами).
Неориентированный граф можно считать частным случаем ориенти-
рованного графа, в котором для каждой стрелки есть обратная.
Связной компонентой вершины i называется множество всех тех
вершин, в которые можно попасть из i, идя по рёбрам графа. (По-
скольку граф неориентированный, отношение «j принадлежит связной
компоненте i» является отношением эквивалентности.)
7.4.5. Дан неориентированный граф (для каждой вершины указано
число соседей и массив номеров соседей, как в задаче о топологической
сортировке). Составьте алгоритм, который по заданному i печатает
все вершины связной компоненты i по одному разу (и только их). Чи-
сло действий не должно превосходить 𝐶
·
(общее число вершин и рёбер
в связной компоненте).
Решение. Программа в процессе работы будет «закрашивать» неко-
торые вершины графа. Незакрашенной частью графа будем называть
то, что останется, если выбросить все закрашенные вершины и веду-
щие в них рёбра. Процедура add(i) закрашивает связную компоненту i
в незакрашенной части графа (и не делает ничего, если вершина i уже
закрашена).

7.4. Другие применения рекурсии
131
procedure add (i:1..n);
begin
if вершина i закрашена then begin
ничего делать не надо
end else begin
закрасить i (напечатать и пометить как закрашенную)
для всех j, соседних с i
add(j);
end;
end;
end;
Докажем, что эта процедура действует правильно (в предположении,
что рекурсивные вызовы работают правильно). В самом деле, ниче-
го, кроме связной компоненты незакрашенного графа, она закрасить
не может. Проверим, что вся она будет закрашена. Пусть k | вер-
шина, доступная из вершины i по пути i
→
j
→
. . .
→
k, проходящему
только по незакрашенным вершинам. Будем рассматривать только пу-
ти, не возвращающиеся снова в i. Из всех таких путей выберем путь
с наименьшим j (в порядке просмотра соседей в процедуре). Тогда при
рассмотрении предыдущих соседей ни одна из вершин пути j
→
. . .
→
k
не будет закрашена (иначе j не было бы минимальным) и потому k ока-
жется в связной компоненте незакрашенного графа к моменту вызова
add(j). Что и требовалось.
Чтобы установить конечность глубины рекурсии, заметим, что на
каждом уровне рекурсии число незакрашенных вершин уменьшается
хотя бы на 1.
Оценим число действий. Каждая вершина закрашивается не более
одного раза | при первым вызове add(i) с данным i. Все последую-
щие вызовы происходят при закрашивании соседей | количество та-
ких вызовов не больше числа соседей | и сводятся к проверке того,
что вершина i уже закрашена. Первый же вызов состоит в просмо-
тре всех соседей и рекурсивных вызовах add(j) для всех них. Таким
образом, общее число действий, связанных с вершиной i, не превосхо-
дит константы, умноженной на число её соседей. Отсюда и вытекает
требуемая оценка.
7.4.6. Решите ту же задачу для ориентированного графа (напе-
чатать все вершины, доступные из данной по стрелкам; граф может
содержать циклы).
Ответ. Годится по существу та же программа (строку «для всех
соседей» надо заменить на «для всех вершин, куда ведут стрелки»).

132
7. Рекурсия
Следующий вариант задачи о связной компоненте имеет скорее те-
оретическое значение (и называется теоремой Сэвича).
7.4.7. Ориентированный граф имеет 2
𝑛
вершин (двоичные слова
длины 𝑛) и задан в виде функции есть ребро, которая по двум верши-
нам 𝑥 и 𝑦 сообщает, есть ли в графе ребро из 𝑥 в 𝑦. Составьте алгоритм,
который для данной пары вершин 𝑢 и 𝑣 определяет, есть ли путь (по
рёбрам) из 𝑢 в 𝑣, используя память, ограниченную многочленом от 𝑛.
(Время при этом может быть | и будет | очень большим.)
[Указание. Используйте рекурсивную процедуру, выясняющую, су-
ществует ли путь из 𝑥 в 𝑦 длины не более 2
𝑘
(и вызывающую себя
с уменьшенным на единицу значением 𝑘).]
Быстрая сортировка Хоара. В заключение приведём рекурсивный
алгоритм сортировки массива, который на практике является одним
из самых быстрых. Пусть дан массив a[1] . . . a[n]. Рекурсивная про-
цедура sort(l,r:integer) сортирует участок массива с индексами из
полуинтервала (l, r], то есть a[l+1] . . . a[r], не затрагивая остального
массива.
procedure sort (l,r: integer);
begin
if l = r then begin
ничего делать не надо - участок пуст
end else begin
выбрать случайное число s в полуинтервале (l,r]
b := a[s]
переставить элементы сортируемого участка так, чтобы
сначала шли элементы, меньшие b - участок (l,ll]
затем элементы, равные b
- участок (ll,rr]
затем элементы, большие b
- участок (rr,r]
sort (l,ll);
sort (rr,r);
end;
end;

жүктеу/скачать 1,66 Mb.

Достарыңызбен бөлісу: