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

      WRITELN (A, B);

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

      END

    END;

    Проверим: для N=1 процедура напечатает  1 2

                  для N=2: 1 3

      1 2

3 2

          Для N=3 проверьте работу процедуры самостоятельно.

    Почему  так называется игра? По легенде  где-то недалеко от Ханоя расположена пирамида из 64 золотых колец. Эти кольца перекладывают жрецы храма. Как только они закончат этот процесс, наступит конец света. Можно приблизительно подсчитать, когда это случится. Пусть L(N) – количество перекладок. Тогда при

          N = 1,  L (N) = 1

          N = 2,  L (N) = 3

          N = 3,  L (N) = 3 + 1 + 3 = 7

          …………………

          N = k,  L (N) = 2^k-1.

    Для количества колец N=64 L(N)=2⁶⁴-1. Если одно перекладывание занимает 1 секунду, то 2⁶⁴ секунд ≈ 10¹² лет (около 1 триллиона лет до конца света).

    Существует 2 формы рекурсивных процедур (или  функций):

1. прямая рекурсия,
2. косвенная рекурсия.

    В случае прямой рекурсии процедура содержит вызов этой же процедуры (как в наших примерах).

    В случае косвенной рекурсии процедура  вызывает другую процедуру, которая  сама либо с помощью других процедур, вызывает исходную. Например

          А→В→А.

    Но  тогда возникает проблема: где  и как описать вызываемую процедуру? По правилам языка Паскаль каждый вызываемый модуль (процедура, функция) должен быть описан до его вызова. Но если А вызывает В, а В вызывает А, то получается замкнутый круг. Выходят из положения так: один из модулей, вызывающих друг друга, описывается предварительно следующим образом

          PROCEDURE P (<список формальных параметров>); FORWARD;

    или

          FUNCTION S (<список формальных параметров >):<тип>; FORWARD;

    Здесь FORWARD – ключевое слово (в переводе означает – передний, вперед). Оно указывает транслятору, что текст процедуры Р помещен ниже. При этом список формальных параметров, а также тип результата (для FUNCTION) указываются только в этом предварительном описании, а в заголовке последующего текста – опускаются.

    Пусть при работе функция А вызывает функцию В, а В – функцию  А. Тогда эти модули можно описать так:

    FUNCTION A (X: INTEGER): REAL; FORWARD;

    FUNCTION B (Y: INTEGER): REAL;

    BEGIN

    ……….

    B := A(I)+3.5

    END;

    FUNCTION A;

    BEGIN

    ………

    A:=B(D)-1.8

    END;

    3.3. Преимущества и  недостатки рекурсивного

             описания алгоритма

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

    FUNCTION FACT (N: INTEGER): INTEGER;

    VAR K,I: INTEGER;

    BEGIN

      K:=1;

      FOR I:=1 TO N DO K:=K*I;

      FACT:=K;

    END;

       Рекурсивность – это не свойство  функции, а свойство ее описания. Какое же из описаний лучше?

    В общем случае рекурсивное описание короче и нагляднее, но требует больших  затрат машинного времени (за счет повторных обращений к процедуре) и большей памяти (за счет дублирования локализованных в процедуре переменных). Чему отдать предпочтение – следует решать в конкретном случае.

    Каждый  рекурсивный алгоритм нужно оценивать  с точки зрения времени работы. Если сам алгоритм даже при нерекурсивном описании содержит много действий, то в нем относительное увеличение времени за счет рекурсии будет небольшим.

    Если  в алгоритме мало действий, то доля дополнительных команд может оказаться  слишком большой. Например, в алгоритме для n! рекурсивная процедура гораздо медленнее, поэтому целесообразнее использовать его нерекурсивную форму, а именно – итеративную (рекуррентную).

    Есть  и другие рекурсивные схемы, которые  можно и должно переводить в нерекурсивную, итеративную форму. Пример – вычисление чисел Фибоначчи по рекуррентной последовательности:

    а₀ = 0,

    а₁ = 1,

    ……

    а_n = а_n-1 + а_n-2,  n>1

    При рекурсивном подходе получим  программу

    FUNCTION FIB (N: INTEGER): INTEGER;

    BEGIN

      IF N=0

      THEN FIB:=0

      ELSE

      IF N=1

      THEN FIG:=1

      ELSE FIB:= FIB(N-1)+FIB(N-2)

    END;

    Обращение к функции FIB(N) приводит к рекурсивным вызовам этой процедуры. Найдем глубину рекурсии нашего алгоритма для значения N=5. Тогда получим схему, изображенную на рис. 3.1.

     Из схемы  видно, что при N>1 каждое обращение к FIB ведет к 2-м дальнейшим обращениям, то есть общее число обращений растет почти экспоненциально. Поэтому такая программа плоха и непригодна.

    Итеративная схема вычислений чисел Фибоначчи  введением всего двух вспомогательных  переменных    X = а_i и Y = а_i-1 позволяет избежать повторного вычисления одних и тех же

                                                                значений.

    FUNCTION FIB (N: INTEGER): INTEGER;

    VAR X, Y, Z, I: INTEGER;

    BEGIN

      I:=1;

      X:=1;

      Y:=0;

      WHILE I<N DO

      BEGIN

      Z:=X;

      X:=X+Y;

      Y:=Z;

      I:=I+1

      END;

      FIB:=X

    END;

    Поэтому  вывод можно сделать следующий. Если задача имеет очевидное итеративное решение, то рекурсии следует избегать. Однако это не значит, что от рекурсии нужно избавляться всегда и любой ценой. Для алгоритма Хоара, например, потери во времени на практике являются небольшими. Многие сложные алгоритмы описываются в рекурсивной форме более наглядно, поэтому целесообразно их описывать именно так.

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

