Task 41. Ханойские башни

Задача: даны три стержня A, B, C, на один из которых нанизаны N колец, причём кольца отличаются размером и лежат меньшее на большем. Задача состоит в том, чтобы перенести пирамиду из N колец за наименьшее число ходов на другой стержень. За один раз разрешается переносить только одно кольцо, причём нельзя класть большее кольцо на меньшее.

Напишите функцию разбора для N колец. Функция должна выводить на экран каждый шаг.

Идея: есть несколько способов решить эту задачу, я сделаю с помощью рекурсии.

Предположим, что существует решение для n-1 колец. Тогда для перекладывания n колец делаем след.шаги:

  1) Перекладываем n-1 кольцо.

  2) Перекладываем n-й кольцо на оставшийся свободным стержень.

  3) Перекладываем стопку из n-1 колец, полученную в пункте (1) поверх n-го кольца.

Поскольку для случая n = 1 алгоритм перекладывания очевиден, то по индукции с помощью выполнения действий (1) – (3) можем переложить произвольное количество колец.

Реализация: напишем рекурсивный метод, на каждом шаге рекурсии будем печатать информацию об одном перекладывании колец.

https://gist.github.com/unilecs/5a4d510d8b39b84fb3a1cb841b3cced4

Тест:

https://dotnetfiddle.net/3cfEwB

P.S. Задача "Ханойские башни" имеет различные подходы к решению. Вы можете ознакомиться с ними на след.ресурсах:

1. Wiki
2. Интересная статья на хабре