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

алгоритма. Алгоритм, который уменьшает размер задачи при каждом шаге в 10

раз, вероятно, будет быстрее, чем алгоритм, который уменьшает размер задачи

вдвое через каждые 5 шагов. Тем не менее, оба эти алгоритма имеют время

выполнения порядка O(log(N)).

Алгоритмы порядка O(log(N)) обычно выполняются очень быстро, и алгоритм

нахождения наибольшего общего делителя не является исключением из этого

правила. Например, чтобы найти, что наибольший общий делитель чисел

1.736.751.235 и 2.135.723.523 равен 71, функция вызывается всего 17 раз.

Фактически, алгоритм практически мгновенно вычисляет значения, не

превышающие максимального значения числа в формате long — 2.147.483.647.

Функция Visual Basic Mod не может оперировать значениями, большими этого,

поэтому это практический предел для данной реализации алгоритма.

Программа GCD использует этот алгоритм для рекурсивного вычисления

наибольшего общего делителя. Введите значения для A и B, затем нажмите на

кнопку Go, и программа вычислит наибольший общий делитель этих двух чисел.

Рекурсивное вычисление чисел Фибоначчи

Можно рекурсивно определить числа Фибоначчи (Fibonacci numbers) при помощи

уравнений:

Fib(0) = 0

Fib(1) = 1

Fib(N) = Fib(N - 1) + Fib(N - 2) для N > 1.

Третье уравнение рекурсивно дважды вызывает функцию Fib, один раз с

входным значением N-1, а другой — со значением N-2. Это определяет

необходимость 2 условий остановки рекурсии: Fib(0)=0 и Fib(1)=1. Если

задать только одно из них, рекурсия может оказаться бесконечной. Например,

если задать только Fib(0)=0, то значение Fib(2) могло бы вычисляться

следующим образом:

Fib(2) = Fib(1) + Fib(0)

= [Fib(0) + Fib(-1)] + 0

= 0 + [Fib(-2) + Fib(-3)]

= [Fib(-3) + Fib(-4)] + [Fib(-4) + Fib(-5)]

И т.д.

Это определение чисел Фибоначчи легко преобразовать в рекурсивную

функцию:

Public Function Fib(num As Integer) As Integer

If num 1, то функция рекурсивно вычисляет Fib(N-1) и Fib(N-2), и

завершает работу. При первом вызове функции, условие остановки не

выполняется — оно достигается только в следующих, рекурсивных вызовах.

Полное число выполнения условия остановки для входного значения N,

складывается из числа раз, которое оно выполняется для значения N-1 и числа

раз, которое оно выполнялось для значения N-2. Все это можно записать так:

G(0) = 1

G(1) = 1

G(N) = G(N - 1) + G(N - 2) для N > 1.

Это рекурсивное определение очень похоже на определение чисел Фибоначчи. В

табл. 5.2 приведены некоторые значения функций G(N) и Fib(N). Легко

увидеть, что G(N) = Fib(N+1).

Теперь рассмотрим, сколько раз алгоритм достигает рекурсивного шага. Если

N1, функция достигает этого

шага 1 раз и затем рекурсивно вычисляет Fib(n-1) и Fib(N-2). Пусть H(N) —

число раз, которое алгоритм достигает рекурсивного шага для входа N. Тогда

H(N)=1+H(N-1)+H(N-2). Уравнения, определяющие H(N):

H(0) = 0

H(1) = 0

H(N) = 1 + H(N - 1) + H(N - 2) для N > 1.

В табл. 5.3 показаны некоторые значения для функций Fib(N) и H(N). Можно

увидеть, что H(N)=Fib(N+1)-1.

@Таблица 5.2. Значения чисел Фибоначчи и функции G(N)

======87

@Таблица 5.3. Значения чисел Фибоначчи и функции H(N)

Объединяя результаты для G(N) и H(N), получаем полное время выполнения для

алгоритма:

Время выполнения = G(N) + H(N)

= Fib(N + 1) + Fib(N + 1) - 1

= 2 * Fib(N + 1) - 1

Поскольку Fib(N + 1) >= Fib(N) для всех значений N, то:

Время выполнения >= 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

Это уравнение можно упростить, воспользовавшись соотношением:

X0 + X1 + X2 + X3 + ... + XM = (XM+1 - 1) / (X - 1)

После преобразования, уравнение приводится к виду:

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

= (4N - 1) / 3

