Когда будет конец света?

Несколько дней назад мой друг сказал мне:

Конец света и рода человеческого наступит тогда, когда проблему Ханойских башен удастся решить за 64 диска.

Интересный подход и замечательная шутка для описания этой темы. Но на самом деле, что это? в чем смысл этой фразы?

Ну, во-первых, чтобы пролить свет на это, необходимо описать саму проблему Ханоя.

Ханойские башни — это математическая головоломка, в которой у нас есть три стержня ( A , B и C ) и N дисков. Изначально все диски уложены в стопку в порядке убывания диаметра, т.е.самый маленький диск кладется сверху и находится на стержне А. Цель головоломки состоит в том, чтобы переместить всю стопку на другой стержень (здесь рассматривается C ), соблюдая следующие простые правила:

• За один раз можно перемещать только один диск.
• Каждое перемещение состоит из взятия верхнего диска из одной стопки и помещения его поверх другой стопки, т.е. диск можно переместить только в том случае, если он является самым верхним диском в стопке.
• Ни один диск не может быть помещен поверх меньшего диска.

На картинке выше показаны три стержня (A, B, C), которые необходимы для перемещения четырех дисков. Таким образом, мы могли бы сказать, что An — это задача о перемещении всех дисков из A в C, где n — общее количество дисков (в данном случае четыре). Основная идея:

• Возьмите n — 1 диск из A (n — 1 первый диск) и переместите его в B (используя вспомогательные стержни).
• Возьмите оставшийся диск в A и переместите его в C.
• Решить задачу о перемещении n — 1 диска из В (точка 1) в С (с помощью вспомогательных стержней).

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

В конце реальное выражение для решения, сколько шагов необходимо (это может быть хорошим упражнением):

И это доказательство:

Что ж, вернемся к началу этой статьи и воспользуемся следующей формулой:

Просто для того, чтобы представить себе, что если бы мы могли перемещать диски со скоростью 1 диск в секунду, это заняло бы около 584 миллиардов лет, что примерно в 44 раза превышает нынешний возраст Вселенной; так что, следуя идее моего друга, нам не о чем беспокоиться. :)

#ханой #рекурсия #математика #шутка