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. Решить ту же задачу для ориентированного графа (на-
печатать все вершины, доступные из данной по стрелкам; граф мо-
жет содержать циклы).
Ответ. Годится по существу та же программа (строку "для
всех соседей" надо заменить на "для всех вершин, куда ведут
стрелки").
Быстрая сортировка Хоара. В заключение приведем рекурсивный
алгоритм сортировки массива, который на практике является одним
из самых быстрых. Пусть дан массив 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.
7.4.7. (Для знакомых с основами теории вероятностей). Дока-
зать, что математическое ожидание числа операций при работе это-
го алгоритма не превосходит C*n*log n, причем константа C не за-
висит от сортируемого массива.
Указание. Пусть T(n) - максимум математического ожидания
числа операций для всех входов длины n. Из текста процедуры вы-
текает такое неравенство:
T(n) <= Cn + 1/n [сумма по всем k+l=(n-1) чисел T(k)+T(l)]
Первый член соответствует распределению элементов на меньшие,
равные и большие. Второй член - это среднее математическое ожи-
дание для всех вариантов случайного выбора. (Строго говоря, пос-
кольку среди элементов могут быть равные, в правой части вместо
T(k) и T(l) должны стоять максимумы T(x) по всем x, не превосхо-
дящим k или l, но это не мешает дальнейшим рассуждениям.) Далее
индукцией по n нужно доказывать оценку T(n) <= C'nlog n. При
этом для вычисления среднего значения x log x по всем
x=1,..,n-1 нужно интегрировать x lnx по частям как lnx * d(x*x).
