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

Dim X As Single ' Координаты точки.

Dim Y As Single

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

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

Программа Poly на диске содержит связный список многоугольников. Каждый

многоугольник содержит связный список точек. Когда вы закрываете форму,

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

счетчик ссылок на верхнюю ячейку многоугольников до нуля. Она уничтожается,

поэтому ее ссылки на следующий многоугольник и его первую точку также

уничтожаются. Счетчики ссылок на эти ячейки также уменьшаются до нуля, и

они тоже уничтожаются. Уничтожение каждой ячейки многоугольника или точки

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

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

Разреженные массивы

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

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

например, может содержать 1 в позиции A(I, J) если есть рейс между городами

I и J. Многие авиалинии обслуживают сотни городов, но число существующих

рейсов намного меньше, чем N2 возможных комбинаций. На рис. 4.8 показана

небольшая карта рейсов авиалинии, на которой изображены только 11

существующих рейсов из 100 возможных пар сочетаний городов.

@Рис. 4.7. Программа Poly

====73

@Рис. 4.8. Карта рейсов авиалинии

Можно построить матрицу смежности для этого примера при помощи массива 10

на 10 элементов, но этот массив будет по большей части пустым. Можно

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

указатели. Каждая ячейка содержит указатели на следующий элемент в строке и

столбце массива. Это позволяет программе определить положение любого

элемента в массиве и обходить элементы в строке или столбце. В зависимости

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

На рис. 4.9 показана разреженная матрица смежности, соответствующая карте

рейсов с рис. 4.8.

Чтобы построить разреженный массив в Visual Basic, создайте класс для

представления элементов массива. В этом случае, каждая ячейка представляет

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

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

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

также должна содержать указатели на следующую ячейку в строке и столбце.

Следующий код показывает объявление переменных в классе ConnectionCell:

Public FromCity As Integer ' Строка ячейки.

Public ToCity As Integer ' Столбец ячейки.

Public NextInRow As ConnectionCell

Public NextInCol As ConnectionCell

Строки и столбцы в этом массиве по существу представляют собой связные

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

работать, если они содержат сигнальные метки. Например, переменная

RowHead(I) должна содержать сигнальную метку для строки I. Для обхода

строки I в массиве можно использовать следующий код:

Private Sub PrintRow(I As Integer)

Dim cell As ConnectionCell

Set Cell = RowHead(I).Next ' Первый элемент данных.

Do While Not (cell Is Nothing)

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

Set cell = cell.NextInRow

Loop

End Sub

====74

@Рис. 4.9. Разреженная матрица смежности

Индексирование массива

Нормальное индексирование массива типа A(I, J) не будет работать с такими

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

извлекают и устанавливают значения элементов массива. Если массив

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

умножения, и других матричных операций.

Специальное значение NoValue представляет пустой элемент массива.

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

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

Аналогично, процедура, которая устанавливает значения элементов, должна

удалять ячейку из массива, если ее значение установлено в NoValue.

Значение NoValue должно выбираться в зависимости от природы данных

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

значение False. При этом значение A(I, J) может устанавливаться равным

True, если существует рейс между городами I и J.

Класс SparseArray определяет процедуру get для свойства Value для

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

в указанной строке и затем перемещается по связному списку ячеек строки.

Как только найдется ячейка с нужным номером столбца, это и будет искомая

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

может остановиться, если найдется ячейка, номер столбца которой больше

искомого.

=====75

Property Get Value(t As Integer, c As Integer) As Variant

Dim cell As SparseArrayCell

Value = NoValue ' Предположим, что мы не найдем элемент.

If r < 1 Or c < 1 Or _

r > NumRows Or c > NumCols _

Then Exit Property

Set cell = RowHead(r).NextInRow ' Пропустить метку.

Do

If cell Is Nothing Then Exit Property ' Не найден.

If cell.Col > c Then Exit Property ' Не найден.

If cell.Col = c Then Exit Do ' Найден.

Set cell = cell.NextInRow

Loop

Value = cell. Data

End Property

Процедура let свойства value присваивает ячейке новое значение. Если новое

значение равно NoValue, процедура вызывает для удаления элемента из

массива. В противном случае, она ищет требуемое положение элемента в нужной

строке. Если элемент уже существует, процедура обновляет его значение.

Иначе, она создает новый элемент и добавляет его к списку строки. Затем она

