Правила форума
Лекция №9.4: Рекурсивные подпрограммыСодержание
Пример сравнения рекурсивного и нерекурсивного алгоритма
Реализация нерекурсивного алгоритма
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(0); {принудительное завершение работы программы}
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.
Иллюстрация
Наиболее понятным образом принцип работы нашей программы можно продемонстрировать на примере.
| Вес | 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.
Быстрая сортировка2
Возвратимся теперь к методам сортировки массивов, которым была посвящена лекция 4. Наиболее эффективный способ сортировки остался тогда не рассмотренным по причине того, что самая удобная его реализация подразумевает рекурсию.
Алгоритм Быстр
- Возьмём в сортируемом массиве срединный элемент: x := a[(1 + N) div 2];
- Будем производить следующие действия:
- начав с левого конца массива, будем перебирать его компоненты до тех пор, пока не встретим элемент a[i], больший х;
- начав с правого конца массива, будем перебирать его компоненты до тех пор, пока не встретим элемент a[j], меньший х;
- поменяем местами элементы a[i] и a[j];
до тех пор, пока не произойдёт «рандеву». В результате массив будет разделён на две части. В левой части окажутся все компоненты, меньшие х, а в правой — большие х.
Теперь применим эти же действия к левой и к правой части массива — рекурсивно.
Реализация алгоритма Быстр
var a : array[range1N] of Integer;
procedure quicksort(l, r : range1N);
var i, j : range1N;
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.
Эффективность алгоритма Быстр
Алгоритм Быстрой сортировки имеет в среднем1 сложность N*log N и, следовательно, относится к улучшенным методам сортировки массивов (см. лекцию 4). Кроме того, даже среди улучшенных методов упорядочения Быстрая сортировка даёт наилучшие результаты по времени (для относительно больших входных последовательностей — начиная с N = 100).
Конечно же, существует и итеративный вариант алгоритма Быстрой сортировки, который ещё более эффективен. Мы предлагаем читателям построить его самостоятельно.
Примечания
- ^ Существует, однако, «плохой» случай (и немногочисленные смежные с ним), когда эффективность Быстрой сортировки резко ухудшается до N2. Это происходит, если на каждом шаге срединным оказывается такой элемент, что от массива отделяется всего один элемент (массив длины N распадается на два массива длины N - 1 и 1). Поэтому при описании эффективности мы использовали слова «в среднем».
::
::
::
