К Ханойской башне прилагается такая легенда. В одном индийском храме стоит башня из 64 золотых дисков, и монахи, не нарушая правил, переносят диски с места на место. Когда они закончат, наступит конец света.
Сколько же времени на самом деле нужно, чтобы перенести 64 диска?
Минимум 2⁶⁴ − 1 ходов
Для n дисков минимальное число ходов равно 2ⁿ − 1. (Почему, объясняется в статье о минимальном числе ходов.) Для 64 дисков получаем
2⁶⁴ − 1 = 18 446 744 073 709 551 615 ходов.
По-японски это примерно «1845 кэй» (кэй — это 10¹⁶, десять тысяч триллионов), то есть около 18,4 квинтиллиона. Это в 18,45 миллиона раз больше одного триллиона.
Если делать один ход в секунду
Представим, что монах двигает диски без отдыха, по одному ходу в секунду, и ни разу не ошибается. Примем год за 31 557 600 секунд (365,25 суток) и разделим:
18 446 744 073 709 551 615 с ÷ 31 557 600 с ≈ 585 млрд лет.
| Что с чем сравниваем | Сколько лет |
|---|---|
| Перенос 64 дисков, один ход в секунду | около 585 млрд лет |
| С момента рождения Вселенной | около 13,8 млрд лет |
| С момента рождения Земли | около 4,6 млрд лет |
Это примерно в 42 раза больше возраста Вселенной. Даже если легенда правдива, бояться конца света не стоит.
А если считать компьютером
Допустим, ходы просчитывает не человек, а компьютер, который делает миллиард ходов в секунду. Всё равно понадобится
18 446 744 073 709 551 615 ÷ 1 000 000 000 ≈ 18,4 млрд секунд ≈ около 585 лет.
Правило для каждого хода очень простое, но с ростом числа дисков число ходов удваивается снова и снова. Это наглядный пример того, что значит «расти экспоненциально».
Сколько дисков можно пройти руками?
При одном ходе в секунду даже минимальное число ходов занимает вот сколько времени.
| Число дисков | Минимум ходов | При одном ходе в секунду |
|---|---|---|
| 7 | 127 | около 2 минут |
| 10 | 1023 | около 17 минут |
| 15 | 32 767 | около 9 часов |
| 20 | 1 048 575 | около 12 суток |
Чтобы сыграть в перерыве, лучше всего подходит примерно 7 дисков. Именно поэтому в режиме «Классика» приложения «Ханойская башня» их 7.
