каждого алгоритма. (Получение решений, приведенных в правом столбце, описывается в разделах 2.5 и 2.6.) При бинарном поиске задача делится пополам, выполняется одно сравнение, а затем рекурсивный вызов для одной из половин. При сортировке слиянием задача делится пополам, затем выполняется рекурсивная обработка обеих половин, после чего программа выполняет Л/ сравнений. В книге будет рассматриваться множество других алгоритмов, разработанных с применением этих рекурсивных схем.

БИНАРНЫЙ ПОИСК количество сравнений

(X)PTV1P0BKA СЛИЯНИЕМ

количество рекурсивных вызовов

количество сравнений

рекуррентное соотношение

Cjv - C,v/2 + 1

C,v = 2Сл/2+ 1

приближенное решение

Быстрая сортировка (см. главу 7) и поиск в бинарном дереве (см. главу 12) представляют важную вариацию базового подхода разделяй и властвуй , в которой задача разделяется на подзадачи размеров А: - 1 и N- к при некотором исходном значении к. При произвольном вводе эти алгоритмы делят задачи на подзадачи, размеры которых в среднем вдвое меньше исходного (что имеет место при сортировке слиянием или бинарном поиске). Влияние упомянутого различия анализируется при рассмотрении этих алгоритмов.

Рассмотрения заслуживают также следующие вариации основной темы: разделение на части различных размеров, разделение более чем на две части, разделение на перекрываюшиеся части и выполнение различного объема вычислений в нерекурсивной части алгоритма. В общем случае алгоритмы типа разделяй и властвуй требуют выполнения вычислений для разделения входного массива на части, либо для объединения результатов обработки двух независимо решенных частей исходной задачи, либо для упрощения задачи после того, как половина входного массива обработана. То есть, код может присутствовать перед, после и между двумя рекурсивными вызовами. Естественно, подобные вариации приводят к созданию более сложных алгоритмов, нежели бинарный поиск или сортировка слиянием, и эти алгоритмы труднее анализировать. В книге приводятся многочисленные примеры; к более сложным приложениям и способам анализа мы вернемся в части 8.

/kochR i

2 copy ge -{dup 0 rlineto } i

3div

2 copy kochR 60 rotate 2 copy kochR -120 rotate 2 copy kochR 60 rotate 2 copy kochR } ifelse pop pop } def 0 0 moveto 27 81 kochR 0 27 moveto 9 81 kochR 0 54 moveto 3 81 kochR

0 81 moveto

1 81 kochR stroke

РИСУНОК 5.13 РЕКУРСИВНАЯ POSTSCRIPT-ПРОГРАММА ДЛЯ РИСОВАНИЯ ФРАКТАЛА КОХА

Это изменение программы PostScript, приведенной на рис. 4.3, преобразует вывод в фрактал (см. текст).

Упражнения

5.16 Создайте рекурсивную программу, которая находит максимальный элемент в массиве, выполняя сравнение первого массива с максимальным элементом остальной части массива (вычисленным рекурсивно).

5.17 Создайте рекурсивную программу, которая находит максимальный элемент в связном списке.

5.18 Модифицируйте программу разделяй и властвуй для отыскания максимального элемента в массиве (программа 5.6), чтобы она делила массив размера N на две части, одна из которых имеет размер =2 , а вторая - N - к (чтобы размер хотя бы одной части был степенью 2).

5.19 Нарисуйте дерево, которое соответствует рекурсивным вызовам, выполняемым профаммой из упражнения 5.18 при размере массива равном 11.

5.20 Методом индукции докажите, что количество вызовов функции, выполняемых любым алгоритмом типа разделяй и властвуй , который делит задачу на части, в сумме составляющие задачу в целом, а затем решает части рекурсивно, линейно связано с размером задачи.

5.21 Докажите, что рекурсивное решение задачи о ханойских башнях (программа 5.7) является оптимальным. То есть, покажите, что любое решение требует, по меньшей мере, 2- 1 перемещений.

о 5.22 Создайте рекурсивную программу, которая вычисляет длину /-ой метки на линейке с 2 - 1 метками.

