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*(общее число вершин и ребер в
связной компоненте).
Решение. Программа в процессе работы будет "закрашивать"
некоторые вершины графа. Незакрашенной частью графа будем назы-
вать то, что останется, если выбросить все закрашенные вершины и
ведущие в них ребра. Процедура add(i) закрашивает связную компо-
ненту i в незакрашенном графе (и не делает ничего, если вершина
i уже закрашена).
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. Решить ту же задачу для ориентированного графа (на-
печатать все вершины, доступные из данной по стрелкам; граф мо-
жет содержать циклы).
Ответ. Годится по существу та же программа (строку "для
