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

Упражнения

> 5.37 Создайте функцию, которая вычисляет по модулю М, используя строго постоянный объем памяти для промежуточных вычислений,

5.38 Каково наибольшее значение N, для которого может быть представлено в виде 64-разрядного целого числа?

о 5.39 Нарисуйте дерево, которое соответствует рис. 5.15 для случая, когда выполнена взаимная замена рекурсивных вызовов в программе 5.11.

5.40 Создайте функцию, которая использует восходящее динамическое программирование для вычисления значения /\, определяемого рекуррентным соотношением

Pn = La/2J + Pu/2j + P\N/2], для N> 1, при Po = 0.

Нарисуйте график зависимости Pfj - N\gN/2 от jV для О < N < 1024.

5.41 Создайте функцию, в которой восходящее дин-амическое программирование используется для решения упражнения 5.40.

о 5.42 Нарисуйте дерево, которое соответствует рис. 5.15 для функции из упражнения 5.41 при значении N= 23.

5.43 Нарисуйте график зависимости количества рекурсивных вызовов, выполняемых функцией из упражнения 5.41 для вычисления Рдт, от Лдля О < Л < 1024. (Для выполнения этих вычислений для каждого значения программа должна запускаться заново.)

5.44 Создайте функцию, в которой восходящее динамическое программирование используется для вычисления значения С, определенного рекуррентным соотношением

Cn=N+- (Ck-i+C-k),

\<k<N

для jV > 1, при Со = 1

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

о 5.46 Нарисуйте дерево, которое соответствует рис. 5.15 для функции из упражнения 5.45 при значении N= 23.

5.47 Нарисуйте график зависимости количества рекурсивных вызовов, выполняемых функцией из упражнения 5.45 для вычисления Сг, от Лдля О < Л < 1024. (Для выполнения этих вычислений для каждого значения Л программа должна запускаться заново.)

> 5.48 Приведите содержимое массивов maxKnown и itemKnown, вычисленное программой 5.13 для вызова кпар(17) применительно к элементам, приведенным на рис. 5.16.

t> 5.49 Приведите дерево, соответствующее рис. 5.18 при допущении, что элементы рассматриваются в порядке уменьшения их размеров.

5.50 Докажите лемму 5.3.

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

5.52 Создайте функцию, которая решает задачу о ранце методом нисходящего динамического программирования, но используя при этом рекурсивное решение, основывающееся на вычислении оптимального количества конкретного элемента, который должен быть помещен в ранец, исходя из определения (рекурсивно) оптимального способа упаковки ранца без этого элемента.

о 5.53 Создайте функцию, решающую задачу о ранце, используя версию рекурсивного решения, описанного в упражнении 5.52, в которой применяется восходящее динамическое программирование.

5.54 Воспользуйтесь динамическим программированием для решения упражнения 5.4. Обеспечьте отслеживание общего количества сохраняемых вызовов функций.

5.55 Создайте программу, в которой нисходящее динамическое программирова-

, исходя из

ние применяется для вычисления биномиального коэффициента рекурсивного соотношения

= 1.

5.4 Деревья

Деревья - это математические абстракции, играющие главную роль при разработке и анализе аяторитмов, поскольку

мы HcnoAJuayeM деревья для описания динамических свойств алгоритмов;

мы строим и используем явные структуры данных, которые являются конкретными реализациями деревьев.

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

Мы часто встречаемся с деревьями в повседневной жизни - это основное понятие очень хорошо знакомо. Например, многие люди отслеживают предков и наследников с помощью генеалогического дерева; как будет показано, значительная часть терминов заимствована именно из этой области применения. Еще один пример - организация спортивных турниров; среди прочих, в исследовании этого применения принял участие и Льюис Кэрролл (Lewis Carroll). В качестве третьего примера можно привести организационную диаграмму большой корпорации; это применение отличается иерархическим разделением, характерным для алгоритмов типа разделяй и властвуй . Четвертым примером служит дерево синтаксического разложения предло-

жения английского (или любого другого языка) на составляющие его части; такое дерево близко связано с обработкой компьютерных языков, как описано в части 5. Типичный пример дерева, в данном случае описывающего структуру этой книги, показан на рис. 5.19. В книге рассматривается и множество других примеров применения деревьев.

Применительно к компьютерам, одно из наиболее известных применений структур деревьев - для организации файловых систем. Файлы хранятся в каталогах (иногда называемых также папками), которые рекурсивно определяются как последовательности каталогов и файлов. Это рекурсивное определение снова отражает естественное рекурсивное разбиение на составляющие и идентично определению определенного типа дерева.

Существует множество различных типов деревьев, и важно понимать различие между абстракцией и конкретным представлением, с которым выполняется работа для данного приложения. Соответственно, мы подробно рассмотрим различные типы деревьев и их представления. Рассмотрение начнется с определения деревьев как абстрактных объектов и с ознакомления с большинством основных связанных с ними терминов. Мы неформально рассмотрим различные типы деревьев, которые следует рассматривать в порядке сужения самого этого понятия:

Деревья

Деревья с корнем

Упорядоченные деревья

М-арные и бинарные деревья

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

Дерево (tree) - это непустая коллекция вершин и ребер, удовлетворяющих определенным требованиям. Вершина (vertex) - это простой объект (называемый также узлом (node)), который может иметь имя и содержать другую связанную с ним информацию; ребро (edge) - это связь между двумя вершинами. Путь (path) в дереве - это список отдельных вершин, в котором следующие друг за другом вершины соединяются ребрами дерева. Определяющее свойство дерева - существование только одно пути, соединяющего любые два узла. Если между какой-либо парой узлов существует более одного пути или если между какой-либо парой узлов путь отсутствует, мы имеем граф, а не дерево. Несвязанный набор деревьев называется бором (forest).

основы ) ( структуры данных )

(гГА Уь) (6

РИСУНОК 5.19 ДЕРЕВО

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