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

Ответ

Это разновидность задачи динамического программирования, и её относительно просто и удобно реализовать с помощью рекурсии.

Для задачи «переместить moveSum дисков со стержня from на стержень to (используя стержень by)» мы можем выполнить её в следующие три шага:

• Переместите верхние moveSum-1 дисков со стержня from на стержень by (используя стержень to)
• Переместите оставшийся 1 диск со стержня from непосредственно на стержень to
• Переместите moveSum-1 дисков со стержня by на стержень to (используя стержень from)

Процесс выполнения выглядит следующим образом:

Исходная ссылка: https://blog.51cto.com/myunix/2399892