Динамические структуры данных
Динамические структуры данных служат полезным дополнением к стандартным структурам, уже определенным в языке Pascal. Динамическими они называются потому, что их элементы создаются и уничтожаются "на ходу" - в процессе работы программы.
Стек
Стеком называется динамическая структура данных, у которой в каждый момент времени доступен только верхний (последний) элемент. Лучше всего понятие стека можно проиллюстрировать примером стопки книг: в стопку можно добавить еще одну книжку, положив ее сверху; из стопки можно взять, не разрушив ее, только верхнюю книгу. А для того, чтобы достать книжку из середины стопки, необходимо сначала убрать по одной все лежащие выше нее.
Последовательность обработки элементов стека хорошо отражают аббревиатуры LIFO (Last In First Out - "последним вошел, первым вышел") и FILO (First In Last Out - "первым вошел, последним вышел").
Реализовать стек можно любым удобным для программиста способом: например, массивом. Тогда началом стека (его "верхним" элементом) будет последний компонент массива, а освобождение стека будет происходить в направлении от конца массива к его началу. При такой реализации нет необходимости в постоянном перемещении компонент массива.
Впрочем, наиболее эффективной все равно будет реализация при помощи односвязного линейного списка, о котором пойдет речь в следующей лекции.
Операции
Для стека должны быть определены следующие операции:
empty(<нач_стека>):boolean
- проверка стека на пустоту;
add(<нач_стека>,<новый_элемент>):<нач_стека>
- добавление элемента в стек;
take(<нач_стека>):<тип_элементов_стека>
- считывание значения верхнего элемента;
del(<нач_стека>):<нач_стека>.
- удаление верхнего элемента из стека.
Очередь
Очередью называется динамическая структура, у которой в каждый момент времени доступны два элемента: первый и последний. Из начала очереди элементы можно удалять, а к концу - добавлять. Примером очереди программистcкой вполне может служить очередь обывательская: скажем, в продуктовом магазине.
Последовательность обработки элементов очереди хорошо отражают аббревиатуры LILO (Last In Last Out - "последним вошел, последним вышел") и FIFO (First In First Out - "первым вошел, первым вышел").
Реализовать очередь также можно при помощи массива, хотя здесь уже не удастся полностью избежать перемещения его компонент. Пусть k-я компонента массива хранит начало очереди, а (k+s)-я - ее конец. Тогда можно приписать новый элемент очереди в (k+s+1)-ю компоненту массива, а при удалении элемента из начала очереди ее голова сдвинется в (k+1)-ю компоненту. В процессе работы может оказаться, что вся очередь "сдвинулась" к концу массива, и ее снова нужно вернуть к началу. В этом случае и потребуется s перемещений компонент массива (s - это текущая длина очереди).
Однако наиболее эффективной снова будет реализация при помощи односвязного линейного списка (см. лекцию 10).
Операции
Для очереди должны быть определены следующие операции:
empty(<нач_очереди>):boolean
- проверка очереди на пустоту;
add(<кон_очереди>,<нов_эл-т>):<кон_очереди>
- добавление элемента в конец очереди;
take_beg(<нач_очереди>):<тип_эл-тов_очереди>
- считывание значения первого элемента;
take_end(<кон_очереди>):<тип_эл-тов_очереди>
- считывание значения последнего элемента;
del(<нач_очереди>):<нач_очереди>
- удаление элемента из начала очереди.
Дек
Дональд Кнут1) ввел понятие усложненной очереди, которая называется дек (deque - Double-Ended QUEue - двухконцевая очередь). В каждый момент времени у дека доступны как первый, так и последний элемент, причем добавлять и удалять элементы можно и в начале, и в конце дека. Таким образом, дек - это симметричная двусторонняя очередь.
Реализация дека при помощи массива ничем не отличается от реализации обычной очереди, а вот в терминах списков дек удобнее представлять двусвязным (разнонаправленным) линейным списком (см. лекцию 10).
Набор операций для дека аналогичен набору операций для очереди, с той лишь разницей, что добавление и удаление элементов можно производить и в конце, и в начале структуры.
Рекурсия
В математике, да и не только в ней одной, часто встречаются объекты, определяемые при помощи самих себя. Они называются рекурсивными.
Например, рекурсивно определяется функция факториал:
0! =1
n! = n*(n-1)!, для любого натурального n.
Другим примером рекурсивного определения может послужить определение арифметического выражения, приведенное в лекции 2.
Рекурсивные подпрограммы
В программировании рекурсивной называется подпрограмма, исполнение которой приводит к ее же повторному вызову.
Если подпрограмма просто вызывает сама себя, то такая рекурсия называется прямой. Например:
procedure rec1(k: byte); function rec2(k: byte): byte;
begin begin
... ...
rec1(k+1); x:= rec2(k+1);
... ...
end; end;
Если же несколько подпрограмм вызывают друг друга, но эти вызовы "замкнуты в кольцо", то такая рекурсия называется косвенной.
В случае косвенной рекурсии возникает проблема с описанием подпрограмм: по правилу языка Pascal, нельзя использовать никакой объект раньше, чем он был описан. Следовательно, невозможно написать в программе:
procedure rec_А(k: byte);
begin
...
reс_В(k+1);
...
end;
procedure rec_В(k: byte);
begin
...
rec_А(k+1);
...
end;
И здесь полезной оказывается возможность отрывать объявление подпрограммы от ее описания (см. лекцию 8). Например, для косвенной рекурсии в случае двух процедур, вызывающих друг друга (rec_A -> rec_B -> rec_A), нужно такое описание:
procedure rec_А(k: byte); forward;
procedure rec_В(k: byte);
begin
...
reс_А(k+1);
...
end;
procedure rec_A;
begin
...
rec_В(k+1);
...
end;
Пример рекурсивного алгоритма
Задача. Двумерный массив целых чисел представляет цвета клеток рисунка. Найдите самую большую связную область одного цвета. (Связи по диагонали не учитываются.)
Алгоритм решения
Будем считать, что цвета задаются целыми положительными числами. В процессе работы программы будем изменять значения пройденных клеток на 0. Кроме того, обрамим исходный массив каймой из нулей, чтобы предотвратить выход за его границы без дополнительных проверок на каждом шагу рекурсии. Теперь массив будет задан не как
array[1..N,1..M] of byte;
а как
array[0..N+1,0..M+1] of byte;
Теперь опишем рекурсивную процедуру, делающую по массиву один "шаг вперед":
Пока в массиве еще остаются не посещенные клетки (их пометка отлична от нуля), мы будем "шагать" на любую из них и проверять оказавшийся "под ногами" цвет.
1. Если цвет новой клетки не совпадает с цветом предыдущей "посчитанной" клетки, то нам она не нужна. Сделаем шаг назад. Если этот шаг выводит нас из массива наружу, то это означает, что мы просмотрели все клетки одной связной области: пора сравнивать их количество с ранее найденным максимумом.
2. Если клетка помечена тем же номером, что и предыдущая, увеличим счетчик найденных клеток, изменим пометку этой клетки на 0, а затем шагнем снова: поочередно вверх, вниз, влево и вправо (последовательность не принципиальна). Здесь важно понимать, что шагнем мы только в одну сторону, а остальные просто запомним. И лишь после того, как мы вновь возвратимся в эту же клетку, мы "вспомним", что из нее мы еще не пытались уйти туда-то и туда-то, и продолжим этот процесс.
После того как мы посетим все клетки, найденный максимум можно будет объявить итоговым.
Замечание. Рекурсивный алгоритм обхода можно представить в двух вариантах: "посмотрел-шагнул" и "шагнул-посмотрел". Другими словами, в первом случае мы сначала выбираем подходящее место для шага вперед и только потом делаем этот шаг (что очень хорошо сообразуется с правилами передвижения, скажем, по болоту). Во втором же случае мы сначала делаем шаг вперед и только потом проверяем, что же именно оказалось у нас под ногами. Все-таки "ходим" мы не по болоту и в любой момент можем "спастись" из неправильно выбранной клетки.
Стековая организация рекурсии
В момент вызова подпрограммы в памяти создается ее контекст: выделяется место под все ее параметры, локальные переменные и константы. Уничтожается этот контекст только после того, как будет достигнут оператор end, закрывающий подпрограмму, либо в ее тексте встретится оператор exit, насильственно прерывающий ее выполнение.
Если некоторая подпрограмма в процессе выполнения вызывает другую подпрограмму, то для вызванной процедуры или функции создается новый отдельный контекст (контекст вызвавшей подпрограммы при этом сохраняется) и т.д. Активным в каждый момент времени является последний контекст. После ликвидации текущего активного контекста активным становится последний "отложенный" контекст - тот, из которого только что закрытый и был вызван.
Таким образом, на внутреннем уровне организован стек контекстов подпрограмм.
Проследим состояние стека контекстов на примере рекурсивной процедуры, решающей задачу разложения натурального числа на сомножители всеми возможными способами (без повторений):
procedure razlozh(k,t:integer; s:string);
var i: integer;
sss: string;
begin
for i:= t to trunc(sqrt(k)) do
if k mod i = 0
then begin
str(i,sss);
razlozh(k div i, i,s+sss+'*');
end;
str(k,sss);
s:=s+sss;
writeln(s);
end;
begin
readln(n);
razlozh(n,2,'');
end.
Для n = 24 стек контекстов этой программы пройдет последовательно такие стадии (значения параметров указаны на моменты вызова процедуры, состояния стека приведены только на моменты времени, предшествующие закрытию очередного контекста):
4
k
3
t
2
s
2*2*2
3
k
6
3
k
6
3
k
4
t
2
t
2
t
3
s
2*2
s
2*2
s
2*3*
2
k
12
2
k
12
2
k
12
2
k
12
2
k
8
2
k
6
t
2
t
2
t
2
t
2
t
3
t
4
s
2*
s
2*
s
2*
s
2*
s
3*
s
4*
1
k
24
1
k
24
1
k
24
1
k
24
1
k
24
1
k
24
1
k
24
t
2
t
2
t
2
t
2
t
2
t
2
t
2
s
s
s
s
s
s
s
Непосредственно перед закрытием самого верхнего контекста происходит печать на консоль. Таким образом, на экране появляются результаты:
2*2*2*3
2*2*6
2*3*4
2*12
3*8
4*6
24
Ограничение глубины рекурсии
Теоретически, рекурсия может быть бесконечной. Однако такой вариант вряд ли кого-нибудь устроит: рекурсивный алгоритм, как и любой нерекурсивный его собрат, обязан выдавать результат своей работы за некое обозримое время. Кроме того, память у компьютера не резиновая, в ней может поместиться лишь конечное число контекстов одновременно открытых экземпляров рекурсивной подпрограммы.
Следовательно, каждая рекурсивная подпрограмма должна содержать в себе признак окончания - своеобразный "забор", определяющий максимальную глубину вложенности для этой рекурсии. Признак конца рекурсии может быть как явным (например, в случае реализации факториала), так и неявным (в частности, описанная выше процедура razlozh рано или поздно обязательно закончится, поскольку на каждом шаге происходит уменьшение разлагаемого натурального числа).
Замена рекурсивных алгоритмов итеративными
Поскольку новый контекст создается каждый раз, когда очередной экземпляр рекурсивной подпрограммы (сам еще оставаясь незавершенным) заново вызывает себя же, то память компьютера расходуется очень быстро. Поэтому рекурсию при всей ее наглядности нельзя отнести к экономичным способам программирования. Существует даже специальная наука - динамическое программирование, изучающая способы замены рекурсивных алгоритмов адекватными итеративными алгоритмами. Мы не станем сейчас углубляться в изложение принципов динамического программирования, а ограничимся лишь примерами превращения рекурсивных программ в нерекурсивные.
Если исполнение подпрограммы приводит только к одному вызову этой же самой подпрограммы, то такая рекурсия называется линейной. Линейную рекурсию довольно легко заменить итеративным алгоритмом. Например, можно реализовать функцию факториала, определенную в начале пункта "Рекурсия", двояко.
Рекурсивная реализация
Итеративная реализация
function fact(k:byte): longint;
var x: longint;
begin
if k = 0
then fact:= 1
else begin x:= fact(k-1)*k;
fact:=x;
end;
end;
fact:= 1
for i:= 2 to k do
fact:= fact * i;
Если же каждый экземпляр подпрограммы может вызвать себя несколько раз, то рекурсия называется нелинейной или "ветвящейся". Для того чтобы превратить такую рекурсию в итеративный алгоритм, придется приложить много усилий и, возможно, даже внести некоторые изменения в обрабатываемую структуру данных. Примером "ветвящейся" рекурсии может служить рассмотренная выше процедура разложения числа на сомножители.
Пример сравнения рекурсивного и нерекурсивного алгоритма
Задача. Двое друзей решили пойти в поход, собрали и взвесили все необходимые вещи. Как им разделить набор предметов на две части наиболее честным образом?
(Имеется набор натуральных чисел, быть может, с повторениями. Необходимо разделить его на два поднабора так, чтобы разность сумм весов была минимальной.)
Рекурсивный алгоритм
Нужно перебрать все возможные подмножества заданного набора весов. Для решения этой задачи существует несколько классических алгоритмов, мы воспользуемся простейшим, который носит название "полный перебор". В полном соответствии со своим названием, этот алгоритм перебирает все возможные варианты наборов.
Реализация рекурсивного алгоритма
program pohod_rec;
var f: text;
a: array[1..100] of integer;
n: integer;
min,obsh_ves: longint;
procedure step(t:byte; ves:longint);
var j: longint;
begin
j:= abs(obsh_ves - 2*ves);
if j
for j:= t+1 to n do step(j,ves+a[t]);
end;
begin
assign(f,'in');
reset(f);
n:=0; {кол-во всех предметов}
obsh_ves:= 0;
while not eof(f) do
begin inc(n);
read(f,a[n]);
inc(obsh_ves,a[n]);
end;
close(f);
min:= MaxLongInt;
step(1,0);
writeln('difference ',min)
end.
Полный перебор с отсечением
Приведенная выше программа делает много лишней работы. Скажем, незачем продолжать генерирование очередного набора после того, как текущая разность уже превысила ранее найденный минимум. Кроме того, если в некоторый момент времени минимум вдруг окажется равным 1 или 0 (в зависимости от четности входных данных), то дальнейшие усилия также становятся ненужными, поскольку все равно ничего меньшего быть не может.
С учетом этих замечаний можно усовершенствовать текст программы. Мы оставляем эту несложную работу желающим.
Нерекурсивный алгоритм
Здесь нам потребуется несколько дополнительных рассуждений и линейных массивов.
Основная часть приводимой ниже программы является итеративной реализацией алгоритма полного перебора всех возможных вариантов, удовлетворяющих входным ограничениям. Ее основное отличие от рекурсии - использование малого объема памяти для хранения текущих данных. Вся информация хранится в массивах ves, take и dif. Для вычислений на каждом шаге используется только эта информация. Такой подход позволяет избежать непрерывных перевычислений, которые и являются причиной "тяжеловесности" рекурсивного алгоритма.
Итак, первая часть программы должна заниматься подсчетом и упорядочением вводимых предметов по убыванию их весов. Для экономии места мы не станем приводить подробную реализацию этого блока: здесь годится любой метод сортировки (см. лекцию 4). Важно лишь, что в результате этой сортировки все входные данные будут записаны в два линейных массива длины k (количество разных весов).
Считаем теперь, что массив ves хранит различные веса предметов, упорядоченные по убыванию, а массив kol - количество предметов каждого веса.
Кроме того, в процессе ввода данных производится суммирование весов всех предметов, этот общий вес записывается в переменную sum. Правда, затем эта же переменная будет хранить не весь общий вес, а только его половину (с учетом четности исходной суммы) - для удобства дальнейших сравнений.
Мы не приводим в тексте программы и реализацию функции min() - как не представляющую особенного интереса.