Практикум по курсу "Алгоритмизация и программирование". Часть 2. Андрианова А.А - 44 стр.

А.А. Андрианова, Л.Н. Исмагилов, Т.М. Мухтарова                        .
лет занимаются перекладыванием колец. Они располагают тремя стержнями,
на которых надеты кольца разных размеров, образующих пирамиды. В на-
чальном состоянии 64 кольца были надеты на первую пирамиду и упорядоче-
ны по размеру.
     Монахи должны переложить все кольца с первой пирамиды на вторую,
выполняя единственное условие – кольцо нельзя положить на кольцо меньше-
го размера. При перекладывании можно использовать все три пирамиды.
     Монахи перекладывают одно кольцо за одну секунду. Как только они за-
кончат свою работу, наступит конец света.
     Количество перекладываний в зависимости от количества колец вычисля-
ется по формуле 2n - 1. Для 64-х колец это 18 446 744 073 709 551 615 перекла-
дываний, и, если принять скорость «одно перекладывание в секунду», полу-
чится около 584 942 417 355 лет, то есть апокалипсис наступит нескоро.
     Сформулируем условие задачи. Дано три стержня a, b, с. На одном нани-
зана пирамида из n колец разного радиуса. Требуется перенести всю пирами-
ду на другой стержень, используя в качестве вспомогательного стержня тре-
тий.
     Если требуется перенести пирамиду, состоящую из одного кольца, то пе-
чатается сообщение о переносе этого кольца на нужный стержень.
     На рис. 2.6 показана ситуация переноса пирамиды из n колец (n>1) (рис.
2.6 а – исходное состояние). Для такого переноса требуется сначала перене-
сти пирамиду размера n-1 на вспомогательный стержень (рис. 2.6 б). Далее
перенести оставшееся кольцо на нужный стержень (рис. 2.6 в), и затем пере-
нести пирамиду из n-1 кольца со вспомогательного стержня на нужный (рис.
2.6 г). Этот алгоритм реализаван в функции HanoiTower, которая имеет сле-
дующие параметры: первый параметр – номер стержня-источника, второй па-
раметр – номер стержня назначения, третий параметр – вспомогательный
стержень, четвертый параметр – количество колец в пирамиде.

    # include 

    // прототип функции решения задачи о Ханойской башне
    void HanoiTower(int a, int b, int c, int n);

    void main(void)
    {
          int n;
          int a,b,c;
          printf("Введите количество колец:");
          scanf("%d",&n);

                                            44