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

    Set row = RowHead. NextHeader  ' Список первой строки.

    Do

        If row Is Nothing Then Exit Sub   ' Такой строки нет.

        If row.Number > r Then Exit Sub   ' Такой строки нет.

        If row.Number = r Then Exit Do    ' Строка найдена.

        Set row = row.NextHeader

Loop

    ' Вывести элементы в строке.

    Set cell = row.Sentinel. NextInRow   ' Первый элемент в строке.

    Do While Not (cell Is Nothing)

        Print Format$(cell.FromCity) & " -> " & Format$(cell.ToCity)

        Set cell = cell.NextInRow

    Loop

End Sub

Резюме

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

=========80

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

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

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

Затем, в главе рассматривается несколько примеров, в которых применение рекурсии более уместно. Алгоритмы построения кривых Гильберта и Серпинского используют рекурсию правильно и эффективно.

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

Что такое рекурсия?

Рекурсия происходит, если функция или подпрограмма вызывает сама себя. Прямая рекурсия (direct recursion) выглядит примерно так:

Function Factorial(num As Long) As Long

    Factorial = num * Factorial(num - 1)

End Function

В случае косвенной рекурсии (indirect recursion) рекурсивная процедура вызывает другую процедуру, которая, в свою очередь, вызывает первую:

Private Sub Ping(num As Integer)

    Pong(num - 1)

End Sub

Private Sub Pong(num As Integer)

    Ping(num / 2)

End Sub

===========81

Рекурсия полезна при решении задач, которые естественным образом разбиваются на несколько подзадач, каждая из которых является более простым случаем исходной задачи. Можно представить дерево на рис. 5.1 в виде «ствола», на котором находятся два дерева меньших размеров. Тогда можно написать рекурсивную процедуру для рисования деревьев:

Private Sub DrawTree()

    Нарисовать "ствол"

    Нарисовать дерево меньшего размера, повернутое на -45 градусов

    Нарисовать дерево меньшего размера, повернутое на 45 градусов

End Sub

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

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

Рекурсивное вычисление факториалов

Факториал числа 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 <= 0 Then

        Factorial = 1

    Else

        Factorial = num * Factorial(num - 1)

    End If

End Function

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

Если входное значение меньше или равно 0, функция возвращает значение 1. В остальных случаях, значение функции равно произведению входного значения на факториал от входного значения, уменьшенного на единицу.

То, что эта рекурсивная функция в конце концов остановится, гарантируется двумя фактами. Во‑первых, при каждом последующем вызове, значение параметра num уменьшается на единицу. Во‑вторых, значение num ограничено снизу нулем. Когда num становится равным 0, функция останавливает рекурсию. Условие, например, в данном случае условие num<=0, называется или условием остановки рекурсии (base case или stopping case).

При каждом вызове подпрограммы, система сохраняет ряд параметров в системном стеке, как описывалось в 3 главе. Так как этот стек играет важную роль, иногда его называют просто стеком. Если рекурсивная функция вызовет себя слишком много раз, она может исчерпать стековое пространство и аварийно завершить работу с ошибкой «Out of stack space».

Число раз, которое функция может вызвать сама себя до того, как использует все стековое пространство, зависит от объема установленной на компьютере памяти и количества данных, помещаемых программой в стек. В одном из тестов, программа исчерпала стековое пространство после 452 рекурсивных вызовов. После изменения рекурсивной функции таким образом, чтобы она определяла 10 локальных переменных при каждом вызове, программа могла вызвать себя только 271 раз.

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

Функции факториала требуется единственный аргумент: число, факториал от которого требуется вычислить. Анализ вычислительной сложности алгоритма обычно исследует зависимость времени выполнения программы как функции от размерности (size) задачи или числа входных значений (number of inputs). Поскольку в данном случае входное значение всего одно, такие расчеты могли бы показаться немного странными.

========83

Поэтому, алгоритмы с единственным входным параметром обычно оцениваются через число битов, необходимых для хранения входного значения, а не число входных значений. В некотором смысле, это и есть размер входа, так как столько бит требуется для того, чтобы записать входное значение. Тем не менее, это не очень наглядный способ представления этой задачи. Кроме того, теоретически компьютер мог бы записать входное значение N в log2(N) бит, но в действительности вероятнее всего N занимает фиксированное число битов. Например, все числа формата long занимают 32 бита.

Поэтому в этой главе алгоритмы этого типа анализируются на основе значения входа, а не его размерности. Если вы хотите переписать результаты в терминах размерности входа, вы можете это сделать, воспользовавшись тем, что N=2M, где М — число битов, необходимое для записи N. Если время выполнения алгоритма порядка O(N2) в терминах входного значения N, то оно составит порядка O((22M)2) = O(22*M) = O((22)M) = O(4M) в терминах размерности входа M.

Функции порядка O(N) растут довольно медленно, поэтому можно ожидать от этого алгоритма хорошей производительности. Так оно и есть. Эта функция приводит к проблемам только при переполнении стека после множества рекурсивных вызовов, или когда значение N! становится слишком большим и не помещается в формат целого числа, вызывая ошибку переполнения.

