В основу эффективного решения головоломки «Ханойская башня» положен алгоритм.

gdz-informatika-9-klass-bosova-2021

Задания для практических работ Глава 3. Обработка числовой информации в электронных таблицахГдз по информатике 9 класс по учебнику Босова. Базовый уровень. Обновленные ФГОС 2021 год.


6. В основу эффективного решения головоломки «Ханойская башня» положен алгоритм, суть которого сводится к следующему: для перемещения башни, состоящей из n колец, с первого стержня на третий мы должны решить чуть более простую задачу — переместить на второй стержень башню, состоящую из n – 1 кольца. После этого нижний диск с первого стержня перемещается на третий и повторно осуществляется перемещение башни из n– 1 кольца, но уже со второго диска на третий. Таким образом, число ходов, необходимых для перемещения башни из n колец, равно удвоенному числу ходов, необходимых для перемещения башни из n – 1 кольца, и ещё одному ходу. Используйте эту закономерность для вычисления числа ходов, необходимых для перемещения башни из 64 колец. Вычислите, сколько времени займёт такое перемещение, если считать, что на один ход требуется 1 секунда.

Ответ

Число ходов для перемещения башни Ханойской головоломки из n колец можно выразить рекурсивной формулой:

T(n) = 2T(n-1) + 1

где:

  • ( T(n) ) — число ходов для башни из n колец,
  • ( T(n-1) ) — число ходов для башни из n-1 колец.

Решив данное рекуррентное уравнение, мы можем вычислить число ходов для башни из 64 колец.

T(64) = 2T(63) + 1
T(63) = 2T(62) + 1

T(2) = 2T(1) + 1
T(1) = 1

Решив эти уравнения, получим:

T(64) = 264 — 1

Теперь, если каждый ход занимает 1 секунду, общее время в секундах

будет равно (2^{64} — 1) секунд. Это очень большое число и далеко превосходит человеческое понимание времени. Для оценки в более понятных единицах, преобразуем это время в дни:

В основу эффективного решения головоломки «Ханойская башня» положен алгоритм.

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

Понравилась статья? Поделиться с друзьями: