Предыдущая страница реферата | 30  31  32  33  34  35  36  37  38  39  40 | Следующая страница реферата

' Достаточно глубокий уровень рекурсии.

' Конец этого рекурсивного вызова. pc = 0

End If

Case 0 ' Возврат из рекурсии.

If TopOfStack > 0 Then

RestoreValues Depth, Dx, Dy, pc

Else

' Стек пуст. Выход.

Exit Do

End If

End Select

Loop
End Sub

======111

Время выполнения этого алгоритма может быть нелегко оценить непосредственно. Поскольку методы преобразования рекурсивных процедур в нерекурсивные не изменяют время выполнения алгоритма, эта процедура так же, как и предыдущая версия, имеет время выполнения порядка O(N4).
Программа Hilbert2 демонстрирует нерекурсивный алгоритм построения кривых
Гильберта. Задавайте вначале построение несложных кривых (меньше 6 порядка), пока не узнаете, насколько быстро будет выполняться эта программа на вашем компьютере.

Нерекурсивное построение кривых Серпинского

Приведенный ранее алгоритм построения кривых Серпинского включает в себя косвенную и множественную рекурсию. Так как алгоритм состоит из четырех подпрограмм, которые вызывают друг друга, то нельзя просто пронумеровать важные строки, как это можно было сделать в случае алгоритма построения кривых Гильберта. С этой проблемой можно справиться, слегка изменив алгоритм.
Рекурсивная версия этого алгоритма состоит из четырех подпрограмм 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

Case 2 ' SierpB

Case 3 ' SierpC

Case 4 ' 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

Рекомендуем скачать другие рефераты по теме: доклад по химии, конспект зима.





Предыдущая страница реферата | 30  31  32  33  34  35  36  37  38  39  40 | Следующая страница реферата