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

Задача: Ханойская башня
Оцени эту статью




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

Утверждается, что эту задачу сформулировали и решают до сих пор монахи каких-то из монастырей Тибета. Задача состоит в том, чтобы пирамидку из колец (на манер детской игрушки), нанизанную на один из 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), что представляет собой очень высокую степень роста вычислительной сложности задачи — экспоненциальную.

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

Olej

Об авторе Olej

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

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

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