Задача ханойская башня

Сегодня разберём известную задачу Ханойская башня. Подобные задачи способствуют повышению уровня грамотности при написании программ, развивают алгоритмические способности и поднимают общий тонус для участия в экзаменах и олимпиадах по информатике.

Задача: Есть три стержня. На одном из которых нанизаны диски. Диски располагаются в виде пирамидки(ханойской башни): в самом низу лежит самый большой диск, затем идёт чуть поменьше диск, затем ещё меньше диск и т. д. Необходимо переместить диски с одного стержня на другой. Можно использовать все три стержня, но при условии: перекладывать можно только по одному диску за ход, складывать диски можно только меньший на больший.

По легенде, в Великом храме города Бенарас находится бронзовый диск, на котором укреплены 3 алмазных стержня. Давным-давно, в самом начале времён, монахи этого монастыря провинились перед богом Брахмой. Разгневанный, Брахма поместил на один из стержней 64 диска из чистого золота, причем так, что каждый меньший диск лежит на большем. Он сказал монахам перекладывать диски со стержня на стержень по одному, причём запретил класть больший диск на меньший.Как только все 64 диска будут переложены со стержня, на который Брахма сложил их при создании мира, на другой стержень, башня вместе с храмом обратятся в пыль и под громовые раскаты погибнет мир.

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

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

Он заключается в следующем: некоторое утверждение справедливо для всякого натурального n, если оно справедливо для n = 1 и из справедливости утверждения для какого-либо произвольного натурального n = k следует его справедливость для n = k+1.

То есть, доказательство по методу математической индукции проводится в три этапа:

во-первых, проверятся справедливость утверждения для любого натурального числа n (обычно проверку делают для n = 1);
во-вторых, предполагается справедливость утверждения при любом натуральном n=k;
в-третьих, доказывается справедливость утверждения для числа n=k+1, отталкиваясь от предположения второго пункта.

Используем метод математической индукции:

Наша задача точно решается для одного диска. Это очевидно. Просто берём и перемещаем диск с одного стержня на другой.
Пусть мы умеем перекладывать n дисков. Докажем, что тогда и n+1 мы также можем переложить.
Пускай нам надо переложить n+1 дисков на второй стержень. Т.к. мы умеем перекладывать n дисков, то мы эту стопку переложим на третий стержень. Затем, положив самый большой диск на второй стержень, мы воспользуемся тем, что умеем перекладывать стопку из n элементов и переложим эту стопку с третьего стержня на второй. Таким образом, мы доказали, что задача решается для любого числа дисков.

Ещё раз о методе математической индукции. Мы доказали, что для одного диска всё работает отлично. Также мы доказали, что если для n дисков задача решается, то для n+1 тоже будет решаться. Но если вместо n подставить нашу 1, то уже для 2 тоже будет выполняться. В свою очередь 2 "тянет" за собой 3 и т.д. Таким образом, у нас задача будет решаться для любого натурального числа.

Сами наши рассуждения по поводу метода математической индукции нам подсказывают, что здесь можно воспользоваться рекурсией

Рекурсия — вызов функции (процедуры) из неё же самой, непосредственно (простая рекурсия) или через другие функции (сложная или косвенная рекурсия), например, функция A вызывает функцию B, а функция B — функцию A.

Пишем программу:

Программу напишем на C#, т.к. этот язык в большинстве случаев принимается на олимпиадах по информатике. n-Количество дисков, i-номер стержня-источника, p-номер стержня-приёмника, v-вспомогательный стержень. Переменные соответственно i,p,v должны принимать значения от 1 до 3. Переменная n>0. Защита от "дурака" в данной функции не реализована. Если понадобится - реализуете сами. Также, здесь приведена сама функция Hanoy, которая и реализует всю работу. Остальные строки кода консольного приложения C# здесь опущены.

 public static bool Hanoy(int n, byte i, byte p, byte v)
 {
            if (n>0) {
                // Перекладываем сначала стопку из n-1 элементов на вспомогательный стержень.
                // А стержень приёмник играет пока роль вспомогательного.
                Hanoy(n - 1, i, v, p);
                // Перекладываем самый большой диск из стержня-источника на стержень-приёмник.
                Console.WriteLine(i + "->" + p);
                // Перекладываем стопку из n-1 элементов уже на стержень-приёмник.
                // А стержень-источник играет пока роль вспомогательного.
                Hanoy(n - 1, v, p, i);
            }
            return true;
  }

Как мы с вами разобрались, когда размышляли о математической индукции, чтобы переложить n дисков на стержень-приёмник, нам необходимо сначала переложить n-1 дисков на вспомогательный стержень, затем переложить самое большое кольцо на стрежень-приёмник, и повторить действия для n-1 дисков, переместив их из вспомогательного стержня, уже на стержень назначения. Таким образом, наша Ханойская башня из n элементов переместится со стержня источника на стержень-приёмник. Обратите внимание, что функция Hanoy вызывает сама себя, т.е. функцию Hanoy (Это и есть рекурсия!). Это происходит из-за того, что для перемещения Ханойской башни из n элементов, ей необходимо воспользоваться результатом своей же работы для n-1 элементов.

Запускаем нашу функцию Hanoy из функции Main (Для языка C# в консольном приложении) для 3х дисков:

 static void Main(string[] args)
 {
      Hanoy(3, 1, 2, 3);
      Console.ReadKey();
 }

Результат:
1->2
1->3
2->3
1->2
3->1
3->2
1->2

Время работы пропорционально 2ⁿ − 1, где n-количество дисков.

На сегодня всё. Надеюсь, Вам понравилась задача Ханойская башня. Давайте изучать классику Информатики вместе! Если у Вас что-то не получилось, пишите в комментариях. До новых встреч!