добавляет новый элемент в правильное положение в соответствующем списке

столбцов.

Property Let Value (r As Integer, c As Integer, new_value As Variant)

Dim i As Integer

Dim found_it As Boolean

Dim cell As SparseArrayCell

Dim nxt As SparseArrayCell

Dim new_cell As SparseArrayCell

' Если value = MoValue, удалить элемент из массива.

If new_value = NoValue Then

RemoveEntry r, c

Exit Property

End If

' Если нужно, добавить строки.

If r > NumRows Then

ReDim Preserve RowHead(1 To r)

' Инициализировать метку для каждой новой строки.

For i = NumRows + 1 To r

Set RowHead(i) = New SparseArrayCell

Next i

End If

' Если нужно, добавить столбцы.

If c > NumCols Then

ReDim Preserve ColHead(1 To c)

' Инициализировать метку для каждой новой строки.

For i = NumCols + 1 To c

Set ColHead(i) = New SparseArrayCell

Next i

NumCols = c

End If

' Попытка найти элемент.

Set cell = RowHead(r)

Set nxt = cell.NextInRow

Do

If nxt Is Nothing Then Exit Do

If nxt.Col >= c Then Exit Do

Set cell = nxt

Set nxt = cell.NextInRow

Loop

' Проверка, найден ли элемент.

If nxt Is Nothing Then

found_it = False

Else

found_it = (nxt.Col = c)

End If

' Если элемент не найден, создать его.

If Not found_it Then

Set new_cell = New SparseArrayCell

' Поместить элемент в список строки.

Set new_cell.NextInRow = nxt

Set cell.NextInRow = new_cell

' Поместить элемент в список столбца.

Set cell = ColHead(c)

Set nxt = cell.NextInCol

Do

If nxt Is Nothing Then Exit Do

If nxt.Col >= c Then Exit Do

Set cell = nxt

Set nxt = cell.NextInRow

Loop

Set new_cell.NextInCol = nxt

Set cell.NextInCol = new_cell

new_cell.Row = r

new_cell.Col = c

' Поместим значение в элемент nxt.

Set nxt = new_cell

End If

' Установим значение.

nxt.Data = new_value

End Property

Программа Sparse, показанная на рис. 4.10, использует классы SparseArray и

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

можно устанавливать и извлекать элементы массива. В этой программе значение

NoValue равно нулю, поэтому если вы установите значение элемента равным

нулю, программа удалит этот элемент из массива.

Очень разреженные массивы

Некоторые массивы содержат так мало непустых элементов, что многие строки и

столбцы полностью пусты. В этом случае, лучше хранить заголовки строк и

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

полностью пропускать пустые строки и столбцы. Заголовки строки и столбцов

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

показан массив 100 на 100, который содержит всего 7 непустых элементов.

@Рис. 4.10. Программа Sparse

=====76-78

@Рис. 4.11. Очень разреженный массив

Для работы с массивами этого типа можно довольно просто доработать

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

массива можно использовать тот же самый класс SparseArray.Тем не менее,

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

связных списках.

Объекты класса HeaderCell представляют связные списки строк и столбцов. В

этом классе определяются переменные, содержащие число строк и столбцов,

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

элементов строк или столбцов, и объект HeaderCell, представляющий следующий

заголовок строки или столбца.

Public Number As Integer ' Номер строки или столбца.

Public Sentinel As SparseArrayCell ' Метка для строки или

' столбца.

Public NextHeader As HeaderCell ' Следующая строка или

' столбец.

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

список заголовков HeaderCells строк, пока не найдется заголовок,

соответствующий строке I. Затем продолжается работа со строкой I.

Private Sub PrintRow(r As Integer)

Dim row As HeaderCell

Dim cell As SparseArrayCell

' Найти правильный заголовок строки.

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

Глава 5. Рекурсия

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

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

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

операций.

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

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

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

ненужной, а иногда и вредной.

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

Фибоначчи, и наибольшего общего делителя. Все эти алгоритмы являются

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

алгоритмов намного эффективнее. Эти примеры интересны и наглядны, поэтому

имеет смысл обсудить их.

Затем, в главе рассматривается несколько примеров, в которых применение

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

используют рекурсию правильно и эффективно.

В последних разделах этой главы объясняется, почему реализацию

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

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

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

устранения рекурсии, если это необходимо.

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

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

Прямая рекурсия (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 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

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

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