5.23 Исследуйте таблицы -разрядных чисел, подобную приведенной на рис. 5.9, на предмет определения свойства /-го числа, определяющего направление /-го перемещения (указанного знаковым битом на рис. 5.7) при решении задачи о ханойских башнях.

5.24 Создайте профамму, которая обеспечивает решение задачи о ханойских башнях путем заполнения массива, содержащего все перемещения, как сделано в программе 5.9.

о 5.25 Создайте рекурсивную программу, которая заполняет массив размера -на-2 нулями и единицами таким образом, чтобы массив представлял все -разрядные числа, как показано на рис. 5.9.

5.26 Отобразите результаты использования рекурсивной программы рисования линейки (программы 5.8) для следующих значений аргументов: rule(0, 11, 4), rule(4, 20, 4) и riile(7, 30, 5).

5.27 Докажите следующее свойство программы рисования линейки (программы 5.8): если разность между ее первыми двумя аргументами является степенью 2, то оба ее рекурсивных вызова также обладают этим свойством.

о 5.28 Создайте функцию, которая эффективно вычисляет количество оконечных нулей в двоичном представлении целого числа.

о 5.29 Сколько квадратов изображено на рис. 5.12 (включая и те, которые скрыты большими квадратами)?

о 5.30 Создайте рекурсивную профамму на С++, результатом которой будет PoslScript-программа в форме списка вызовов функций х у г box, обеспечивающая

отображение нижнего рисунка рис. 5.12; функция box рисует квадрат размера г-на-г в точке с координатами (jc,). Реализуйте функцию box в виде команд PostScript (см. раздел 4.3).

5.31 Создайте восходящую нерекурсивную программу (аналогичную программе 5.9), которая обеспечивает отображение верхнего рисунка рис. 5.12, как описано в упражнении 5.30.

5.32 Создайте программу PostScript, обеспечивающую рисование нижней части рис. 5.12.

> 5.33 Сколько линейных сегментов содержит звезда Коха -го порядка?

5.34 Рисование звезды Коха я-го порядка сводится к выполнению последовательности команд типа повернуть на а фадусов, затем нарисовать сегмент линии длиной 1/3 . Установите соответствие с системами счисления, позволяющее рисовать звезду путем увеличения значения счетчика и последующего вычисления на базе этого значения угла а.

5.35 Модифицируйте программу рисования звезды Коха, приведенную на рис. 5.13, для создания другого фрактала, основывающегося на фигуре, состоящей из 5 линий нулевого порядка, вычерчиваемых путем смещения на одну условную единицу в восточном, северном, восточном, южном и восточном направлениях (см. рис. 4.3).

5.36 Создайте рекурсивную функцию типа разделяй и властвуй для рисования аппроксимации сегмента линии в пространстве целочисленных координат для заданных конечных точек. Примите, что координаты изменяются в интервале от О до М. Совет: вначале вычертите точку вблизи середины сегмента.

5.3 Динамическое программирование

Главная особенность алгоритмов типа разделяй и властвуй , рассмотренных нами в разделе 5.2, - разделение ими задачи на независимые подзадачи. Когда подзадачи не являются независимыми, ситуация усложняется, в первую очередь потому, что непосредственная рекурсивная реализация даже простейщих алгоритмов этого типа может требовать неприемлемо больших затрат времени. В этом разделе рассматривается систематический подход для избежания этой опасности в некоторых случаях.

Например, программа 5.10 - непосредственная рекурсивная реализация рекуррентного соотношения, определяющего числа Фибоначчи (см. раздел 3.3). Не используйте эту программу - она весьма неэффективна. Действительно, количество рекурсивных вызовов для вычисления /д- равно Fn+i- Но /л- приближенно равно ф, где ф ~ 1,618 - золотая пропорция. Как это ни удивительно, но для профаммы 5.10 время этого элементарного вычисления определяется экспоненциальной зависимостью. Рисунок 5.14, на котором приведены рекурсивные вызовы для небольшого примера, весьма наглядно демонстрирует требуемый объем повторных вычислений.

И напротив, можно легко вычислить первые jV чисел Фибоначчи за время, пропорциональное значению N, используя следующий массив:

F[0] = 0; F[l] = 1;

For (i = 2; i <= N; i++

F[i] = F[i-1] + F[i-21;