Ханойская башня

Задача про ханойскую башню, применение

1

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

Задача легко решается с помощью рекурсии, рассмотрим подробнее реализацию класса.  В общем виде алгоритм решения задачи выглядит так,  где n – количество колец:

  1. Переместить n – 1 кольцо со стержня 1 на стержень 2, используя стержень 3 для временного перемещения колец.

  2. Переместить последнее кольцо (самое большое) со стержня 1 на стержень 3.

  3. Переместить n-1 кольцо со стержня 2 на стержень 3, используя стержень 1 для временного перемещения колец.

 

 

Следующий код тестирует решение задачи, на строке 12 создается объект класса HanoiTower, в качестве параметра передается число колец, которые необходимо переместить с одного кольца на другое. На строке 15  вызывается рекурсивный метод solveHanoi, который выводит на экран шаги решения задачи.

Результат выполнения программы:

 

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

Ваш e-mail не будет опубликован. Обязательные поля помечены *