Смекни!
smekni.com

VB, MS Access, VC++, Delphi, Builder C++ принципы(технология), алгоритмы программирования (стр. 24 из 72)

Private Sub Factorial(num As Integer, value As Integer)

ReDim num_stack(1 to 200) As Integer

ReDim pc_stack(1 to 200) As Integer

Dim stack_top As Integer ' Вершина стека.

Dim pc As Integer

pc = 1

Do

Select Case pc

Case 1

If num <= 1 Then ' Это условие остановки. value = 1

pc = 0 ' Конец рекурсии.

Else ' Рекурсия.

' Сохранить num и следующее значение pc.

stack_top = stack_top + 1

num_stack(stack_top) = num

pc_stack(stack_top) = 2 ' Возобновить с 2.

' Начать рекурсию.

num = num - 1

' Перенести блок управления в начало.

pc = 1

End If

Case 2

' value содержит результат последней

' рекурсии. Умножить его на num.

value = value * num

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

pc = 0

Case 0

' Конец "рекурсии".

' Если стеки пусты, исходный вызов

' подпрограммы завершен.

If stack_top <= 0 Then Exit Do

' Иначе восстановить локальные переменные и pc.

num = num_stack(stack_top)

pc = pc_stack(stack_top)

stack_top = stacK_top - 1

End Select

Loop

End Sub

Так же, как и устранение хвостовой рекурсии, этот метод имитирует поведение рекурсивного алгоритма. Процедура заменяет каждый рекурсивный вызов итерацией цикла While. Поскольку число шагов остается тем же самым, полное время выполнения алгоритма не изменяется.

Так же, как и в случае с устранением хвостовой рекурсии, этот метод устраняет глубокую рекурсию, которая может переполнить стек.

Нерекурсивное построение кривых Гильберта

Пример вычисления факториала из предыдущего раздела превратил простую, но неэффективную рекурсивную функцию вычисления факториала в сложную и неэффективную нерекурсивную процедуру. Намного лучший нерекурсивный алгоритм вычисления факториала, был представлен ранее в этой главе.

=======107-108

Может оказаться достаточно трудно найти простую нерекурсивную версию для более сложных алгоритмов. Методы из предыдущего раздела могут быть полезны, если алгоритм содержит многократную или косвенную рекурсию.

В качестве более интересного примера, рассмотрим нерекурсивный алгоритм построения кривых Гильберта.

Private Sub Hilbert(depth As Integer, Dx As Single, Dy As Single)

If depth > 1 Then Hilbert depth - 1, Dy, Dx

HilbertPicture.Line -Step(Dx, Dy)

If depth > 1 Then Hilbert depth - 1, Dx, Dy

HilbertPicture.Line -Step(Dy, Dx)

If depth > 1 Then Hilbert depth - 1, Dx, Dy

HilbertPicture.Line -Step(-Dx, -Dy)

If depth > 1 Then Hilbert depth - 1, -Dy, -Dx

End Sub

В следующем фрагменте кода первые строки каждого блока кода между рекурсивными шагами пронумерованы. Эти блоки включают первую строку процедуры и любые другие точки, в которых может понадобиться продолжить выполнение после возврата после «рекурсии».

Private Sub Hilbert(depth As Integer, Dx As Single, Dy As Single)

1 If depth > 1 Then Hilbert depth - 1, Dy, Dx

2 HilbertPicture.Line -Step(Dx, Dy)

If depth > 1 Then Hilbert depth - 1, Dx, Dy

3 HilbertPicture.Line -Step(Dy, Dx)

If depth > 1 Then Hilbert depth - 1, Dx, Dy

4 HilbertPicture.Line -Step(-Dx, -Dy)

If depth > 1 Then Hilbert depth - 1, -Dy, -Dx

End Sub

Каждый раз, когда нерекурсивная процедура начинает «рекурсию», она должна сохранять значения локальных переменных Depth, Dx, и Dy, а также следующее значение переменной pc. После возврата из «рекурсии», она восстанавливает эти значения. Для упрощения работы, можно написать пару вспомогательных процедур для заталкивания и выталкивания этих значений из нескольких стеков.

====109

Const STACK_SIZE =20

Dim DepthStack(0 To STACK_SIZE)

Dim DxStack(0 To STACK_SIZE)

Dim DyStack(0 To STACK_SIZE)

Dim PCStack(0 To STACK_SIZE)

Dim TopOfStack As Integer

Private Sub SaveValues (Depth As Integer, Dx As Single, _

Dy As Single, pc As Integer)

TopOfStack = TopOfStack + 1

DepthStack(TopOfStack) = Depth

DxStack(TopOfStack) = Dx

DyStack(TopOfStack) = Dy

PCStack(TopOfStack) = pc

End Sub

Private Sub RestoreValues (Depth As Integer, Dx As Single, _

Dy As Single, pc As Integer)

Depth = DepthStack(TopOfStack)

Dx = DxStack(TopOfStack)

Dy = DyStack(TopOfStack)

pc = PCStack(TopOfStack)

TopOfStack = TopOfStack - 1

End Sub

Следующий код демонстрирует нерекурсивную версию подпрограммы Hilbert.

Private Sub Hilbert(Depth As Integer, Dx As Single, Dy As Single)

Dim pc As Integer

Dim tmp As Single

pc = 1

Do

Select Case pc

Case 1

If Depth > 1 Then ' Рекурсия.

' Сохранить текущие значения.

SaveValues Depth, Dx, Dy, 2

' Подготовиться к рекурсии.

Depth = Depth - 1

tmp = Dx

Dx = Dy

Dy = tmp

pc = 1 ' Перейти в начало рекурсивного вызова.

Else ' Условие остановки.

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

' Продолжить со 2 блоком кода.

pc = 2

End If

Case 2

HilbertPicture.Line -Step(Dx, Dy)

If Depth > 1 Then ' Рекурсия.

' Сохранить текущие значения.

SaveValues Depth, Dx, Dy, 3

' Подготовиться к рекурсии.

Depth = Depth - 1

' Dx и Dy остаются без изменений.

pc = 1 Перейти в начало рекурсивного вызова.

Else ' Условие остановки.

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

' Продолжить с 3 блоком кода.

pc = 3

End If

Case 3

HilbertPicture.Line -Step(Dy, Dx)

If Depth > 1 Then ' Рекурсия.

' Сохранить текущие значения.

SaveValues Depth, Dx, Dy, 4

' Подготовиться к рекурсии.

Depth = Depth - 1

' Dx и Dy остаются без изменений.

pc = 1 Перейти в начало рекурсивного вызова.

Else ' Условие остановки.

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

' Продолжить с 4 блоком кода.

pc = 4

End If

Case 4

HilbertPicture.Line -Step(-Dx, -Dy)

If Depth > 1 Then ' Рекурсия.

' Сохранить текущие значения.

SaveValues Depth, Dx, Dy, 0

' Подготовиться к рекурсии.

Depth = Depth - 1

tmp = Dx

Dx = -Dy

Dy = -tmp

pc = 1 Перейти в начало рекурсивного вызова.

Else ' Условие остановки.

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

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

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

<код 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). Она выполняется немного медленнее, чем рекурсивная версия, и является намного более сложной.