всех соседей" надо заменить на "для всех вершин, куда ведут
стрелки").
Быстрая сортировка Хоара. В заключение приведем рекурсивный
алгоритм сортировки массива, который на практике является одним
из самых быстрых. Пусть дан массив 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 является стороной много-
угольника A(k,l) и, следовательно, стороной одного из тре-
угольников, на которые он разрезан. Противоположной вершиной i
этого треугольника может быть любая из вершин k+1,...,l-1, и ми-
нимальная стоимость разрезания может быть вычислена как
min {(длина хорды k--i)+(длина хорды i--l)+a(k,i)+a(i,l)}
по всем i=k+1,..., i=l-1. При этом надо учесть, что при i=k+1
хорда k--i - не хорда, а сторона, и ее длину надо считать равной
0 (по стороне разрез не проводится).
Составив таблицу для a(k,l) и заполняя ее в порядке возрас-
тания числа вершин (равного l-k+2), мы получаем программу, ис-
пользующую память порядка n*n и время порядка n*n*n (однократное
применение рекуррентной формулы требует выбора минимума из не
более чем n чисел).
8.1.4. Матрицей размера m*n называется прямоугольная табли-
ца из m строк и n столбцов, заполненная числами. Матрицу размера
m*n можно умножить на матрицу размера n*k (ширина левого сомно-
жителя должна равняться высоте правого), и получается матрица
размером m*k. Ценой такого умножения будем считать произведение
m*n*k (таково число умножений, которые нужно выполнить при стан-
дартном способе умножения - но сейчас это нам не важно). Умноже-
ние матриц ассоциативно, поэтому произведение n матриц можно вы-
числять в разном порядке. Для каждого порядка подсчитаем суммар-
ную цену всех матричных умножений. Найти минимальную цену вычис-
ления произведения, если известны размеры всех матриц. Число
действий должно быть ограничено многочленом от числа матриц.
Пример. Матрицы размером 2*3, 3*4, 4*5 можно перемножать
двумя способами. В первом цена равна 2*3*4 + 2*4*5 = 24 + 40 =
64, во втором цена равна 3*4*5 + 2*3*5 = 90.
Решение. Представим себе, что первая матрица написана на
отрезке [0,1], вторая - на отрезке [1,2],..., s-ая - на отрезке
[s-1,s]. Матрицы на отрезках [i-1,i] и [i,i+1] имеют общий раз-
мер, позволяющих их перемножить. Обозначим его через d[i]. Таким
образом, исходным данным в задаче является массив d[0]..d[s].
Через a(i,j) обозначим минимальную цену вычисления произве-
дения матриц на участке [i,j] (при 0<=i
