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

Эти уравнения почти совпадают с уравнениями, которые использовались для оценки времени выполнения алгоритма, рисующего кривые Гильберта.
Единственное отличие состоит в том, что для кривых Гильберта T(1) = 1.
Сравнение значений этих уравнений показывает, что
TSierpinski(N) = THilbert(N+1). В конце предыдущего раздела было показано, что THilbert(N) = (4N - 1) / 3, поэтому TSierpinski(N) = (4N+1 - 1) / 3, что также составляет O(4N).

=====95

Так же, как и алгоритм построения кривых Гильберта, этот алгоритм выполняется за время порядка O(4N), но это не так уж и плохо. Кривая
Серпинского состоит из O(4N) линий, поэтому ни один алгоритм не может нарисовать кривую Серпинского быстрее, чем за время порядка O(4N).
Кривые Серпинского также полностью заполняют экран большинства компьютеров при порядке кривой, большем или равном 9. При каком-то порядке, большем 9, вы столкнетесь с ограничениями языка Visual Basic и возможностей вашего компьютера, но, скорее всего, вы еще раньше будете ограничены предельным разрешением экрана.
Программа Sierp, показанная на рис. 5.10, использует этот рекурсивный алгоритм для рисования кривых Серпинского. При выполнении программы, задавайте вначале небольшую глубину рекурсии (меньше 6), до тех пор, пока вы не определите, насколько быстро выполняется эта программа на вашем компьютере.

Опасности рекурсии

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

Бесконечная рекурсия

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

@Рис. 5.10 Программа Sierp

=====96

Private Function BadFactorial(num As Integer) As Integer

BadFactorial = num * BadFactorial (num - 1)
End Function

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

Private Function BadFactorial2(num As Double) As Double

If num = 0 Then

BadFactorial2 = 1

Else

BadFactorial2 = num * BadFactorial2(num-1)

End If
End Function

Следующая версия функции Fibonacci является более сложным примером. В ней условие остановки рекурсии прекращает выполнение только нескольких путей рекурсии, и возникают те же проблемы, что и при выполнении функции
BadFactorial2, если входные значения отрицательные или не целые.

Private Function BadFib(num As Double) As Double

If num = 0 Then

BadFib = 0

Else

BadFib = BadPib(num - 1) + BadFib (num - 2)

End If
End Function

И последняя проблема, связанная с бесконечной рекурсией, заключается в том, что «бесконечная» на самом деле означает «до тех пор, пока не будет исчерпано стековое пространство». Даже корректно написанные рекурсивные процедуры будут иногда приводить к переполнению стека и аварийному завершению работы. Следующая функция, которая вычисляет сумму N + (N - 1) +
… + 2 +1, приводит к исчерпанию стекового пространства при больших значениях N. Наибольшее возможное значение N, при котором программа еще будет работать, зависит от конфигурации вашего компьютера.

Private Function BigAdd(N As Double) As Double

If N 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.

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



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

Поделитесь этой записью или добавьте в закладки