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

Это может быть связано и с тем, что ограничение рекурсивного алгоритма вычисления чисел Фибоначчи связано с тем, что он вычисляет слишком много промежуточных значений, а не глубиной вложенности рекурсии. Устранение хвостовой рекурсии уменьшает глубину рекурсии, но оно не изменяет время выполнения алгоритма. Даже если бы устранение хвостовой рекурсии было бы применимо к алгоритму вычисления чисел Фибоначчи, этот алгоритм все равно остался бы чрезвычайно медленным.

Проблема этого алгоритма в том, что он многократно вычисляет одни и те же значения. Значения 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 <= 1 Then

        Fib = N

    Else

        Fib_i_minus_2 = 0          ' Вначале Fib(0)

        Fib_i_minus_1 = 1          ' Вначале Fib(1)

        For i = 2 To N

           fib_i = Fib_i_minus_1 + Fib_i_minus_2

           Fib_i_minus_2 = Fib_i_minus_1

           Fib_i_minus_1 = fib_i

        Next i

        Fib = fib_i

    End If

End Function

Этой версии требуется порядка O(N) шагов для вычисления Fib(N). Это больше, чем один шаг, который требовался в предыдущей версии, но намного быстрее, чем O(Fib(N)) шагов в исходной версии алгоритма. На компьютере с процессором Pentium с тактовой частотой 90 МГц, исходному рекурсивному алгоритму потребовалось почти 52 секунды для вычисления Fib(32) = 2.178.309. Время вычисления Fib(1476) » 1,31E+308 при помощи нового алгоритма пренебрежимо мало. Программа Fibo4 использует этот метод для вычисления чисел Фибоначчи.

=====105

Устранение рекурсии в общем случае

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

Некоторые рекурсивные алгоритмы настолько сложны, то применение этих методов затруднено или невозможно. Достаточно сложно было бы написать нерекурсивный алгоритм для построения кривых Гильберта или Серпинского с нуля. Другие рекурсивные алгоритмы более просты.

Ранее было показано, что алгоритм, который рисует кривые Гильберта или Серпинского, должен включать порядка O(N4) шагов, так что исходные рекурсивные версии достаточно хороши. Они достигают почти максимальной возможной производительности при приемлемой глубине рекурсии.

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

Основной подход при этом заключается в том, чтобы рассмотреть порядок выполнения рекурсии на компьютере и затем попытаться сымитировать шаги, выполняемые компьютером. Затем новый алгоритм будет сам осуществлять «рекурсию» вместо того, чтобы всю работу выполнял компьютер.

Поскольку новый алгоритм выполняет практически те же шаги, что и компьютер, можно поинтересоваться, возрастет ли скорость вычислений. В Visual Basic это обычно не выполняется. Компьютер может выполнять задачи, которые требуются при рекурсии, быстрее, чем вы можете их имитировать. Тем не менее, оперирование этими деталями самостоятельно обеспечивает лучший контроль над выделением памяти под локальные переменные, и позволяет избежать глубокого уровня вложенности рекурсии.

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

Рассмотрим следующую обобщенную рекурсивную процедуру:

Sub Subr(num)

    <1 блок кода>

    Subr(<параметры>)

    <2 блок кода>

End Sub

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

=====105

Вначале пометим первые строки в 1 и 2 блоках кода. Затем эти метки будут использоваться для определения места, с которого требуется продолжить выполнение при возврате из «рекурсии». Эти метки используются только для того, чтобы помочь вам понять, что делает алгоритм — они не являются частью кода Visual Basic. В этом примере метки будут выглядеть так:

    Sub Subr(num)

1       <1 блок кода>

        Subr(<параметры>)

2       <2 блок кода>

    End Sub

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

Sub Subr(num)

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

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

    Do

        Select Case pc

           Case 1

               <1 блок кода>

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

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

                   pc = 2

               Else

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

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

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

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

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

                       :

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

                   pc = 1

               End If

           Case 2     ' Выполнить 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

           value = 1

        Else

           Factorial(num - 1, partial)

2          value = num * partial

        End If

    End Sub

После возврата процедуры из рекурсии, требуется узнать исходное значение переменной num, чтобы выполнить операцию умножения value = num * partial. Поскольку процедуре требуется доступ к значению num после возврата из рекурсии, она должна сохранять значение переменных pc и num до начала рекурсии.

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

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, но в других отношениях она имеет такую же структуру и поэтому к ней можно применить те же методы устранения рекурсии.

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33