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

Факториал числа N записывается как N! (произносится «эн факториал»). По определению, 0! равно 1. Остальные значения определяются формулой:

N! = N * (N - 1) * (N - 2) * ... * 2 * 1

Как уже упоминалось в 1 главе, эта функция чрезвычайно быстро растет с увеличением N. В табл. 5.1 приведены 10 первых значений функции факториала.

Можно также определить функцию факториала рекурсивно:

0! = 1
N! = N * (N - 1)! для N > 0.

@Рис. 5.1. Дерево, составленное из двух деревьев меньшего размера

===========82

@Таблица 5.1. Значения функции факториала

Легко написать на основе этого определения рекурсивную функцию:

Public Function Factorial(num As Integer) As Integer

If num = 2 * Fib(N) - 1

С точностью до порядка это составит O(Fib(N)). Интересно, что эта функция не только рекурсивная, но она также используется для оценки времени ее выполнения.
Чтобы помочь вам представить скорость роста функции Фибоначчи, можно показать, что Fib(M)>(M-2 где ( — константа, примерно равная 1,6. Это означает, что время выполнения не меньше, чем значение экспоненциальной функции O((M). Как и другие экспоненциальные функции, эта функция растет быстрее, чем полиномиальные функции, но медленнее, чем функция факториала.
Поскольку время выполнения растет очень быстро, этот алгоритм довольно медленно выполняется для больших входных значений. Фактически, настолько медленно, что на практике почти невозможно вычислить значения функции
Fib(N) для N, которые намного больше 30. В табл. 5.4 показано время выполнения для этого алгоритма на компьютере с процессором Pentium с тактовой частотой 90 МГц при разных входных значениях.
Программа Fibo использует этот рекурсивный алгоритм для вычисления чисел
Фибоначчи. Введите целое число и нажмите на кнопку Go для вычисления чисел
Фибоначчи. Начните с небольших чисел, пока не оцените, насколько быстро ваш компьютер может выполнять эти вычисления.

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

Кривые Гильберта (Hilbert curves) — это самоподобные (self-similar) кривые, которые обычно определяются при помощи рекурсии. На рис. 5.2. показаны кривые Гильберта с 1, 2 или 3 порядка.

@Таблица 5.4. Время выполнения программы Fibonacci

=====88

@Рис. 5.2. Кривые Гильберта

Кривая Гильберта, как и любая другая самоподобная кривая, создается разбиением большой кривой на меньшие части. Затем вы можете использовать эту же кривую, после изменения размера и поворота, для построения этих частей. Эти части можно разбить на более мелкие части, и так далее, пока процесс не достигнет нужной глубины рекурсии. Порядок кривой определяется как максимальная глубина рекурсии, которой достигает процедура.
Процедура Hilbert управляет глубиной рекурсии, используя соответствующий параметр. При каждом рекурсивном вызове, процедура уменьшает параметр глубины рекурсии на единицу. Если процедура вызывается с глубиной рекурсии, равной 1, она рисует простую кривую 1 порядка, показанную на рис. 5.2 слева и завершает работу. Это условие остановки рекурсии.
Например, кривая Гильберта 2 порядка состоит из четырех кривых Гильберта 1 порядка. Аналогично, кривая Гильберта 3 порядка состоит из четырех кривых 2 порядка, каждая из которых состоит из четырех кривых 1 порядка. На рис. 5.3 показаны кривые Гильберта 2 и 3 порядка. Меньшие кривые, из которых построены кривые большего размера, выделены полужирными линиями.
Следующий код строит кривую Гильберта 1 порядка:

Line -Step (Length, 0)
Line -Step (0, Length)
Line -Step (-Length, 0)

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

Private Sub Hilbert(Depth As Integer)

If Depth = 1 Then

Нарисовать кривую Гильберта 1 порядка

Else

Нарисовать и соединить 4 кривые порядка (Depth - 1)

End If
End Sub

====89

@Рис. 5.3. Кривые Гильберта, образованные меньшими кривыми

Этот метод требует небольшого усложнения для определения направления рисования кривых. Это требуется для того, чтобы выбрать тип используемых кривых Гильберта.
Эту информацию можно передать процедуре при помощи параметров Dx и Dy для определения направления вывода первой линии в кривой. Для кривой 1 порядка, процедура рисует первую линию при помощи функции Line-Step(Dx, Dy). Если кривая имеет более высокий порядок, процедура соединяет первые две подкривых, используя функцию Line-Step(Dx, Dy). В любом случае, процедура может использовать параметры Dx и Dy для выбора направления, в котором она должна рисовать линии, образующие кривую.
Код на языке Visual Basic для рисования кривых Гильберта короткий, но сложный. Вам может потребоваться несколько раз пройти его в отладчике для кривых 1 и 2 порядка, чтобы увидеть, как изменяются параметры Dx и Dy, при построении различных частей кривой.

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

Анализ времени выполнения программы

Чтобы проанализировать время выполнения этой процедуры, вы можете определить число вызовов процедуры Hilbert. При каждой рекурсии она вызывает себя четыре раза. Если T(N) — это число вызовов процедуры, когда она вызывается с глубиной рекурсии N, то:

T(1) = 1
T(N) = 1 + 4 * T(N - 1) для N > 1.

Если раскрыть определение T(N), получим:

T(N) = 1 + 4 * T(N - 1)

= 1 + 4 *(1 + 4 * T(N - 2))

= 1 + 4 + 16 * T(N - 2)

= 1 + 4 + 16 * (1 + 4 * T(N - 3))

= 1 + 4 + 16 + 64 * T(N - 3)

= ...

= 40 + 41 + 42 + 43 + ... + 4K * T(N - K)

Раскрыв это уравнение до тех пор, пока не будет выполнено условие остановки рекурсии T(1)=1, получим:

T(N) = 40 + 41 + 42 + 43 + ... + 4N-1

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



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

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