Реферат: VB, MS Access, VC++, Delphi, Builder C++ принципы(технология), алгоритмы программирования
Рекурсивная версия этого алгоритма состоит из четырех подпрограмм SierpA, SierpB, SierpC и SierpD. Подпрограмма SierpA выглядит так:
Private Sub SierpA(Depth As Integer, Dist As Single)
If Depth = 1 Then
Line -Step(-Dist, Dist)
Line -Step(-Dist, 0)
Line -Step(-Dist, -Dist)
Else
SierpA Depth - 1, Dist
Line -Step(-Dist, Dist)
SierpB Depth - 1, Dist
Line -Step(-Dist, 0)
SierpD Depth - 1, Dist
Line -Step(-Dist, -Dist)
SierpA Depth - 1, Dist
End If
End Sub
Три другие процедуры аналогичны. Несложно объединить эти четыре процедуры в одну подпрограмму.
Private Sub SierpAll(Depth As Integer, Dist As Single, Func As Integer)
Select Case Punc
Case 1 ' SierpA
<код SierpA code>
Case 2 ' SierpB
<код SierpB>
Case 3 ' SierpC
<код SierpC>
Case 4 ' SierpD
<код SierpD>
End Select
End Sub
======112
Параметр Func сообщает подпрограмме, какой блок кода выполнять. Вызовы подпрограмм заменяются на вызовы процедуры SierpAll с соответствующим значением Func. Например, вызов подпрограммы SierpA заменяется на вызов процедуры SierpAll с параметром Func, равным 1. Таким же образом заменяются вызовы подпрограмм SierpB, SierpC и SierpD.
Полученная процедура рекурсивно вызывает себя в 16 различных точках. Эта процедура намного сложнее, чем процедура Hilbert, но в других отношениях она имеет такую же структуру и поэтому к ней можно применить те же методы устранения рекурсии.
Можно использовать первую цифру меток pc, для определения номера блока кода, который должен выполняться. Перенумеруем строки в коде SierpA числами 11, 12, 13 и т.д. Перенумеруем строки в коде SierpB числами 21, 22, 23 и т.д.
Теперь можно пронумеровать ключевые строки кода внутри каждого из блоков. Для кода подпрограммы SierpA ключевыми строками будут:
' Код SierpA.
11 If Depth = 1 Then
Line -Step(-Dist, Dist)
Line -Step(-Dist, 0)
Line -Step(-Dist, -Dist)
Else
SierpA Depth - 1, Dist
12 Line -Step(-Dist, Dist)
SierpB Depth - 1, Dist
13 Line -Step(-Dist, 0)
SierpD Depth - 1, Dist
14 Line -Step(-Dist, -Dist)
SierpA Depth - 1, Dist
End If
Типичная «рекурсия» из кода подпрограммы SierpA в код подпрограммы SierpB выглядит так:
SaveValues Depth, 13 ' Продолжить с шага 13 после завершения.
Depth = Depth - 1
pc = 21 ' Передать управление на начало кода SierpB.
======113
Метка 0 зарезервирована для обозначения выхода из «рекурсии». Следующий код демонстрирует нерекурсивную версию процедуры SierpAll. Код для подпрограмм SierpB, SierpC, и SierpD аналогичен коду для SierpA, поэтому он опущен.
Private Sub SierpAll(Depth As Integer, pc As Integer)
Do
Select Case pc
' **********
' * SierpA *
' **********
Case 11
If Depth <= 1 Then
SierpPicture.Line -Step(-Dist, Dist)
SierpPicture.Line -Step(-Dist, 0)
SierpPicture.Line -Step(-Dist, -Dist)
pc = 0
Else
SaveValues Depth, 12 ' Выполнить SierpA
Depth = Depth - 1
pc = 11
End If
Case 12
SierpPicture.Line -Step(-Dist, Dist)
SaveValues Depth, 13 ' Выполнить SierpB
Depth = Depth - 1
pc = 21
Case 13
SierpPicture.Line -Step(-Dist, 0)
SaveValues Depth, 14 ' Выполнить SierpD
Depth = Depth - 1
pc = 41
Case 14
SierpPicture.Line -Step(-Dist, -Dist)
SaveValues Depth, 0 ' Выполнить SierpA
Depth = Depth - 1
pc = 11
' Код для SierpB, SierpC и SierpD опущен.
:
' *******************
' * Конец рекурсии. *
' *******************
Case 0
If TopOfStack <= 0 Then Exit Do
RestoreValues Depth, pc
End Select
Loop
End Sub
=====114
Так же, как и в случае с алгоритмом построения кривых Гильберта, преобразование алгоритма построения кривых Серпинского в нерекурсивную форму не изменяет время выполнения алгоритма. Новая версия алгоритма имитирует рекурсивный алгоритм, который выполняется за время порядка O(N4), поэтому порядок времени выполнения новой версии также составляет O(N4). Она выполняется немного медленнее, чем рекурсивная версия, и является намного более сложной.
Нерекурсивная версия также могла бы рисовать кривые более высоких порядков, но построение кривых Серпинского с порядком выше 8 или 9 непрактично. Все эти факты определяют преимущество рекурсивного алгоритма.
Программа Sierp2 использует этот нерекурсивный алгоритм для построения кривых Серпинского. Задавайте вначале построение несложных кривых (меньше 6 порядка), пока не определите, насколько быстро будет выполняться эта программа на вашем компьютере.
Резюме
При применении рекурсивных алгоритмов следует избегать трех основных опасностей:
· Бесконечной рекурсии. Убедитесь, что условия остановки вашего алгоритма прекращают все рекурсивные пути.
· Глубокой рекурсии. Если алгоритм достигает слишком большой глубины рекурсии, он может привести к переполнению стека. Минимизируйте использование стека за счет уменьшения числа определяемых в процедуре переменных, использования глобальных переменных, или определения переменных как статических. Если процедура все равно приводит к переполнению стека, перепишите алгоритм в нерекурсивном виде, используя устранение хвостовой рекурсии.
· Ненужной рекурсии. Обычно это происходит, если алгоритм типа рекурсивного вычисления чисел Фибоначчи, многократно вычисляет одни и те же промежуточные значения. Если вы столкнетесь с этой проблемой в своей программе, попробуйте переписать алгоритм, используя подход снизу вверх. Если алгоритм не позволяет прибегнуть к подходу снизу вверх, создайте таблицу промежуточных значений.
Применение рекурсии не всегда неправильно. Многие задачи являются рекурсивными по своей природе. В этих случаях рекурсивный алгоритм будет проще понять, отлаживать и поддерживать, чем его нерекурсивную версию. В качестве примера можно привести алгоритмы построения кривых Гильберта и Серпинского. Оба по своей природе рекурсивны и намного понятнее, чем их нерекурсивные модификации. При этом рекурсивные версии даже выполняются немного быстрее.
Если у вас есть алгоритм, который рекурсивен по своей природе, но вы не уверены, будет ли рекурсивная версия лишена проблем, запишите алгоритм в рекурсивном виде и выясните это. Может быть, проблемы не возникнут. Если же они возникнут, то, возможно, окажется проще преобразовать эту рекурсивную версию в нерекурсивную, чем написать нерекурсивную версию с нуля.
======115
Глава 6. ДеревьяВо 2 главе приводились способы создания динамических связных структур, таких, как изображенные на рис 6.1. Такие структуры данных называются графами (graphs). В 12 главе алгоритмы работы с графами и сетями обсуждаются более подробно. В этой главе рассматриваются графы особого типа, которые называются деревьями (trees).
В начале этой главы приводится определение дерева и разъясняются некоторые термины. Затем в ней описываются некоторые методы реализации деревьев различных типов на языке Visual Basic. В последующих разделах рассматривается несколько алгоритмов обхода для деревьев, записанных в этих разных форматах. Глава заканчивается обсуждением некоторых специальных типов деревьев, включая упорядоченные деревья (sorted trees), деревья со ссылками[RV7] (threaded trees), боры[RV8] (tries) и квадродеревья[RV9] (quadtrees).
В 7 и 8 главе обсуждаются более сложные темы — сбалансированные деревья и деревья решений.
@Рис. 6.1. Графы
=====117
Определения
Можно рекурсивно определить дерево как:
* Пустую структуру или
* Узел, называемый корнем (node) дерева, связанный с нулем или более поддеревьев (subtrees).
На рис. 6.2 показано дерево. Корневой узел A связан с тремя поддеревьями, начинающимися в узлах B, C и D. Эти узлы связаны с поддеревьями с корнями E, F и G, и эти узлы, в свою очередь связаны с поддеревьями с корнями H, I и J.
Терминология деревьев представляет собой смесь терминов, позаимствованных из ботаники и генеалогии. Из ботаники пришли термины, такие как узел (node), определяемый как точка, в которой может начинаться ветвление, ветвь (branch), определяемая как связь между двумя узлами, и лист (leaf) — узел, из которого не выходят другие ветви.
Из генеалогии пришли термины, которые описывают родство. Если один узел находится непосредственно над другим, верхний узел называется родителем (parent), а нижний дочерним узлом (child). Узлы на пути вверх от узла до корня называются предками (ancestors) узла. Например, на рис. 6.2 узлы E, B и A — это все предки узла I.
Узлы, которые находятся ниже какого‑либо узла дерева, называются потомками (descendants) этого узла. Узлы E, H, I и J на рис. 6.2 — это все потомки узла B.
Иногда узлы, имеющие одного родителя, называются узлами‑братьями или узлами‑сестрами (sibling nodes).
Существует еще несколько терминов, которые не пришли из ботаники или генеалогии. Внутренним узлом (internal node) называется узел, который не является листом. Порядком узла (node degree) называется число его дочерних узлов. Порядок дерева — это наибольший порядок его узлов. Дерево на рис. 6.2 — третьего порядка, потому что узлы с наибольшим порядком, узлы A и E, имеют по 3 дочерних узла.
Глубина (depth) дерева равна числу его предков плюс 1. На рис. 6.2 глубина узла E равна 3. Глубиной (depth) или высотой (height) дерева называется наибольшая глубина его узлов. Глубина дерева на рис. 6.2 равна 4.
Дерево 2 порядка называется двоичным деревом (binary tree). Деревья третьего порядка иногда называются троичными[RV10] (ternary) деревьями. Более того, деревья порядка N иногда называются N‑ичными (N‑ary) деревьями.
@Рис. 6.2. Дерево
======118
Дерево порядка 12, например, называется 12‑ричным (12‑ary) деревом, а не додекадеричным (dodecadary) деревом. Некоторые избегают употребления лишних терминов и просто говорят «деревья 12 порядка».
Рис. 6.3 иллюстрирует некоторые из этих терминов.
Представления деревьев
Теперь, когда вы познакомились с терминологией, вы можете представить себе способы реализации деревьев на языке Visual Basic. Один из способов — создать отдельный класс для каждого типа узлов дерева. Для построения дерева, показанного на рис. 6.3, вы можете определить структуры данных для узлов, которые имеют ноль, один, два или три дочерних узла. Этот подход был бы довольно неудобным. Кроме того, что нужно было бы управлять четырьмя различными классами, в классах потребовались бы какие‑то флаги, которые бы указывали тип дочерних узлов. Алгоритмы, которые оперировали бы этими деревьями, должны были бы уметь работать со всем различными типами деревьев.
Полные узлы
В качестве простого решения можно определить один тип узлов, который содержит достаточное число указателей на потомков для представления всех нужных узлов. Я называю это методом полных узлов, так как некоторые узлы могут быть большего размера, чем необходимо на самом деле.
Дерево, изображенное на рис 6.3, имеет 3 порядок. Для построения этого дерева с использованием метода полных узлов (fat nodes), требуется определить единственный класс, который содержит указатели на три дочерних узла. Следующий код демонстрирует, как эти указатели могут быть определены в классе TernaryNode.
Public LeftChild As TernaryNode
Public MiddleChild As TernaryNode
Public RightChild As TernaryNode
@Рис. 6.3. Части троичного (3 порядка) дерева
======119
При помощи этого класса можно построить дерево, используя записи Child узлов, для связи их друг с другом. Следующий фрагмент кода строит два верхних уровня дерева, показанного на рис. 6.3.
Dim A As New TernaryNode
Dim B As New TernaryNode
Dim C As New TernaryNode
Dim D As New TernaryNode
:
Set A.LeftChild = B
Set A.MiddleChild = C
[RV11] :
Программа Binary, показанная на рис. 6.4, использует метод полных узлов для работы с двоичным деревом. Когда вы выбираете узел с помощью мыши, программа подсвечивает кнопку Add Left (Добавить слева), если узел не имеет левого потомка и кнопку Add Right (Добавить справа), если узел не имеет правого потомка. Кнопка Remove (Удалить) разблокируется, если выбранный узел не является корневым. Если вы нажмете на кнопку Remove, программа удалит узел и всех его потомков.
Поскольку программа позволяет создать узлы с нулевым числом, одним или двумя дочерними узлами, она использует представление в виде полных узлов. Вы можете легко распространить этот пример на деревья более высоких порядков.
Списки потомков
Если порядки узлов в дереве сильно различаются, метод полных узлов приводит к напрасному расходованию большого количества памяти. Чтобы построить дерево, показанное на рис. 6.5 с использованием полных узлов, вам понадобится определить в каждом узле по шесть указателей, хотя только в одном узле все шесть из них используются. Это представление дерева потребует 72 указателей на дочерние узлы, из которых в действительности будет использоваться только 11.
@Рис. 6.4. Программа Binary
======120
Некоторые программы добавляют и удаляют узлы, изменяя порядок узлов в процессе выполнения. В этом случае метод полных узлов не будет работать. Такие динамически изменяющиеся деревья можно представить, поместив дочерние узлы в списки. Есть несколько подходов, которые можно использовать для создания списков дочерних узлов. Наиболее очевидный подход заключается в создании в классе узла открытого (public) массива дочерних узлов, как показано в следующем коде. Тогда для оперирования дочерними узлами можно использовать методы работы со списками на основе массивов.
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48
