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

наименьшей на данный момент стоимостью и цепочки с наибольшей стоимос-
тью, чем удержанный маршрут.
       Для приведённого примера оптимальный маршрут коммивояжера: (а12,
а23, а35, а54, а41) имеет стоимость 56. Маршрут можно записать также в виде:
1→2→3→5→4→1.

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

      Объект называется рекурсивным, если он прямо или косвенно обращается
к себе. Рекурсия является обобщением итерации (повтора). Повтор в языках
программирования организуется с помощью оператор цикла. Рекурсия форми-
руется на основе подпрограммы, вызывающей себя. Первый вызов выполняется
из внешней программной единицы. При этом особое внимание должно уде-
ляться условиям выхода из рекурсии. Рассмотрим несколько задач с примене-
нием рекурсивных алгоритмов /7/.
      1 Ханойские башни Существует легенда: «В храме Бендареса находится
бронзовая плита с тремя алмазными стержнями. На один из стержней бог при
сотворении мира нанизал 64 диска разного диаметра из чистого золота. Наибо-
льший диск лежит на бронзовой плите и с остальными образует пирамиду, су-
жающуюся кверху. Это – башня Брамы. Работая день и ночь, жрецы переносят
диски с одного стержня на другой, следуя законам Брамы:
      1) диски можно перемещать с одного стержня на другой только по одно-
му;
      2) нельзя класть больший диск на меньший:
      3)при переносе дисков с одного стержня на другой можно использовать
промежуточный третий стержень, на котором диски тоже могут находиться то-
же только в виде пирамиды.
      Когда все 64 диска будут перенесены с одного стержня на другой, насту-
пит конец света».
      Рекурсивная программа на языке программирования Turbo Pascal пере-
мещения дисков может выглядеть следующим образом. Здесь N – число дисков,
X, Y, Z – переменные диски, A, B, C – их конкретные имена.
      PROGRAM HANOI; VAR N: INTEGER; X, Y, Z: CHAR;
      PROCEDURE HAN(N: INTEGER; VAR X, Y, Z: CHAR);
      BEGIN IF N>0 THEN
       BEGIN HAN(N-1, X, Z, Y,); WRITELN(X,’→’,Y,’ ’);
      HAN(N-1, Z, Y, X)
       END END;
      BEGIN WRITELN(‘ВВОД N, X, Y, Z’); READ(N, X, Y, Z);
      HAN(N, X, Y, Z); WRITELN
      END.
      В результате запуска программы может получиться:
      ВВОД N, X, Y, Z
      4ABC
      A→C C→B A→C B→A B→C A→C A→B C→B C→A