=====90

С точностью до постоянных, эта процедура выполняется за время порядка

O(4N). В табл. 5.5 приведены несколько первых значений функции времени

выполнения. Если вы внимательно посмотрите на эти числа, то увидите, что

они соответствуют рекурсивному определению.

Этот алгоритм является типичным примером рекурсивного алгоритма, который

выполняется за время порядка O(CN), где C — некоторая постоянная. При

каждом вызове подпрограммы Hilbert, она увеличивает размерность задачи в 4

раза. В общем случае, если при каждом выполнении некоторого числа шагов

алгоритма размер задачи увеличивается не менее, чем в C раз, то время

выполнения алгоритма будет порядка O(CN).

Это поведение противоположно поведению алгоритма поиска наибольшего общего

делителя. Процедура GCD уменьшает размерность задачи в 2 раза при каждом

втором своем вызове, и поэтому время ее выполнения порядка O(log(N)).

Процедура построения кривых Гильберта увеличивает размер задачи в 4 раза

при каждом своем вызове, поэтому время ее выполнения порядка O(4N).

Функция (4N-1)/3 — это экспоненциальная функция, которая растет очень

быстро. Фактически, она растет настолько быстро, что вы можете

предположить, что это не слишком эффективный алгоритм. В действительности

работа этого алгоритма занимает много времени, но есть две причины, по

которым это не так уж и плохо.

Во-первых, ни один алгоритм для построения кривых Гильберта не может быть

намного быстрее. Кривые Гильберта содержат множество отрезков линий, и

любой рисующий их алгоритм будет требовать достаточно много времени. При

каждом вызове процедуры Hilbert, она рисует три линии. Пусть L(N) —

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

L(N) = 3 * T(N) = 4N - 1, поэтому L(N) также порядка O(4N). Любой алгоритм,

рисующий кривые Гильберта, должен вывести O(4N) линий, выполнив при этом

O(4N) шагов. Существуют другие алгоритмы построения кривых Гильберта, но

они занимают почти столько же времени, сколько и этот алгоритм.

@Таблица 5.5. Число рекурсивных вызовов подпрограммы Hilbert

=====91

Второй факт, который показывает, что этот алгоритм не так уж плох,

заключается в том, что кривые Гильберта 9 порядка содержат так много линий,

что экран большинства компьютерных мониторов при этом оказывается полностью

закрашенным. Это неудивительно, так как эта кривая содержит 262.143

отрезков линий. Это означает, что вам вероятно никогда не понадобится

выводить на экран кривые Гильберта 9 или более высоких порядков. На каком-

то порядке вы столкнетесь с ограничениями языка Visual Basic и вашего

компьютера, но, скорее всего, вы еще раньше будете ограничены максимальным

разрешением экрана.

Программа Hilbert, показанная на рис. 5.4, использует этот рекурсивный

алгоритм для рисования кривых Гильберта. При выполнении программы не

задавайте слишком большую глубину рекурсии (больше 6) до тех пор, пока вы

не определите, насколько быстро выполняется эта программа на вашем

компьютере.

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

Как и кривые Гильберта, кривые Серпинского (Sierpinski curves) — это

самоподобные кривые, которые обычно определяются рекурсивно. На рис. 5.5

показаны кривые Серпинского 1, 2 и 3 порядка.

Алгоритм построения кривых Гильберта использует всего одну подпрограмму для

рисования кривых. Кривые Серпинского проще рисовать, используя четыре

отдельных процедуры, которые работают совместно. Эти процедуры называются

SierpA, SierpB, SierpC и SierpD. Это процедуры с косвенной рекурсией —

каждая процедура вызывает другие, которые затем вызывают первоначальную

процедуру. Они рисуют верхнюю, левую, нижнюю и правую части кривой

Серпинского, соответственно.

На рис. 5.6 показано, как эти процедуры работают совместно, образуя кривую

Серпинского 1 порядка. Подкривые изображены стрелками, чтобы показать

направление, в котором они рисуются. Отрезки, соединяющие четыре подкривые,

нарисованы пунктирными линиями.

@Рис. 5.4. Программа Hilbert

=====92

@Рис. 5.5. Кривые Серпинского

Каждая из четырех основных кривых состоит из диагонального отрезка, затем

вертикального или горизонтального отрезка, и еще одного диагонального

отрезка. Если глубина рекурсии больше единицы, каждая из этих кривых

