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




задача и решение, ханойская башня с++Из разделов чистой математики (не углубляясь в деталях) известно, что в форме рекурсивной формулировки может быть выражен любой вычислимый алгоритм. Одной из самых любопытных иллюстраций возможностей и мощи рекурсивных вычислений является задача Ханойская башня.

Утверждается, что эту задачу сформулировали и решают до сих пор монахи каких-то из монастырей Тибета. Задача состоит в том, чтобы пирамидку из колец (на манер детской игрушки), нанизанную на один из 3-х стержней, перенести на другой такой же стержень, придерживаясь строгих правил:

  • пирамидка состоит из N колец разного размера, уложенных по убыванию диаметра колец один на другой;
  • перекладывать за одну операцию можно только одно кольцо с любого штыря на любой …
  • но только при условии, что класть можно только меньшее кольцо сверху на большее, но никак не наоборот;
  • нужно, в итоге, всю исходную пирамидку, лежащую на штыре №1, переместить на штырь №3, используя штырь №2 как промежуточный.

Например, для 2-х колец результат получается такой вот последовательностью перекладываний: 1 => 2 , 1 => 3 , 2 => 3

По преданию, эту задачу по перекладыванию N=10 колечек, решают тибетские монахи, и когда они её, наконец, решат, тогда и наступит конец света … Армагедон, в нашей западной нотации.

Для особо желающих поупражняться, тут же формулируем задачу №2: попробуйте решить эту задачу не рекурсивными методами (это очень непростое занятие)!

А теперь запишем решение задачи:




Решение здесь (если его таковым можно назвать) состоит в том, чтобы при необходимости переноса пирамиды из n колец с штыря с номером from на штырь с номером to последовательно сделать следующее:

  • перенести (каким-то образом) меньшую пирамиду из n-1 колец временно на штырь с номером temp, чтобы не мешала…
  • перенести оставшееся единственное нижнее (наибольшее) кольцо на результирующий штырь с номером to
  • после чего, точно так же как в первом пункте, водрузить пирамиду (n-1 колец) с номера temp поверх этого наибольшего кольца на штырь с номером to.

Здесь важно то, что мы не знаем каким образом, и не умеем выполнить 1-й и 3-й пункт нашей программы, но надеемся, что он будет рекурсивно раскручиваться по аналогии, по тому же алгоритму, но для меньшего числа n-1 (основополагающий принцип рекурсии)… пока n не станет равным 1 — а там уже совсем просто.

И вот как разворачивается решение для различных N:

Можете выполнить эту программу для N=10 (только не спровоцируйте тем конец света!) и убедиться, что число перестановок для этого потребуется 1023. И вообще, для любого N число перестановок будет 2**(N — 1), что представляет собой очень высокую степень роста вычислительной сложности задачи — экспоненциальную.

Рассылка новых уроков по программированию:

Дата
Страница
Задача с решением: Ханойская башня
Рейтинг
51star1star1star1star1star
Olej

Об авторе Olej

Стаж практических программных разработок около 40 лет. Преподаватель международной софтверной компании Global Logic. Постоянный автор публикаций IBM Developer Works. Научный редактор книжного издательства компьютерной литературы "Символ-Плюс", Санкт-Петербург.

Добавить комментарий

Код размещайте в тегах: <pre class="lang:c++ decode:true ">YOUR CODE</pre>