7.2. Запоминание последовательности рекурсивных вызовов
Как говорилось выше, рекурсивные вызовы образуют дерево, где каждый узел соответствует вызову одной процедуры. Последовательность выполнения этих процедур соответствует тому или иному алгоритму обхода узлов. Если требуется много раз обойти узлы одного и того же дерева, то можно один раз обойти их рекурсивно, запомнить количество и последовательность узлов, а затем, пользуясь этой информацией, обходить узлы уже нерекурсивно.
Например, в разделе 6.3 обсуждалась задача вычисления арифметических выражений, заданных строкой. Может возникнуть ситуация, когда одно и то же выражение потребуется вычислить много раз при различных значениях переменной x. Синтаксическое дерево, которое требуется обходить при таких вычислениях, не зависит от x. Можно обойти его один раз, построив при этом массив, где каждый элемент будет соответствовать узлу дерева, а их последовательность – порядку обхода. Повторные вычисления при новом x потребуют только нерекурсивного перебора элементов массива.
Еще один пример такого запоминания в задаче о вычислении значений многомерных полиномов смотрите тут: http://tvd-home.ru/numerical/polynom.
Такой подход не избавляет нас от рекурсии полностью. Однако он позволяет ограничиться только одним обращением к рекурсивной процедуре, что может быть достаточно, если мотивом является забота о максимальной производительности.
7.3. Определение узла дерева по его номеру
Идея данного подхода в том, чтобы заменить рекурсивные вызовы простым циклом, который выполнится столько раз, сколько узлов в дереве, образованном рекурсивными процедурами. Что именно будет делаться на каждом шаге, следует определить по номеру шага. Сопоставить номер шага и необходимые действия – задача не тривиальная и в каждом случае ее придется решать отдельно.
Например, пусть требуется выполнить k вложенных циклов по n шагов в каждом:
1
2
3
4
|
for i1 := 0 to n-1 do
for i2 := 0 to n-1 do
for i3 := 0 to n-1 do
…
|
Если k заранее неизвестно, то написать их явным образом, как показано выше невозможно. Используя прием, продемонстрированный в разделе 6.5 можно получить требуемое количество вложенных циклов с помощью рекурсивной процедуры:
1
2
3
4
5
6
7
8
9
10
11
12
13
|
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. То есть цифры соответствуют значениям счетчиков циклов. Номер шага в обычной десятичной системе счисления:
Всего шагов будет nk. Перебрав их номера в десятичной системе счисления и переведя каждый из них в систему с основанием n, получим значения индексов:
1
2
3
4
5
6
7
8
9
10
11
|
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)?
1
2
3
4
5
6
7
|
procedure Rec(a: integer);
begin
writeln(a);
if a>0 then
Rec(a-1);
writeln(a);
end;
|
(б) Чему будет равно значение функции Nod(78, 26)?
1
2
3
4
5
6
7
8
9
10
|
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)?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
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)?
1
2
3
4
5
6
7
8
9
10
|
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 раза меньше (этот коэффициент можно сделать параметром).
Рис. 16.
Литература
1. Д. Кнут. Искусство программирования на ЭВМ. т. 1. (раздел 2.3. «Деревья»).
2. Н. Вирт. Алгоритмы и структуры данных.
|
|
