Лекция №9.4: Рекурсивные подпрограммы

страницы: 1 2 3 4

Содержание

Пример сравнения рекурсивного и нерекурсивного алгоритма

Реализация нерекурсивного алгоритма
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(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.
Иллюстрация

Наиболее понятным образом принцип работы нашей программы можно продемонстрировать на примере.

Вес251195
Количество1222

Пусть имеется семь предметов (n = 7) с весами 9, 5, 25, 11, 9, 5, и 11 единиц (килограмм, фунтов, бушелей...). Тогда всего есть четыре разных вида предметов (k = 4).

Общая сумма весов равна 75; следовательно, «большая половина» sum = 38. Теперь нужно найти такой набор предметов, чей суммарный вес будет наиболее близким к этой «золотой середине». Кроме того, не стоит забывать и о сделанном ранее замечании: как только найдётся набор, вес которого отличается от «золотого» лишь на единицу, поиск можно закончить.

Начнём теперь заполнять массивы take и dif (массив dif хранит остатки, в пределах которых можно проводить дальнейшие вычисления).

На начальном («нулевом») шаге мы заполним массив take так, чтобы в создаваемый набор попали по возможности самые тяжёлые предметы (см. раздел реализации «Основная часть программы»). Таким образом, получим следующие состояния массивов:

ves-251195
take01100
dif3813200

После этого шага переменная razn, которая хранит отклонение текущего набора весов от оптимального, будет содержать значение 2. Попытаемся уменьшить это значение (переход к разделу реализации «Заполнение массива»).

Двигаясь от конца массива take к его началу, будем уменьшать поочередно каждую его ненулевую компоненту. Разумеется, при этом будут возникать изменения в хвосте этого массива; эти изменения мы будем вносить туда в обычной последовательности «от начала к концу».

Таким образом, наши массивы последовательно примут следующие значения (некоторые непринципиальные шаги опущены):

1

ves-251195
take01010
dif38131340

2

ves-251195
take01002
dif381313133

3

ves-251195
take01001
dif38131308

4

ves-251195
take01000
dif3813131313

5

ves-251195
take00211
dif38381672

6

ves-251195
take00210
dif38381677

7

ves-251195
take00202
dif383816166

10

ves-251195
take00121
dif38382794

12

ves-251195
take00112
dif383827188

17

ves-251195
take00022
dif3838382010

22

ves-251195
take00002
dif3838383828

24

ves-251195
take00000
dif3838383838

Итак, мы убедились в том, что найденное в самом начале значение переменной 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. Наиболее эффективный способ сортировки остался тогда не рассмотренным по причине того, что самая удобная его реализация подразумевает рекурсию.

Алгоритм Быстр

  1. Возьмём в сортируемом массиве срединный элемент: x := a[(1 + N) div 2];
  2. Будем производить следующие действия:
    1. начав с левого конца массива, будем перебирать его компоненты до тех пор, пока не встретим элемент a[i], больший х;
    2. начав с правого конца массива, будем перебирать его компоненты до тех пор, пока не встретим элемент a[j], меньший х;
    3. поменяем местами элементы a[i] и a[j];

до тех пор, пока не произойдёт «рандеву». В результате массив будет разделён на две части. В левой части окажутся все компоненты, меньшие х, а в правой — большие х.

Теперь применим эти же действия к левой и к правой части массива — рекурсивно.

Реализация алгоритма Быстр

type range1N = 1 .. N;
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).

Конечно же, существует и итеративный вариант алгоритма Быстрой сортировки, который ещё более эффективен. Мы предлагаем читателям построить его самостоятельно.

страницы: 1 2 3 4

Примечания

  1. ^ Существует, однако, «плохой» случай (и немногочисленные смежные с ним), когда эффективность Быстрой сортировки резко ухудшается до N2. Это происходит, если на каждом шаге срединным оказывается такой элемент, что от массива отделяется всего один элемент (массив длины N распадается на два массива длины N - 1 и 1). Поэтому при описании эффективности мы использовали слова «в среднем».
Тэги: рекурсия
| G+
Код для вставки: :: :: :: ::
Поделиться: // //