разбивается на меньшие части. Это осуществляется разбиением каждого из двух

диагональных отрезков на две подкривые.

Например, для разбиения кривой типа A, первый диагональный отрезок

разбивается на кривую типа A, за которой следует кривая типа B. Затем

рисуется без изменений горизонтальный отрезок из исходной кривой типа A.

Наконец, второй диагональный отрезок разбивается на кривую типа D, за

которой следует кривая типа A. На рис. 5.7 показано, как кривая типа A

второго порядка образуется из нескольких кривых 1 порядка. Подкривые

изображены жирными линиями.

На рис. 5.8 показано, как полная кривая Серпинского 2 порядка образуется из

4 подкривых 1 порядка. Каждая из подкривых обведена контурной линией.

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

подкривые (тонкие линии на рис. 5.8), тогда можно будет изобразить

рекурсивные отношения между четырьмя типами кривых так, как это показано на

рис. 5.9.

@Рис. 5.6. Части кривой Серпинского

=====93

@Рис. 5.7. Разбиение кривой типа A

Все процедуры для построения подкривых Серпинского очень похожи, поэтому мы

приводим здесь только одну из них. Соотношения на рис. 5.9 показывают,

какие операции нужно выполнить для рисования кривых различных типов.

Соотношения для кривой типа A реализованы в следующем коде. Вы можете

использовать остальные соотношения, чтобы определить, какие изменения нужно

внести в код для рисования кривых других типов.

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

@Рис. 5.8. Кривые Серпинского, образованные из меньших кривых Серпинского

=====94

@Рис. 5.9. Рекурсивные соотношения между кривыми Серпинского

Кроме процедур, которые рисуют каждую из основных кривых, потребуется еще

процедура, которая по очереди вызывает их все для создания законченной

кривой Серпинского.

Sub Sierpinski (Depth As Integer, Dist As Single)

SierpB Depth, Dist

Line -Step(Dist, Dist)

SierpC Depth, Dist

Line -Step(Dist, -Dist)

SierpD Depth, Dist

Line -Step(-Dist, -Dist)

SierpA Depth, Dist

Line -Step(-Dist, Dist)

End Sub

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

Чтобы проанализировать время выполнения этого алгоритма, необходимо

определить число вызовов для каждой из четырех процедур рисования кривых.

Пусть T(N) — число вызовов любой из четырех основных подпрограмм основной

процедуры Sierpinski при построении кривой порядка N.

Если порядок кривой равен 1, кривая каждого типа рисуется только один раз.

Прибавив сюда основную процедуру, получим T(1) = 5.

При каждом рекурсивном вызове, процедура вызывает саму себя или другие

процедуры четыре раза. Так как эти процедуры практически одинаковые, то

T(N) будет одинаковым, независимо от того, какая процедура вызывается

первой. Это обусловлено тем, что кривые Серпинского симметричны и содержат

одно и то же число кривых разных типов. Рекурсивные уравнения для T(N)

выглядят так:

T(1) = 5

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

Эти уравнения почти совпадают с уравнениями, которые использовались для

оценки времени выполнения алгоритма, рисующего кривые Гильберта.

Единственное отличие состоит в том, что для кривых Гильберта 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

value = value * N

N = N - 1 ' Подготовить аргументы для "рекурсии".

Loop

Factorial = value

End Function

Private Function GCD(ByVal A As Double, ByVal B As Double) As Double

Dim B_Mod_A As Double

B_Mod_A = B Mod A

Do While B_Mod_A <> 0

' Подготовить аргументы для "рекурсии".

B = A

A = B_Mod_A

B_Mod_A = B Mod A

Loop

GCD = A

End Function

Private Function BigAdd(ByVal N As Double) As Double

Dim value As Double

value = 1# ' ' Это будет значением функции.

Do While N > 1

value = value + N

N = N - 1 ' подготовить параметры для "рекурсии".

Loop

BigAdd = value

End Function

=====101

Для алгоритмов вычисления факториала и наибольшего общего делителя

практически не существует разницы между рекурсивной и нерекурсивной

версиями. Обе версии выполняются достаточно быстро, и обе они могут

оперировать задачами большой размерности.

Для функции BigAdd, тем не менее, разница огромна. Рекурсивная версия

приводит к переполнению стека даже для довольно небольших входных значений.

Поскольку нерекурсивная версия не использует стек, она может вычислять

