Ханойские башни
Перейти к навигации
Перейти к поиску
Ханойская башня решение [1:16]
Ханойские башни — традиционное название вычислительной задачи:
В монастыре монахи уже тысячу лет занимаются перекладыванием колец. Они располагают тремя пирамидами, на которых надеты кольца разных размеров. В начальном состоянии 64 кольца были надеты на первую пирамиду и упорядочены по размеру. Монахи должны переложить все кольца с первой пирамиды на вторую, выполняя единственное условие — кольцо нельзя положить на кольцо меньшего размера. При перекладывании можно использовать все три пирамиды. Монахи перекладывают одно кольцо за одну секунду. Как только они закончат свою работу, наступит конец света.
Рекурсивный вариант решения задачи можно описать так:
Если число дисков равно одному, тогда:
- Передвиньте диск из источника в задание
В противном случае:
- Рекурсивно передвиньте все диски кроме одного из источника в запас, используя задание как запас
- Передвиньте оставшийся диск из источника в задание
- Передвиньте все диски из запаса в задание используя источник как запас
Литература[править]
- Мартин Гарднер, Математические головоломки и развлечения