Программирование на ЭВМ

    VAR

      Z: REAL;

      D,C: INTEGER;

    BEGIN

Z:=M[A]; - опорный элемент – №1 в последовательности (или ее части);

 D:=B+1; - временные границы просматриваемой

C:=A; части (сужаются);

WHILE C+1 < D DO^* - пока вся последовательность не просмотрена;

IF M[D-1] > Z - сравнение текущего элемента с опорным (начинаем сравнивать с конца массива);

THEN D:=D-1 - элемент стоит на своем месте, переходим к следующему     элементу;

          ELSE

          BEGIN

M[C]:=M[D-1]; - элемент, больший опорного, заносится в начало последовательности;

          C:=C+1;

M[D-1]:=M[C]; - соответственно элемент из начала последовательности переносится в конец, освобождая место для Z;

          END;

M[C]:=Z; - опорный элемент заносится на свое место;

          IF C>A+1 - в левой части больше 1 элемента;

THEN HOARE (A, C-1, M); -применяем алгоритм к левой части;

          IF C+1<B - в правой части больше 1 элемента;

THEN HOARE (C+1, B, M); -применяем алгоритм к правой части;

    END;

    Пусть исходная последовательность: 

Номер элемента	1	2	3	4	5	6	7	8
Исходная  последовательность	25	98	6	72	7	88	14	51
Процесс ее разделения	14	98	6	72	7	88	98	51
	14	7	6	72	6	88	98	51
	14	7	6	72	72	88	98	51
	14	7	6		72	88	98	51

    Исходные  значения: A=1,  B=8,  Z=25,  D=9,  C=1.

    Оценим  трудоемкость алгоритма в предположении, что на каждом этапе делим с  помощью опорного элемента последовательность на две равные части. 

     Разделение  массива выполняется за число  шагов, равное длине последовательности. 

    Тогда число шагов на этапах:

1. 2 по N / 2    Всего получим m этапов.
2. 4 по N / 2²   2^m ≥ N
3. 8 по N / 2³   m = [log₂ N]

          ……….    

13. N по N / N

    На  каждом этапе суммарное число  сравнений C_i ≤ N. Тогда общее число сравнений C ≤ N log₂ N.

    В этих условиях алгоритм Хоара является оптимальным по быстродействию. Если при делении какая-то часть последовательности окажется больше другой, то количество этапов m > [log₂ N]. Следовательно, трудоемкость алгоритма окажется выше. Экспериментально получено, что средняя величина трудоемкости C_ср = N log₂ N * 1.4.

    Эффективность алгоритма Хоара существенно  зависит от выбора опорного элемента. В ряде случаев алгоритм может оказаться очень плохим. Вероятность плохой ситуации уменьшается, если брать опорный элемент из середины последовательности: Z:= M[(A+B) DIV 2];

    Выбор начального элемента в качестве опорного является неудачным.

    Контрольные вопросы и задания

1. В чем состоит  задача информационного поиска? Каковы ее разновидности?
2. Запишите алгоритм отыскания минимального элемента и его номера в последовательности с различными и повторяющимися элементами.
3. Запишите алгоритмы отыскания элемента с заданным значением в неупорядоченной и упорядоченной последовательностях.
4. В чем состоит задача сортировки?
5. Чем отличается сортировка в массивах от сортировки в файлах?
6. Что такое устойчивая сортировка?
7. Назовите основные разновидности методов сортировки в массивах.
8. На чем основан метод сортировки простым выбором? Запишите алгоритм, реализующий этот метод.
9. Какова идея метода простого обмена? Запишите его алгоритм.
10. Поясните смысл метода простых ставок. Запишите алгоритм сортировки этим методом.
11. Как оценить трудоемкость методов сортировки?
12. Что представляет собой метод сортировки Шелла?
13. Оформите алгоритм Шелла в виде процедуры.
14. В чем состоит идея метода сортировки Хоара?
15. Составьте процедуру, реализующую алгоритм Хоара.