1. Что такое  рекурсия?
2. Приведите примеры рекурсивных алгоритмов. Объясните их работу.
3. Что понимают под глубиной рекурсии? Как она вычисляется?
4. В чем состоит различие между прямой и косвенной рекурсией?
5. Как описать процедуры, связанные косвенной рекурсией? Приведите примеры.
6. Каковы достоинства и недостатки рекурсивного описания алгоритма?
7. В каких случаях целесообразно использовать рекурсию?
8. Проанализируйте алгоритм игры «Ханойские башни». Запишите его в форме процедуры.

4. Обработка нечисловых  массивов

    4.1. Упорядочение символьных  данных

    Мы  с вами рассмотрели алгоритмы сортировки для числовых массивов. Не менее интересно применение этих методов и для нечисловых массивов. Таких, например, в которых записаны тексты. Такие массивы (тексты) мы уже умеем выводить. Для того, чтобы хранить тексты, нужно использовать массивы символьных данных (CHAR).

          VAR C: CHAR; (CHARACTER – знак, символ, значок).

    Значениями  такой переменной являются символьные константы: ‘A’, ‘+’, ‘(‘, ‘.’, ‘1’ и т.д.

    Можно записать: 

    С:= ‘(‘;

    или

    IF C=’(‘ THEN < действие>;

    С = ‘(‘ – логическое выражение, значением которого является “истина” или “ложь”.

    Следовательно, символьные значения можно сравнивать, используя операции <, = и т.д.:

    C < ‘O’, C<=’O’ или С<B (В –  тоже переменная типа CHAR).

    Каким образом сравниваются символьные данные? Для выяснения этого вопроса обратимся к их внутреннему представлению. Известно, что все символьные значения перенумерованы и представлены в ЭВМ своими номерами (кодами), то есть целыми числами. Так, например, код символа ‘0’ равен 48 (в кодировке ASCII), код символа ‘  ‘ равен 32 (меньше любого печатного символа).

    Для записи кодов в памяти отводится 8 бит (1 байт). В них могут быть записаны числа:

    0000 0000 = 0,

    0000 0001 = 1,

    0000 0010 = 2,

    ……….…

    1111 1111 = 255 = 2⁸-1

      При сравнении символов сравниваются  их коды. Поэтому

     ‘    ‘ < ‘0’ - “истина”,

    ‘1’   > ‘0’ - “истина”.

    В международной системе кодирования  латинские буквы упорядочены.

    ‘A’ < ‘B’ < ‘C’ < ‘D’ < …< ‘Z’

    48 –57 : 0 ¸ 9

    65 – 90 : A ¸ Z

    97 –122 : a ¸ z

    Отдельно  упорядочиваются коды прописных  и строчных букв.

    Если имеем массив символьных данных

          VAR C1: ARRAY [1..100] OF CHAR;

то присвоив его элементам  некоторые значения, а потом упорядочив их, получим элементы, расставленные в порядке возрастания (убывания) кодов этих символов.

    На  практике часто используют строки символов. Интересен вопрос упорядочения этих строк: ‘ALFA’, ‘ABBA’ – какая из строк должна стоять раньше по алфавиту?

    Используем  принцип лексикографической упорядоченности (он используется в словарях). Формально этот принцип реализуется так:

    два символа строки сравнивают с первой буквы слева направо так, что если очередные буквы равны, то сравнивают следующие по порядку буквы. Если очередная буква первого слова меньше той же буквы во втором слове, то считают, что первое слово меньше второго слова. Следовательно,

                      ‘ABBA’ < ‘ALFA’.

    Если  одно из слов короче, то продолжим сравнение, дополняя короткое слово пробелами. В международной кодировке пробел меньше любой буквы. Поэтому

                      ‘ДОМ’ < ‘ДОМИК’.

    Можно расширить область применения алгоритмов сортировки и поиска на массивы символьных строк. Для этого нужно рассматривать отдельные строки как одномерные массивы:

          VAR S: ARRAY [1..10] OF CHAR;

    Для набора таких строк будем иметь  двумерный массив

          VAR SM: ARRAY [1..1000, 1..10] OF CHAR;

    Тогда нужно сравнивать весь массив S с какой-либо строкой матрицы SM.

    Рассмотрим  алгоритм сравнения двух символьных строк. Пусть С1, С2 – строки из 10 символов. Основой алгоритма является оператор цикла.

    VAR C1, C2: ARRAY [1..10] OF CHAR;

                  I: INTEGER;

    I:=1;

    WHILE I<=10 AND C1[I]=C2[I] DO

    I:=I+1;

    Какое постусловие будет выполняться  после завершения такого цикла? Возможны две ситуации:

1. строки равны между собой и тогда цикл завершится по условию I>10.
2. строки не равны; в этом случае найдется такое 1 ≤ I ≤ 10,  что        С1[I] ¹ C2[I].

    Объединяя обе ситуации в одно постусловие, получим