Математическая логика и теория алгоритмов. Стенюшкина В.А. - 84 стр.

       B→A C→B A→C A→C A→B C→B
      (Стрелки означают перемещение диска со стержня с именем, указанным
слева, на диск с именем, указанным справа.)
      Примечание – Ввод достаточно больших чисел требует модификации
программы.
      2 Задача Фибоначчи (1228) «Некто поместил пару кроликов в некоем ме-
сте. Природа кроликов такова, что каждый месяц пара кроликов производит на
свет другую пару, а начинают рождать через 2 месяца после своего рождения.
Сколько пар кроликов будет через 12 месяцев?»
      Эта задача сводится к последовательности чисел 1, 1, 2, 3, 5, 8, 13, 21, …,
при этом каждое следующее число, начиная с третьего, равно сумме двух
предыдущих.
      Программу можно составить с применением рекурсивной функции FIB.
      PROGRAM CROL;
      VAR N, CR:INTEGER; {N - число месяцев, CR – число кроликов}
      FUNCTION FIB(N:INTEGER):INTEGER;
      BEGIN IF (N=1) OR (N-2) THEN FIB:=1 ELSE FIB:=FIB(N-1)+FIB(N-2)
      END;
      BEGIN WRITE (‘Ввод N’);READ(N); CR:=FIB(N);
      WRITE(‘Число пар кроликов =’,CR:5
      END.
      Первый вызов функции происходит в основной программе, а затем выпо-
лняется рекурсивный вызов внутри функции. Пример выполнения программы:
      Ввод N 12
      Число пар кроликов = 233.

       4.6 Жадные алгоритмы

      Жадный алгоритм – это алгоритм, на каждом шаге которого выбирается
оптимум, соответствующий условиям этого шага. Такой локально оптимальный
алгоритм далеко не всегда дает глобальный оптимум. В то же время имеются
классы жадных алгоритмов, дающих глобальный оптимум /5/.
      Пример – Кратчайший путь из А в B имеет длину 16 (АЕВ, например); по
локально оптимальному алгоритму получается длина, равная 30 (ACFDGEB)
(рисунок 4.5).
      Говорят, что к оптимизационной задаче применим принцип жадного вы-
бора, если последовательность локально оптимальных (жадных) выборов дает
глобально оптимальное решение. Дает ли данный алгоритм оптимальное реше-
ние определить не просто. Достаточными условиями являются: жадный выбор
на первом шаге не исключает оптимального решения (то есть возможно продо-
лжение с результатом, не уступающим оптимальному решению), и подзадача,
возникающая после жадного выбора на первом шаге, аналогична исходной.
(Вывод об оптимальности теперь можно сделать по индукции.) Решаемые с по-
мощью жадных алгоритмов задачи обладают (как и в динамическом програм-
мировании) свойством оптимальности для подзадач.