Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
лекция 9.docx
Скачиваний:
26
Добавлен:
01.05.2015
Размер:
53.5 Кб
Скачать

Реализация нерекурсивного алгоритма

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.

Иллюстрация

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

Вес

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

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

  1. Возьмем в сортируемом массиве срединный элемент: x:=a[(1+N)div 2] ;

  2. Будем производить следующие действия:

    1. начав с левого конца массива, будем перебирать его компоненты до тех пор, пока не встретим элемент a[i], больший х ;

    2. начав с правого конца массива, будем перебирать его компоненты до тех пор, пока не встретим элемент a[j], меньший х ;

    3. поменяем местами элементы a[i] и a[j] ;

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

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

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

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.

Эффективность алгоритма Быстр

Алгоритм Быстрой сортировки имеет в среднем2) сложность N*log N и, следовательно, относится к улучшенным методам сортировки массивов (см. лекцию 4). Кроме того, даже среди улучшенных методов упорядочения Быстрая сортировка дает наилучшие результаты по времени (для относительно больших входных последовательностей - начиная с N = 100 ).

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

  1)   См. Д. Кнут. Искусство программирования для ЭВМ, любое издание. Т.1 Основные алгоритмы.   2)   Существует, однако, "плохой" случай (и немногочисленные смежные с ним), когда эффективность Быстрой сортировки резко ухудшается до N2. Это происходит, если на каждом шаге срединным оказывается такой элемент, что от массива отделяется всего один элемент (массив длины N распадается на два массива длины N-1 и 1 ). Поэтому при описании эффективности мы использовали слова "в среднем".

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]