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

<26 27 28 29 303132 >

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

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

for i1 := 0 to n-1 do for i2 := 0 to n-1 do for i3 := 0 to n-1 do …

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

procedure NestedCycles(Indexes: array of integer; n, k, depth: integer); var i: integer; begin if depth <= k then for i:=0 to n-1 do begin Indexes[depth] := i; NestedCycles(Indexes, n, k, depth + 1); end else DoSomething(Indexes); end;

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

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

M := round(IntPower(n, k)); for i := 0 to M-1 do begin Number := i; for p := 0 to k-1 do begin Indexes[k – p] := Number mod n; Number := Number div n; end; DoSomething(Indexes); end;

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

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

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

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

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

procedure Rec(a: integer); begin writeln(a); if a>0 then Rec(a-1); writeln(a); end;

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

function Nod(a, b: integer): integer; begin if a > b then Nod := Nod(a – b, b) else if b > a then Nod := Nod(a, b – a) else Nod := a; end;

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

procedure A(n: integer); procedure B(n: integer); procedure A(n: integer); begin writeln(n); B(n-1); end; procedure B(n: integer); begin writeln(n); if n < 5 then A(n+2); end;

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

procedure BT(x: real; D, MaxD: integer); begin if D = MaxD then writeln(x) else begin BT(x – 1, D + 1, MaxD); BT(x + 1, D + 1, MaxD); end; end;

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 раза меньше (этот коэффициент можно сделать параметром).