Так как N! растет очень быстро, переполнение наступает раньше, если только стек не используется интенсивно для других целей. При использовании данных целого типа, переполнение наступает для 8!, поскольку 8! = 40.320, что больше, чем наибольшее целое число 32.767. Для того чтобы программа могла вычислять приближенные значения факториала больших чисел, можно изменить функцию, используя вместо целых чисел значения типа double. Тогда максимальное число, которое сможет вычислить алгоритм, будет равно 170! = 7,257E+306.

Программа Facto демонстрирует рекурсивную функцию факториала. Введите значение и нажмите на кнопку Go, чтобы вычислить его факториал.

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

Наибольшим общим делителем (greatest common divisor, GCD) двух чисел называется наибольшее целое, на которое делятся два числа без остатка. Например, наибольший общий делитель чисел 12 и 9 равен 3. Два числа называются взаимно простыми (relatively prime), если их наибольший общий делитель равен 1.

Математик Эйлер, живший в восемнадцатом веке, обнаружил интересный факт:

Если A нацело делится на B, то GCD(A, B) = A.

Иначе GCD(A, B) = GCD(B Mod A, A).

Этот факт можно использовать для быстрого вычисления наибольшего общего делителя. Например:

GCD(9, 12) = GCD(12 Mod 9, 9)

           = GCD(3, 9)

           = 3

========84

На каждом шаге числа становятся все меньше, так как 1<=B Mod A<A, если A не делится на B нацело. По мере уменьшения аргументов, в конце концов, A примет значение 1. Так как любое число делится на 1 нацело, на этом шаге рекурсия остановится. Таким образом, в какой то момент B разделится на A нацело, и работа процедуры завершится.

Открытие Эйлера закономерным образом приводит к рекурсивному алгоритму вычисления наибольшего общего делителя:

public Function GCD(A As Integer, B As Integer) As Integer

    If B Mod A = 0 Then            ' Делится ли B на A нацело?

        GCD = A                    ' Да. Процедура завершена.

    Else

        GCD = GCD(B Mod A, A)      ' Нет. Рекурсия.

    End If

End Function

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

Чтобы проанализировать время выполнения этого алгоритма, необходимо определить, насколько быстро убывает переменная A. Так как функция останавливается, когда A доходит до значения 1, то скорость уменьшения A дает верхнюю границу оценки времени выполнения алгоритма. Оказывается, при каждом втором вызове функции GCD, параметр A уменьшается, по крайней мере, в 2 раза.

Допустим, A < B. Это условие всегда выполняется при первом вызове функции GCD. Если B Mod A <= A/2, то при следующем вызове функции GCD первый параметр уменьшится, по крайней мере, в 2 раза, и доказательство закончено.

Предположим обратное. Допустим, B Mod A > A / 2. Первым рекурсивным вызовом функции GCD будет GCD(B Mod A, A).

Подстановка в функцию значения B Mod A и A вместо A и B дает следующий рекурсивный вызов GCD(B Mod A, A).

Но мы предположили, что B Mod A > A / 2. Тогда B Mod A разделится на A только один раз, с остатком A – (B Mod A). Так как B Mod A больше, чем A / 2, то A – (B Mod A) должно быть меньше, чем A / 2. Значит, первый параметр второго рекурсивного вызова функции GCD меньше, чем A / 2, что и требовалось доказать.

Предположим теперь, что N — это исходное значение параметра A. После двух вызовов функции GCD, значение параметра A должно уменьшится, по крайней мере, до N / 2. После четырех вызовов, это значение будет не больше, чем (N / 2) / 2 = N / 4. После шести вызовов, значение не будет превосходить (N / 4) / 2 = N / 8. В общем случае, после 2 * K вызовов функции GCD, значение параметра A будет не больше, чем N / 2K.

Поскольку алгоритм должен остановиться, когда значение параметра A дойдет до 1, он может продолжать работу только до тех, пока не выполняется равенство N/2K=1. Это происходит, когда N=2K или когда K=log2(N). Так как алгоритм выполняется за 2*K шагов это означает, что алгоритм остановится не более, чем через 2*log2(N) шагов. С точностью до постоянного множителя, это означает, что алгоритм выполняется за время порядка O(log(N)).

=======85

Этот алгоритм — один из множества рекурсивных алгоритмов, которые выполняются за время порядка O(log(N)). При выполнении фиксированного числа шагов, в данном случае 2, размер задачи уменьшается вдвое. В общем случае, если размер задачи уменьшается, по меньшей мере, в D раз после каждых S шагов, то задача потребует S*logD(N) шагов.

Поскольку при оценке по порядку величины можно игнорировать постоянные множители и основания логарифмов, то любой алгоритм, который выполняется за время S*logD(N), будет алгоритмом порядка O(log(N)). Это не обязательно означает, что этими постоянными можно полностью пренебречь при реализации алгоритма. Алгоритм, который уменьшает размер задачи при каждом шаге в 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 Then

        Fib = num

    Else

        Fib = Fib(num – 1) + Fib(num - 2)

    End If

End Function

=========86

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

Анализ этого алгоритма достаточно сложен. Во‑первых, определим, сколько раз выполняется одно из условий остановки num <=1. Пусть G(N) — количество раз, которое алгоритм достигает условия остановки для входа N. Если N <= 1, то функция достигает условия остановки один раз и не требует рекурсии.

Если N > 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).

Теперь рассмотрим, сколько раз алгоритм достигает рекурсивного шага. Если N<=1, функция не достигает этого шага. При N>1, функция достигает этого шага 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), получим:

Страницы: 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