результат для значений N вплоть до 10154. После этого наступит переполнение

для данных типа double. Конечно, выполнение 10154 шагов алгоритма займет

очень много времени, поэтому возможно вы не станете проверять этот факт

сами. Заметим также, что значение этой функции совпадает со значением более

просто вычисляемой функции N * N(N + 1) / 2.

Программы Facto2, GCD2 и BigAdd2 демонстрируют эти нерекурсивные алгоритмы.

Нерекурсивное вычисление чисел Фибоначчи

К сожалению, нерекурсивный алгоритм вычисления чисел Фибоначчи не содержит

только хвостовую рекурсию. Этот алгоритм использует два рекурсивных вызова

для вычисления значения, и второй вызов следует после завершения первого.

Поскольку первый вызов не находится в самом конце функции, то это не

хвостовая рекурсия, и от ее нельзя избавиться, используя прием устранения

хвостовой рекурсии.

Это может быть связано и с тем, что ограничение рекурсивного алгоритма

вычисления чисел Фибоначчи связано с тем, что он вычисляет слишком много

промежуточных значений, а не глубиной вложенности рекурсии. Устранение

хвостовой рекурсии уменьшает глубину рекурсии, но оно не изменяет время

выполнения алгоритма. Даже если бы устранение хвостовой рекурсии было бы

применимо к алгоритму вычисления чисел Фибоначчи, этот алгоритм все равно

остался бы чрезвычайно медленным.

Проблема этого алгоритма в том, что он многократно вычисляет одни и те же

значения. Значения Fib(1) и Fib(0) вычисляются Fib(N + 1) раз, когда

алгоритм вычисляет Fib(N). Для вычисления Fib(29), алгоритм вычисляет одни

и те же значения Fib(0) и Fib(1) 832.040 раз.

Поскольку алгоритм многократно вычисляет одни и те же значения, следует

найти способ избежать повторения вычислений. Простой и конструктивный

способ сделать это — построить таблицу вычисленных значений. Когда

понадобится промежуточное значение, можно будет взять его из таблицы,

вместо того, чтобы вычислять его заново.

=====102

В этом примере можно создать таблицу для хранения значений функции

Фибоначчи Fib(N) для N, не превосходящих 1477. Для N >= 1477 происходит

переполнение переменных типа double, используемых в функции. Следующий код

содержит измененную таким образом функцию, вычисляющую числа Фибоначчи.

Const MAX_FIB = 1476 ' Максимальное значение.

Dim FibValues(0 To MAX_FIB) As Double

Private Function Fib(N As Integer) As Double

' Вычислить значение, если оно не находится в таблице.

If FibValues(N) < 0 Then _

FibValues(M) = Fib(N - 1) + Fib(N - 2)

Fib = FibValues(N)

End Function

При запуске программы, она присваивает каждому элементу в массиве FibValues

значение -1. Затем она присваивает FibValues(0) значение 0, и

FibValues(1) — значение 1. Это условия остановки рекурсии.

При выполнении функции, она проверяет, находится ли уже в массиве значение,

которое ей требуется. Если его там нет, она, как и раньше, рекурсивно

вычисляет это значение и сохраняет его в массиве для дальнейшего

использования.

Программа Fibo2 использует этот метод для вычисления чисел Фибоначчи.

Программа может быстро вычислить Fib(N) для N до 100 или 200. Но если вы

попытаетесь вычислить Fib(1476), то программа выполнит последовательность

рекурсивных вызовов глубиной 1476 уровней, которая вероятно переполнит стек

вашей системы.

Тем не менее, по мере того, как программа вычисляет новые значения, она

заполняет массив FibValues. Значения из массива позволяют функции вычислять

все большие и большие значения без глубокой рекурсии. Например, если

вычислить последовательно Fib(100), Fib(200), Fib(300), и т.д. то, в конце

концов, можно будет заполнить массив значений FibValues и вычислить

максимальное возможно значение Fib(1476).

Процесс медленного заполнения массива FibValues приводит к новому методу

вычисления чисел Фибоначчи. Когда программа инициализирует массив

FibValues, она может заранее вычислить все числа Фибоначчи.

Private Sub InitializeFibValues()

Dim i As Integer

FibValues(0) = 0 ' Инициализация условий остановки.

FibValues(1) = 1

For i = 2 To MAX_FIB

FibValues(i) = FibValues(i - 1) + FibValues(i - 2)

