| end;
end;
7.2.4. Написать программу подсчета высоты дерева (корень
имеет высоту 0, его сыновья - высоту 1, внуки - 2 и т.п.; высота
дерева - это максимум высот его вершин).
Указание. Рекурсивно определяется функция f(x) = высота
поддерева с корнем в x.
7.2.5. Написать программу, которая по заданному n считает
число всех вершин высоты n (в заданном дереве).
Вместо подсчета количества вершин того или иного рода можно
просить напечатать список этих вершин (в том или ином порядке).
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 (их
количество равно k в степени n).
Решение. Программа будет оперировать с массивом a[1]..a[n]
и числом t. Рекурсивная процедура generate печатает все последо-
вательности, начинающиеся на a[1]..a[t]; после ее окончания t
имеет то же значение, что и в начале:
procedure generate;
| var i,j : integer;
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;
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;
| 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. Напечатать все возрастающие последовательности длины
k, элементами которых являются натуральные числа от 1 до n.
(Предполагается, что k не превосходит n - иначе таких последова-
тельностей не существует.)
Решение. Программа оперирует с массивом a[1]..a[k] и целой
переменной t. Предполагая, что a[1]..a[t] - возрастающая после-
довательность чисел натуральных чисел из отрезка 1..n, рекурсив-
но определенная процедура generate печатает все ее возрастающие
продолжения длины k.
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 и т.п.
Основная программа теперь выглядит так:
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.4. Перечислить все представления положительного целого
числа 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
| s:=j;
| generate;
end;
Замечание. Можно немного сэконмить, вынеся операции увели-
чения и уменьшения t из цикла, а также не возвращая s каждый раз
к исходному значению (а увеличивая его на 1 и возвращая к исход-
ному значению в конце). Кроме того, добавив фиктивный элемент
a[0]=n, можно упростить основную программу:
t:=0; s:=0; a[0]:=n; generate;
7.3.5. Написать рекурсивную программу обхода дерева (ис-
пользуя те же команды и проверки, что и в главе про обход дере-
ва).
Решение. Процедура обработать_над обрабатывает все листья
над текущей вершиной и заканчивает работу в той же вершине, что
и начала. Вот ее рекурсивное описание:
procedure обработать_над;
begin
| if есть_сверху then begin
| | вверх_налево;
| | обработать_над;
| | while есть_справа do begin
| | | вправо;
| | | обработать_над;
| | end;
| | вниз;
| end else begin
| | обработать;
| end;
end;
7.4. Другие применения рекурсии
Топологическая сортировка. Представим себе n чиновников,
каждый из которых выдает справки определенного вида. Мы хотим
получить все эти справки, соблюдая ограничения, установленные
чиновниками. Ограничения состоят в том, что у каждого чиновника
есть список справок, которые нужно собрать перед обращением к
нему. Дело безнадежно, если схема зависимостей имеет цикл
(справку A нельзя получить без B, B без C,..., Y без Z и Z без
A). Предполагая, что такого цикла нет, требуется составить план,
указывающий один из возможных порядков получения справок.
Изображая чиновников точками, а зависимости - стрелками,
приходим к такой формулировке. Имеется n точек, пронумерованных
от 1 до n. Из каждой точки ведет несколько (возможно, 0) стрелок
в другие точки. (Такая картинка называется ориентированным гра-
фом.) Циклов нет. Требуется расположить вершины графа (точки) в
таком порядке, чтобы конец любой стрелки предшествовал ее нача-
лу. Эта задача называется топологической сортировкой.
7.4.1. Доказать, что это всегда возможно.
Решение. Из условия отсутствия циклов вытекает, что есть
вершина, из которой вообще не выходит стрелок (иначе можно дви-
гаться по стрелкам, пока не зациклимся). Ее будем считать пер-
вой. Выкидывая все стрелки, в нее ведущие, мы сводим задачу к
графу с меньшим числом вершин и продолжаем рассуждение по индук-
ции.
7.4.2. Предположим, что ориентированный граф без циклов
хранится в такой форме: для каждого i от 1 до n в num[i] хранит-
ся число выходящих из i стрелок, в adr[i][1],..., adr[i][num[i]]
- номера вершин, куда эти стрелки ведут. Составить (рекурсивный)
алгоритм, который производит топологическую сортировку не более
чем за C*(n+m) действий, где m - число ребер графа (стрелок).
Замечание. Непосредственная реализация приведенного выше
доказательства существования не дает требуемой оценки; ее прихо-
дится немного подправить.
Решение. Наша программа будет печатать номера вершин. В
массиве printed: array[1..n] of boolean мы будем хранить сведе-
ния о том, какие вершины напечатаны (и корректировать их однов-
ременно с печатью вершины). Будем говорить, что напечатанная
последовательность вершин корректна, если никакая вершина не на-
печатана дважды и для любого номера i, входящего в эту последос-
тельность, все вершины, в которые ведут стрелки из i, напечата-
ны, и притом до i.
procedure add (i: 1..n);
| {дано: напечатанное корректно;}
| {надо: напечатанное корректно и включает вершину i}
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.
7.4.4. Где использован тот факт, что граф не имеет циклов?
Решение. Мы опустили доказательство конечности глубины ре-
курсии. Для каждой вершины рассмотрим ее "глубину" - макси-
мальную длину пути по стрелкам, из нее выходящего. Условие от-
сутствия циклов гарантирует, что эта величина конечна. Из верши-
ны нулевой глубины стрелок не выходит. Глубина конца стрелки по
крайней мере на 1 меньше, чем глубина начала. При работе проце-
дуры add(i) все рекурсивные вызовы add(j) относятся к вершинам
меньшей глубины.
Связная компонента графа. Неориентированный граф - набор
точек (вершин), некоторые из которых соединены линиями (ребра-
ми). Неориентированный граф можно считать частным случаем ориен-
тированного графа, в котором для каждой стрелки есть обратная.
Связной компонентой вершины i называется множество всех тех
вершин, в которые можно попасть из i, идя по ребрам графа. (Пос-
кольку граф неориентированный, отношение "j принадлежит связной
компоненте i" является отношением эквивалентности.)
7.4.5. Дан неориентированный граф (для каждой вершины ука-
зано число соседей и массив номеров соседей, как в предыдущей
задаче). Составить алгоритм, который по заданному i печатает все
вершины связной компоненты i по одному разу (и только их). Число
действий не должно превосходить C*(общее число вершин и ребер в
