Алгоритм Быстр
Возьмем в сортируемом массиве срединный элемент: x:=a[(1+N)div 2];Будем производить следующие действия: начав с левого конца массива, будем перебирать его компоненты до тех пор, пока не встретим элемент a[i], больший х;начав с правого конца массива, будем перебирать его компоненты до тех пор, пока не встретим элемент a[j], меньший х;поменяем местами элементы a[i] и a[j];
до тех пор, пока не произойдет "рандеву". В результате массив будет разделен на две части. В левой части окажутся все компоненты, меньшие х, а в правой - большие х.
Теперь применим эти же действия к левой и к правой части массива - рекурсивно.
Алгоритм решения
Будем считать, что цвета задаются целыми положительными числами. В процессе работы программы будем изменять значения пройденных клеток на 0. Кроме того, обрамим исходный массив каймой из нулей, чтобы предотвратить выход за его границы без дополнительных проверок на каждом шагу рекурсии. Теперь массив будет задан не как
array[1..N,1..M] of byte;
а как
array[0..N+1,0..M+1] of byte;
Теперь опишем рекурсивную процедуру, делающую по массиву один "шаг вперед":
Пока в массиве еще остаются не посещенные клетки (их пометка отлична от нуля), мы будем "шагать" на любую из них и проверять оказавшийся "под ногами" цвет.
Если цвет новой клетки не совпадает с цветом предыдущей "посчитанной" клетки, то нам она не нужна. Сделаем шаг назад. Если этот шаг выводит нас из массива наружу, то это означает, что мы просмотрели все клетки одной связной области: пора сравнивать их количество с ранее найденным максимумом.Если клетка помечена тем же номером, что и предыдущая, увеличим счетчик найденных клеток, изменим пометку этой клетки на 0, а затем шагнем снова: поочередно вверх, вниз, влево и вправо (последовательность не принципиальна). Здесь важно понимать, что шагнем мы только в одну сторону, а остальные просто запомним. И лишь после того, как мы вновь возвратимся в эту же клетку, мы "вспомним", что из нее мы еще не пытались уйти туда-то и туда-то, и продолжим этот процесс.
После того как мы посетим все клетки, найденный максимум можно будет объявить итоговым.
Замечание. Рекурсивный алгоритм обхода можно представить в двух вариантах: "посмотрел-шагнул" и "шагнул-посмотрел". Другими словами, в первом случае мы сначала выбираем подходящее место для шага вперед и только потом делаем этот шаг (что очень хорошо сообразуется с правилами передвижения, скажем, по болоту). Во втором же случае мы сначала делаем шаг вперед и только потом проверяем, что же именно оказалось у нас под ногами. Все-таки "ходим" мы не по болоту и в любой момент можем "спастись" из неправильно выбранной клетки.
Дек
Дональд Кнут1) ввел понятие усложненной очереди, которая называется дек (deque - Double-Ended QUEue - двухконцевая очередь). В каждый момент времени у дека доступны как первый, так и последний элемент, причем добавлять и удалять элементы можно и в начале, и в конце дека. Таким образом, дек - это симметричная двусторонняя очередь.
Реализация дека при помощи массива ничем не отличается от реализации обычной очереди, а вот в терминах списков дек удобнее представлять двусвязным (разнонаправленным) линейным списком (см. лекцию 10).
Набор операций для дека аналогичен набору операций для очереди, с той лишь разницей, что добавление и удаление элементов можно производить и в конце, и в начале структуры.
Динамические структуры данных
Динамические структуры данных служат полезным дополнением к стандартным структурам, уже определенным в языке Pascal. Динамическими они называются потому, что их элементы создаются и уничтожаются "на ходу" - в процессе работы программы.
Наиболее понятным образом принцип работы
Наиболее понятным образом принцип работы нашей программы можно продемонстрировать на примере.
| Вес | 25 | 11 | 9 | 5 |
| Количество | 1 | 2 | 2 | 2 |
Пусть имеется семь предметов (n = 7) с весами 9, 5, 25, 11, 9, 5, и 11 единиц (килограмм, фунтов, бушелей...). Тогда всего есть четыре разных вида предметов (k = 4).
Общая сумма весов равна 75; следовательно, "большая половина" sum = 38. Теперь нужно найти такой набор предметов, чей суммарный вес будет наиболее близким к этой "золотой середине". Кроме того, не стоит забывать и о сделанном ранее замечании: как только найдется набор, вес которого отличается от "золотого" лишь на единицу, поиск можно закончить.
Начнем теперь заполнять массивы take и dif (массив dif хранит остатки, в пределах которых можно проводить дальнейшие вычисления).
На начальном ("нулевом") шаге мы заполним массив take так, чтобы в создаваемый набор попали по возможности самые тяжелые предметы (см. раздел реализации "Основная часть программы"). Таким образом, получим следующие состояния массивов:
| ves | - | 25 | 11 | 9 | 5 |
| take | 0 | 1 | 1 | 0 | 0 |
| dif | 38 | 13 | 2 | 0 | 0 |
После этого шага переменная razn, которая хранит отклонение текущего набора весов от оптимального, будет содержать значение 2. Попытаемся уменьшить это значение (переход к разделу реализации "Заполнение массива").
Двигаясь от конца массива take к его началу, будем уменьшать поочередно каждую его ненулевую компоненту. Разумеется, при этом будут возникать изменения в хвосте этого массива; эти изменения мы будем вносить туда в обычной последовательности "от начала к концу".
Таким образом, наши массивы последовательно примут следующие значения (некоторые непринципиальные шаги опущены):
1
| ves | - | 25 | 11 | 9 | 5 |
| take | 0 | 1 | 0 | 1 | 0 |
| dif | 38 | 13 | 13 | 4 | 0 |
2
| ves | - | 25 | 11 | 9 | 5 |
| take | 0 | 1 | 0 | 0 | 2 |
| dif | 38 | 13 | 13 | 13 | 3 |
3
| ves | - | 25 | 11 | 9 | 5 |
| take | 0 | 1 | 0 | 0 | 1 |
| dif | 38 | 13 | 13 | 0 | 8 |
4
| ves | - | 25 | 11 | 9 | 5 |
| take | 0 | 1 | 0 | 0 | 0 |
| dif | 38 | 13 | 13 | 13 | 13 |
5
| ves | - | 25 | 11 | 9 | 5 |
| take | 0 | 0 | 2 | 1 | 1 |
| dif | 38 | 38 | 16 | 7 | 2 |
6
| ves | - | 25 | 11 | 9 | 5 |
| take | 0 | 0 | 2 | 1 | 0 |
| dif | 38 | 38 | 16 | 7 | 7 |
7
| ves | - | 25 | 11 | 9 | 5 |
| take | 0 | 0 | 2 | 0 | 2 |
| dif | 38 | 38 | 16 | 16 | 6 |
10
| ves | - | 25 | 11 | 9 | 5 |
| take | 0 | 0 | 1 | 2 | 1 |
| dif | 38 | 38 | 27 | 9 | 4 |
12
| ves | - | 25 | 11 | 9 | 5 |
| take | 0 | 0 | 1 | 1 | 2 |
| dif | 38 | 38 | 27 | 18 | 8 |
17
| ves | - | 25 | 11 | 9 | 5 |
| take | 0 | 0 | 0 | 2 | 2 |
| dif | 38 | 38 | 38 | 20 | 10 |
22
| ves | - | 25 | 11 | 9 | 5 |
| take | 0 | 0 | 0 | 0 | 2 |
| dif | 38 | 38 | 38 | 38 | 28 |
24
| ves | - | 25 | 11 | 9 | 5 |
| take | 0 | 0 | 0 | 0 | 0 |
| dif | 38 | 38 | 38 | 38 | 38 |
Итак, мы убедились в том, что найденное в самом начале значение переменной razn и было минимальным (найденные группы весов соответственно 25 + 11 = 36 и 11 + 9 + 9 + 5 + 5 = 39). Необходимо отметить, что из приведенных выше таблиц видно (см. шаг 5), что существует еще один способ разделить приведенный набор весов таким же оптимальным образом: (11 + 11 + 9 + 5 = 36 и 25 + 9 + 5 = 39). Найденная разница 39 - 36 = 3 и будет окончательным результатом, который программа сообщит пользователю.
Эффективность
В отличие от рекурсивного алгоритма, верхним пределом для которого можно смело считать наборы длиной в 50 предметов, итеративный алгоритм способен обработать до 5 000 различных весов (общее количество предметов может быть гораздо больше).
Другие примеры сравнения рекурсивных и нерекурсивных алгоритмов, решающих одну и ту же задачу, будут приведены в лекции 12.
Эффективность алгоритма Быстр
Алгоритм Быстрой сортировки имеет в среднем1) сложность N*log N и, следовательно, относится к улучшенным методам сортировки массивов (см. лекцию 4). Кроме того, даже среди улучшенных методов упорядочения Быстрая сортировка дает наилучшие результаты по времени (для относительно больших входных последовательностей - начиная с N = 100).
Конечно же, существует и итеративный вариант алгоритма Быстрой сортировки, который еще более эффективен. Мы предлагаем читателям построить его самостоятельно.
Нерекурсивный алгоритм
Здесь нам потребуется несколько дополнительных рассуждений и линейных массивов.
Основная часть приводимой ниже программы является итеративной реализацией алгоритма полного перебора всех возможных вариантов, удовлетворяющих входным ограничениям. Ее основное отличие от рекурсии - использование малого объема памяти для хранения текущих данных. Вся информация хранится в массивах ves, take и dif. Для вычислений на каждом шаге используется только эта информация. Такой подход позволяет избежать непрерывных перевычислений, которые и являются причиной "тяжеловесности" рекурсивного алгоритма.
Итак, первая часть программы должна заниматься подсчетом и упорядочением вводимых предметов по убыванию их весов. Для экономии места мы не станем приводить подробную реализацию этого блока: здесь годится любой метод сортировки (см. лекцию 4). Важно лишь, что в результате этой сортировки все входные данные будут записаны в два линейных массива длины k (количество разных весов).
Считаем теперь, что массив ves хранит различные веса предметов, упорядоченные по убыванию, а массив kol - количество предметов каждого веса.
Кроме того, в процессе ввода данных производится суммирование весов всех предметов, этот общий вес записывается в переменную sum. Правда, затем эта же переменная будет хранить не весь общий вес, а только его половину (с учетом четности исходной суммы) - для удобства дальнейших сравнений.
Мы не приводим в тексте программы и реализацию функции min() - как не представляющую особенного интереса.
Очередь
Очередью называется динамическая структура, у которой в каждый момент времени доступны два элемента: первый и последний. Из начала очереди элементы можно удалять, а к концу - добавлять. Примером очереди программистcкой вполне может служить очередь обывательская: скажем, в продуктовом магазине.
Последовательность обработки элементов очереди хорошо отражают аббревиатуры LILO (Last In Last Out - "последним вошел, последним вышел") и FIFO (First In First Out - "первым вошел, первым вышел").
Реализовать очередь также можно при помощи массива, хотя здесь уже не удастся полностью избежать перемещения его компонент. Пусть k-я компонента массива хранит начало очереди, а (k+s)-я - ее конец. Тогда можно приписать новый элемент очереди в (k+s+1)-ю компоненту массива, а при удалении элемента из начала очереди ее голова сдвинется в (k+1)-ю компоненту. В процессе работы может оказаться, что вся очередь "сдвинулась" к концу массива, и ее снова нужно вернуть к началу. В этом случае и потребуется s перемещений компонент массива (s - это текущая длина очереди).
Однако наиболее эффективной снова будет реализация при помощи односвязного линейного списка (см. лекцию 10).
Ограничение глубины рекурсии
Теоретически, рекурсия может быть бесконечной. Однако такой вариант вряд ли кого-нибудь устроит: рекурсивный алгоритм, как и любой нерекурсивный его собрат, обязан выдавать результат своей работы за некое обозримое время. Кроме того, память у компьютера не резиновая, в ней может поместиться лишь конечное число контекстов одновременно открытых экземпляров рекурсивной подпрограммы.
Следовательно, каждая рекурсивная подпрограмма должна содержать в себе признак окончания - своеобразный "забор", определяющий максимальную глубину вложенности для этой рекурсии. Признак конца рекурсии может быть как явным (например, в случае реализации факториала), так и неявным (в частности, описанная выше процедура razlozh рано или поздно обязательно закончится, поскольку на каждом шаге происходит уменьшение разлагаемого натурального числа).
Операции
Для стека должны быть определены следующие операции:
| empty(<нач_стека>):boolean | - проверка стека на пустоту; |
| add(<нач_стека>,<новый_элемент>):<нач_стека> | - добавление элемента в стек; |
| take(<нач_стека>):<тип_элементов_стека> | - считывание значения верхнего элемента; |
| del(<нач_стека>):<нач_стека>. | - удаление верхнего элемента из стека. |
Операции
Для очереди должны быть определены следующие операции:
| empty(<нач_очереди>):boolean | - проверка очереди на пустоту; |
| add(<кон_очереди>,<нов_эл-т>):<кон_очереди> | - добавление элемента в конец очереди; |
| take_beg(<нач_очереди>):<тип_эл-тов_очереди> | - считывание значения первого элемента; |
| take_end(<кон_очереди>):<тип_эл-тов_очереди> | - считывание значения последнего элемента; |
| del(<нач_очереди>):<нач_очереди> | - удаление элемента из начала очереди. |
Полный перебор с отсечением
Приведенная выше программа делает много лишней работы. Скажем, незачем продолжать генерирование очередного набора после того, как текущая разность уже превысила ранее найденный минимум. Кроме того, если в некоторый момент времени минимум вдруг окажется равным 1 или 0 (в зависимости от четности входных данных), то дальнейшие усилия также становятся ненужными, поскольку все равно ничего меньшего быть не может.
С учетом этих замечаний можно усовершенствовать текст программы. Мы оставляем эту несложную работу желающим.
Пример рекурсивного алгоритма
Задача. Двумерный массив целых чисел представляет цвета клеток рисунка. Найдите самую большую связную область одного цвета. (Связи по диагонали не учитываются.)
Пример сравнения рекурсивного и нерекурсивного алгоритма
Задача. Двое друзей решили пойти в поход, собрали и взвесили все необходимые вещи. Как им разделить набор предметов на две части наиболее честным образом?
(Имеется набор натуральных чисел, быть может, с повторениями. Необходимо разделить его на два поднабора так, чтобы разность сумм весов была минимальной.)
Реализация алгоритма Быстр
type index = 1..N; var a: array[index] of integer;
procedure quicksort(l,r:index); var i,j: index; x,z: integer; begin i:= l; j:= r; x:= a[(l+r)div 2]; repeat while a[i]< x do inc(i); while a[j]> x do dec(j); if i <= j then begin z:= a[i]; a[i]:= a[j]; a[j]:= z; inc(i); dec(j); end; until i>j; if l<j then quicksort(l,j); if i<r then quicksort(i,r); end; begin {тело программы} ... quicksort(1,n); ... end.
Реализация нерекурсивного алгоритма
program pohod; const nnn = 100; {максимально возможное количество различных весов} var f: text; d,razn,k,i,j,n: integer; sum: longint; ves,kol: array[1..nnn] of word; take, dif: array[0..nnn] of word;
procedure vyvod(a: integer); begin writeln(a); halt; {принудительное завершение работы программы} end;
begin {---- Ввод данных и их сортировка ---} ... {---- Основная часть программы -----} d:= sum mod 2; {показатель четности общего веса} sum:=(sum div 2)+ d; {"большая половина" общего веса}
dif[0]:= sum; razn:= sum; for i:= 1 to k do begin take[i]:= min(dif[i-1] div ves[i],kol[i]); dif[i]:= dif[i-1]- take[i]*ves[i]; if dif[i]< razn then razn:= dif[i]; if razn <= d then vyvod(d); {проверка того, что уже на первом шаге найдено решение} end;
{---- Заполнение массива --------} i:= k; while i>0 do begin if take[i]= 0 then i:= i-1 {переход к следующей компоненте} else begin dec(take[i]); уменьшение текущей компоненты на 1} inc(dif[i],ves[i]); {увеличение остатка на соотв. величину} for j:= i+1 to k do {перезаполнение хвоста} begin take[j]:= min(dif[j-1] div ves[j],kol[j]); dif[j]:= dif[j-1]- take[j]*ves[j]; if dif[j]< razn then razn:= dif[j]; if razn <= d then vyvod(d); {проверка результата} end; i:= k; end; end; vyvod(2*razn-d); end.
Реализация рекурсивного алгоритма
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<min then min:= 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.
Рекурсия
В математике, да и не только в ней одной, часто встречаются объекты, определяемые при помощи самих себя. Они называются рекурсивными.
Например, рекурсивно определяется функция факториал:
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;
Рекурсивный алгоритм
Нужно перебрать все возможные подмножества заданного набора весов. Для решения этой задачи существует несколько классических алгоритмов, мы воспользуемся простейшим, который носит название "полный перебор". В полном соответствии со своим названием, этот алгоритм перебирает все возможные варианты наборов.
Стек
Стеком называется динамическая структура данных, у которой в каждый момент времени доступен только верхний (последний) элемент. Лучше всего понятие стека можно проиллюстрировать примером стопки книг: в стопку можно добавить еще одну книжку, положив ее сверху; из стопки можно взять, не разрушив ее, только верхнюю книгу. А для того, чтобы достать книжку из середины стопки, необходимо сначала убрать по одной все лежащие выше нее.
Последовательность обработки элементов стека хорошо отражают аббревиатуры LIFO (Last In First Out - "последним вошел, первым вышел") и FILO (First In Last Out - "первым вошел, последним вышел").
Реализовать стек можно любым удобным для программиста способом: например, массивом. Тогда началом стека (его "верхним" элементом) будет последний компонент массива, а освобождение стека будет происходить в направлении от конца массива к его началу. При такой реализации нет необходимости в постоянном перемещении компонент массива.
Впрочем, наиболее эффективной все равно будет реализация при помощи односвязного линейного списка, о котором пойдет речь в следующей лекции.
Стековая организация рекурсии
В момент вызова подпрограммы в памяти создается ее контекст: выделяется место под все ее параметры, локальные переменные и константы. Уничтожается этот контекст только после того, как будет достигнут оператор 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
Замена рекурсивных алгоритмов итеративными
Поскольку новый контекст создается каждый раз, когда очередной экземпляр рекурсивной подпрограммы (сам еще оставаясь незавершенным) заново вызывает себя же, то память компьютера расходуется очень быстро. Поэтому рекурсию при всей ее наглядности нельзя отнести к экономичным способам программирования. Существует даже специальная наука - динамическое программирование, изучающая способы замены рекурсивных алгоритмов адекватными итеративными алгоритмами. Мы не станем сейчас углубляться в изложение принципов динамического программирования, а ограничимся лишь примерами превращения рекурсивных программ в нерекурсивные.
Если исполнение подпрограммы приводит только к одному вызову этой же самой подпрограммы, то такая рекурсия называется линейной. Линейную рекурсию довольно легко заменить итеративным алгоритмом. Например, можно реализовать функцию факториала, определенную в начале пункта "Рекурсия", двояко.
| 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; |
Если же каждый экземпляр подпрограммы может вызвать себя несколько раз, то рекурсия называется нелинейной или "ветвящейся". Для того чтобы превратить такую рекурсию в итеративный алгоритм, придется приложить много усилий и, возможно, даже внести некоторые изменения в обрабатываемую структуру данных. Примером "ветвящейся" рекурсии может служить рассмотренная выше процедура разложения числа на сомножители.