Next i

End Sub

Private Function Fib(N As Integer) As Duble

Fib - FibValues(N)

End Function

=====104

Определенное время в этом алгоритме занимает составление массива с

табличными значениями. Но после того как массив создан, для получения

элемента из массива требуется всего один шаг. Ни процедура инициализации,

ни функция Fib не используют рекурсию, поэтому ни одна из них не приведет к

исчерпанию стекового пространства. Программа Fibo3 демонстрирует этот

подход.

Стоит упомянуть еще один метод вычисления чисел Фибоначчи. Первое

рекурсивное определение функции Фибоначчи использует подход сверху вниз.

Для получения значения Fib(N), алгоритм рекурсивно вычисляет Fib(N - 1) и

Fib(N - 2) и затем складывает их.

Подпрограмма InitializeFibValues, с другой стороны, работает снизу вверх.

Она начинает со значений Fib(0) и Fib(1). Она затем использует меньшие

значения для вычисления больших, до тех пор, пока таблица не заполнится.

Вы можете использовать тот же подход снизу вверх для прямого вычисления

значений функции Фибоначчи каждый раз, когда вам потребуется значение. Этот

метод требует больше времени, чем выборка значений из массива, но не

требует дополнительной памяти для таблицы значений. Это пример

пространственно-временного компромисса. Использование большего объема

памяти для хранения таблицы значений делает выполнение алгоритма более

быстрым.

Private Function Fib(N As Integer) As Double

Dim Fib_i_minus_1 As Double

Dim Fib_i_minus_2 As Double

Dim fib_i As Double

Dim i As Integer

If N

Subr()

End Sub

Поскольку после рекурсивного шага есть еще операторы, вы не можете

использовать устранение хвостовой рекурсии для этого алгоритма.

=====105

Вначале пометим первые строки в 1 и 2 блоках кода. Затем эти метки будут

использоваться для определения места, с которого требуется продолжить

выполнение при возврате из «рекурсии». Эти метки используются только для

того, чтобы помочь вам понять, что делает алгоритм — они не являются частью

кода Visual Basic. В этом примере метки будут выглядеть так:

Sub Subr(num)

1

Subr()

2

End Sub

Используем специальную метку «0» для обозначения конца «рекурсии». Теперь

можно переписать процедуру без использования рекурсии, например, так:

Sub Subr(num)

Dim pc As Integer ' Определяет, где нужно продолжить рекурсию.

pc = 1 ' Начать сначала.

Do

Select Case pc

Case 1

If (достигнуто условие остановки) Then

' Пропустить рекурсию и перейти к блоку 2.

pc = 2

Else

' Сохранить переменные, нужные после рекурсии.

' Сохранить pc = 2. Точка, с которой

продолжится

' выполнение после возврата из "рекурсии".

' Установить переменные, нужные для рекурсии.

' Например, num = num - 1.

:

' Перейти к блоку 1 для начала рекурсии.

pc = 1

End If

Case 2 ' Выполнить 2 блок кода

pc = 0

Case 0

If (это последняя рекурсия) Then Exit Do

' Иначе восстановить pc и другие переменные,

' сохраненные перед рекурсией.

End Select

Loop

End Sub

======106

Переменная pc, которая соответствует счетчику программы, сообщает

процедуре, какой шаг она должна выполнить следующим. Например, при pc = 1,

процедура должна выполнить 1 блок кода.

Когда процедура достигает условия остановки, она не выполняет рекурсию.

Вместо этого, она присваивает pc значение 2, и продолжает выполнение 2

блока кода.

Если процедура не достигла условия остановки, она выполняет «рекурсию». Для

этого она сохраняет значения всех локальных переменных, которые ей

понадобятся позже после завершения «рекурсии». Она также сохраняет значение

pc для участка кода, который она будет выполнять после завершения

«рекурсии». В этом примере следующим выполняется 2 блок кода, поэтому она

сохраняет 2 в качестве следующего значения pc. Самый простой способ

сохранения значений локальных переменных и pc состоит в использовании

стеков, подобных тем, которые описывались в 3 главе.

Реальный пример поможет вам понять эту схему. Рассмотрим слегка измененную

версию функции факториала. В нем переписана только подпрограмма, которая

возвращает свое значение при помощи переменной, а не функции, для упрощения

работы.

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

Dim partial As Integer

1 If num 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 ' Рекурсия.

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15