Определение узла дерева по его номеру

Идея данного подхода в том, чтобы заменить рекурсивные вызовы простым циклом, который выполнится столько раз, сколько узлов в дереве, образованном рекурсивными процедурами. Что именно будет делаться на каждом шаге, следует определить по номеру шага. Сопоставить номер шага и необходимые действия – задача не тривиальная и в каждом случае ее придется решать отдельно.

Например, пусть требуется выполнить k вложенных циклов по n шагов в каждом:

Если k заранее неизвестно, то написать их явным образом, как показано выше невозможно. Используя прием, продемонстрированный в разделе 6.5 можно получить требуемое количество вложенных циклов с помощью рекурсивной процедуры:

Чтобы избавиться от рекурсии и свести все к одному циклу, обратим внимание, что если нумеровать шаги в системе счисления с основанием n, то каждый шаг имеет номер, состоящий из цифр i1, i2, i3, … или соответствующих значений из массива Indexes. То есть цифры соответствуют значениям счетчиков циклов. Номер шага в обычной десятичной системе счисления:

Всего шагов будет n^k. Перебрав их номера в десятичной системе счисления и переведя каждый из них в систему с основанием n, получим значения индексов:

Еще раз отметим, что метод не универсален и под каждую задачу придется придумывать что-то свое.

Еще один замечательный пример - вычисление по номеру шага перекладываний в задаче о Ханойских башнях смотрите тут: http://algolist.manual.ru/maths/combinat/hanoi.php

Контрольные вопросы

1. Определите, что сделают приведенные ниже рекурсивные процедуры и функции.

(а) Что напечатает приведенная ниже процедура при вызове Rec(4)?

(б) Чему будет равно значение функции Nod(78, 26)?

(в) Что будет напечатано приведенными ниже процедурами при вызове A(1)?

(г) Что напечатает нижеприведенная процедура при вызове BT(0, 1, 3)?

2. Уроборос – змей, пожирающий собственный хвост (рис. 14) в развернутом виде имеет длину L, диаметр около головыD, толщину брюшной стенки d. Определите, сколько хвоста он сможет в себя впихнуть и в сколько слоев после этого будет уложен хвост?

Рис. 14. Развернутый уроборос.

3. Для дерева на рис. 10а укажите последовательности посещения узлов при прямом, обратном и концевом порядке обхода.

4. Изобразите графически дерево, заданное с помощью вложенных скобок: (A(B(C, D), E), F, G).

5. Изобразите графически синтаксическое дерево для следующего арифметического выражения:

Запишите это выражение в обратной польской записи.

6. Для приведенного ниже графа (рис. 15) запишите матрицу смежности и матрицу инцидентности.

Рис. 15.

Задачи

1. Вычислив факториал достаточно большое количество раз (миллион или больше), сравните эффективность рекурсивного и итерационного алгоритмов. Во сколько раз будет отличаться время выполнения и как это отношение будет зависеть от числа, факториал которого рассчитывается?

2. Напишите рекурсивную функцию, проверяющую правильность расстановки скобок в строке. При правильной расстановке выполняются условия:

(а) количество открывающих и закрывающих скобок равно.
(б) внутри любой пары открывающая – соответствующая закрывающая скобка, скобки расставлены правильно.

Примеры неправильной расстановки: )(, ())(, ())(() и т.п.

3. В строке могут присутствовать скобки как круглые, так и квадратные скобки. Каждой открывающей скобке соответствует закрывающая того же типа (круглой – круглая, квадратной- квадратная). Напишите рекурсивную функцию, проверяющую правильность расстановки скобок в этом случае.

Пример неправильной расстановки: ( [ ) ].

4. Число правильных скобочных структур длины 6 равно 5: ()()(), (())(), ()(()), ((())), (()()).
Напишите рекурсивную программу генерации всех правильных скобочных структур длины 2n.

Указание: Правильная скобочная структура минимальной длины «()». Структуры большей длины получаются из структур меньшей длины, двумя способами:

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

5. Создайте процедуру, печатающую все возможные перестановки для целых чисел от 1 до N.

6. Создайте процедуру, печатающую все подмножества множества {1, 2, …, N}.

7. Создайте процедуру, печатающую все возможные представления натурального числа N в виде суммы других натуральных чисел.

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

Замечание: Данный алгоритм является альтернативой приему накопления суммы. В случае вещественнозначных массивов он, обычно, позволяет получать меньшие погрешности округления.

9. Запрограммируйте быстрые методы сортировки массивов, описанные в разделе 6.4.

10. Создайте процедуру, рисующую кривую Коха (рис. 12).

11. Воспроизведите рис. 16. На рисунке на каждой следующей итерации окружности в 2.5 раза меньше (этот коэффициент можно сделать параметром).

Рис. 16.