связной компоненте).
Решение. Программа в процессе работы будет "закрашивать"
некоторые вершины графа. Незакрашенной частью графа будем назы-
вать то, что останется, если выбросить все закрашенные вершины и
ведущие в них ребра. Процедура 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).
При достаточно большом C' член Cn в правой части перевешивается
за счет интеграла x*x*d(ln x), и индуктивный шаг проходит.
7.4.8. Имеется массив из n различных целых чисел a[1]..a[n]
и число k. Требуется найти k-ое по величине число в этом масси-
ве, сделав не более C*n действий, где C - некоторая константа,
не зависящая от k.
Замечание. Сортировка позволяет очевидным образом сделать
это за C*n*log(n) действий. Очевидный способ: найти наименьший
элемент, затем найти второй, затем третий,..., k-ый требует по-
рядка k*n действий, то есть не годится (константа при n зависит
от k).
Указание. Изящный (хотя практически и бесполезный -
константы слишком велики) способ сделать это таков:
А. Разобьем наш массив на n/5 групп, в каждой из которых по
5 элементов. Каждую группу упорядочим.
Б. Рассмотрим средние элементы всех групп и перепишем их в
массив из n/5 элементов. С помощью рекурсивного вызова найдем
средний по величине элемент этого массива.
В. Сравним этот элемент со всеми элементами исходного мас-
сива: они разделятся на большие его и меньшие его (и один равный
ему). Подсчитав количество тех и других, мы узнаем, в какой из
этих частей должен находится искомый (k-ый) элемент и каков он
там по порядку.
Г. Применим рекурсивно наш алгоритм к выбранной части.
Пусть T(n) - максимально возможное число действий, если
этот способ применять к массивам из не более чем n элементов (k
может быть каким угодно). Имеем оценку:
T(n) <= Cn + T(n/5) + T(примерно 0.7n)
Последнее слагаемое объясняется так: при разбиении на части каж-
дая часть содержит не менее 0.3n элементов. В самом деле, если x
- средний из средних, то примерно половина всех средних меньше
x. А если в пятерке средний элемент меньше x, то еще два заведо-
мо меньше x. Тем самым по крайней мере 3/5 от половины элементов
меньше x.
Теперь по индукции можно доказать оценку T(n) <= Cn (реша-
ющую роль при этом играет то обстоятельство, что 1/5 + 0.7 < 1).
Глава 8. Как обойтись без рекурсии.
Для универсальных языков программирования (каковым является
паскаль) рекурсия не дает ничего нового: для всякой рекурсивной
программы можно написать эквивалентную программу без рекурсии.
Мы не будем доказывать этого, а продемонстрируем некоторые при-
емы, позволяющие избавиться от рекурсии в конкретных ситуациях.
Зачем это нужно? Ответ прагматика мог бы быть таким: во
многих компьютерах (в том числе, к сожалению, и в современных,
использующих так называемые RISC-процессоры), рекурсивные прог-
раммы в несколько раз медленнее соответствующих нерекурсивных
программ. Еще один возможный ответ: в некоторых языках програм-
мирования рекурсивные программы запрещены. А главное, при удале-
нии рекурсии возникают изящные и поучительные конструкции.
8.1. Таблица значений (динамическое программирование)
8.1.1. Следующая рекурсивная процедура вычисляет числа со-
четаний (биномиальные коэффициенты). Написать эквивалентную не-
рекурсивную программу.
function C(n,k: integer):integer;
| {n,k >=0; k <=n}
begin
| if (k = 0) or (k = n) then begin
| | C:=1;
| end else begin {0 2.
8.1.3. Дан выпуклый n-угольник (заданный координатами своих
вершин в порядке обхода). Его разрезают на треугольники диагона-
лями, для чего необходимо n-2 диагонали (докажите индукцией по
n). Стоимостью разрезания назовем сумму длин всех использованных
диагоналей. Найти минимальную стоимость разрезания. Число
действий должно быть ограничено некоторым многочленом от n. (Пе-
ребор не подходит, так как число вариантов не ограничено многоч-
леном.)
Решение. Будем считать, что вершины пронумерованы от 1 до n
и идут по часовой стрелке. Пусть k, l - номера вершин, причем
l>k. Через A(k,l) обозначим многоугольник, отрезаемый от нашего
хордой k--l. (Эта хорда разрезает многоугольник на 2, один из
которых включает сторону 1--n; через A(k,l) мы обозначаем дру-
гой.) Исходный многоугольник естественно обозначить A(1,n). При
l=k+1 получается "двуугольник" с совпадающими сторонами.
Через a(k,l) обозначим стоимость разрезания многоугольника
A(k,l) диагоналями на треугольники. Напишем рекуррентную формулу
для a(k,l). При l=k+1 получается двуугольник, и мы полагаем
a(k,l)=0. При l=k+2 получается треугольник, и в этом случае так-
же a(k,l)=0. Пусть l > k+2. Хорда k--l является стороной много-
