Смекни!
smekni.com

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

=====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 <= 0 Then

Factorial = 1

Else

Factorial = num * Factorial(num - 1)

End If

End Function

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

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