3. Рекурсивные алгоритмы

    3.1. Понятие рекурсии

    Объект  называется рекурсивным, если он содержит сам себя или определен с помощью самого себя.

    С понятием рекурсии мы уже встречались  при рассмотрении алгоритма Хоара. Вообще это понятие относится не только к алгоритмам. В жизни возникают рекурсивные изображения (в зеркале, на телеэкране). При описании синтаксиса какого-либо языка часто используются металингвистические формулы (Бэкуса нормальные формы), например:

          <цифра> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |,

          <буква>  ::= A| B | …| Z,

          <целое число без знака> ::= <цифра> | <целая часть><цифра>,

          <идентификатор> ::= <буква> | <идентификатор><буква> | <идентификатор><цифра>.

    Две последние формулы рекурсивны.

    Рекурсивным может быть и определение функции. Так, например, факториал: f(n) = n! Одним из способов определения такой функции является рекурсивный способ:

      

    n! =

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

             и косвенная рекурсии

    Язык  Паскаль позволяет создавать процедуры и функции, обладающие свойством рекурсивности, то есть содержащие в своем описании вызов самих себя. Так для вычисления n! мы можем составить такое рекурсивное описание функции.

    Пример 1.

    FUNCTION FACT (N: INTEGER): INTEGER;

    BEGIN

      IF N=0

      THEN FACT:=1

      ELSE FACT:=N*FACT(N-1)

    END;

    Пример 2.Выдать на печать в обратном порядке цифры целого положительного числа N.

    PROCEDURE REVERSE (N: INTEGER);

    BEGIN

      WRITE (N MOD 10);

      IF (N DIV 10) 0

      THEN REVERSE (N DIV 10)

    END;

    Проанализируем  работу  программы. Пусть N=153. Тогда печатаем число 3 и проверяем на равенство нулю целой части деления:

    целая часть 153/10 равна 15, снова обращаемся к REVERSE, печатаем 5,

    целая часть 15/10 равна 1, снова обращаемся  к REVERSE, печатаем 1.

    Таким образом, однократное обращение извне к процедуре REVERSE вызвало троекратное ее срабатывание. Условие полного окончания работы должно содержаться в самой процедуре. Иначе произойдет зацикливание.

    Посмотрим теперь, как происходит процесс вычисления при рекурсивном описании алгоритма в примере 1.

    Пусть в основной программе происходит вызов функции FACT (3). Тогда при входе в процедуру-функцию в употребление вводится некоторая локальная переменная N, соответствующая этому параметру-значению, после чего выполняются операторы процедуры. Так как здесь N=3, то выполняется оператор

          FACT:= 3*FACT (2).

    В процессе выполнения этого оператора  мы снова обращаемся к функции FACT для вычисления FACT(2). При этом снова вводится в употребление локальная переменная, соответствующая этому параметру-значению. Но это уже другая переменная, например, N1. Ей присваивается значение N1=2 и так как N1≠0, то выполняется оператор

          FACT:= 2*FACT (1).

    При его выполнении для вычисления FACT(1) снова требуется обращение к функции FACT, что требует введения новой локальной переменной N2 со значением N2=1, и выполнится оператор

          FACT:= 1*FACT (0).

    При этом каждый раз завершение вычисления выражения в правой части оператора  присваивания откладывается. При очередном  обращении к процедуре-функции получим N3=0, и в теле процедуры выполняется оператор FACT:=1.

    После этого завершится выполнение оператора  FACT:= 1*FACT (0), то есть получим FACT(1)=1.

    После этого завершится выполнение оператора  FACT:= 2*FACT (1), что даст нам FACT(2)=2, и, наконец, закончится вычисление FACT:= 3*FACT (2), что даст FACT(3)=6.

    Таким образом, в момент рекурсивного вызова мы как бы запомнили состояние алгоритма в момент исходного вызова (сфотографировали). Это нужно, чтобы после завершения рекурсивного вызова продолжить выполнение алгоритма от первичного вызова. Это запоминание делается автоматически, но следует об этом знать. При каждом вторичном вызове рекурсивной процедуры требуется память для запоминания внутренних переменных.

    Сколько может быть вторичных вызовов  до первого завершения самого последнего вызова? Количество повторных вызовов  называют глубиной рекурсии –  это важная характеристика алгоритма.

    Попытайтесь самостоятельно подсчитать глубину  рекурсии для алгоритма Хоара в наиболее благоприятном и наименее благоприятном случаях.

    Пример 3.

     Интересный  пример рекурсии – игра “ханойские башни”. Здесь применение рекурсии очень уместно.

    Имеется 3 стержня и N дисков разного размера.

    Пусть вначале все диски находятся  на стержне А в порядке убывания размера.

    Задача  состоит в том, чтобы переместить диски на стержень В в том же порядке.

    Правила перемещения.

1. На каждом шаге только один диск (верхний) перемещается с одного стержня на другой.
2. Диск большего размера нельзя помещать на меньший диск.
3. Стержень С можно использовать как промежуточный.

    Пусть N=1. Тогда единственная перекладка: А→В.

               N=2:  А→С,

                А→В,

                С→В.

              N=3:  A→В,

            А→С,

          В→С,

          А→В,

          С→А,

          С→В,

          А→В.

    При большем N записать последовательность перекладок уже сложно.

    Для составления алгоритма рассуждаем следующим образом (по методу математической индукции).

1. При N=1 перекладка очевидна (А→В).
2. При N>1. Допустим, что умеем перекладывать N-1 колец правильным образом. Тогда нужно переложить N-1 кольцо с А на С, затем одно с А на В, а затем всю пирамиду с С на В (диск A освободился). В свою очередь, чтобы переложить N-1 кольцо, надо научиться перекладывать N-2 и так далее до 1.

    Отсюда  непосредственно получим рекурсивную  процедуру, в которой основной оператор 
 

    

    WRITE (A, B);  перекладывать 

    PROCEDURE HANOY (N, A, B, C: INTEGER);

    BEGIN

      IF N=1

      THEN WRITELN (A, B);

      ELSE

      BEGIN

      HANOY (N-1, A, C, B);