=====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
Рекурсия — мощный метод программирования, который позволяет разбить задачу на части все меньшего и меньшего размера до тех пор, пока они не станут настолько малы, что решение этих подзадач сведется к набору простых операций.
После того, как вы приобретете опыт применения рекурсии, вы будете обнаруживать ее повсюду. Многие программисты, недавно овладевшие рекурсией, увлекаются, и начинают применять ее в ситуациях, когда она является ненужной, а иногда и вредной.
В первых разделах этой главы обсуждается вычисление факториалов, чисел Фибоначчи, и наибольшего общего делителя. Все эти алгоритмы являются примерами плохого использования рекурсии — нерекурсивные версии этих алгоритмов намного эффективнее. Эти примеры интересны и наглядны, поэтому имеет смысл обсудить их.
Затем, в главе рассматривается несколько примеров, в которых применение рекурсии более уместно. Алгоритмы построения кривых Гильберта и Серпинского используют рекурсию правильно и эффективно.
В последних разделах этой главы объясняется, почему реализацию алгоритмов вычисления факториалов, чисел Фибоначчи, и наибольшего общего делителя лучше осуществлять без применения рекурсии. В этих параграфах объясняется также, когда следует избегать рекурсии, и приводятся способы устранения рекурсии, если это необходимо.
Рекурсия происходит, если функция или подпрограмма вызывает сама себя. Прямая рекурсия (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. В остальных случаях, значение функции равно произведению входного значения на факториал от входного значения, уменьшенного на единицу.