Comments 9
Классическая задача, но подана реально круто. Особенно понравилось, как ты не просто дал рекурсию, а сделал через объекты и визуализацию сразу видно, что алгоритм не читерит, а честно перекладывает диски. Такой подход на собеседовании точно выделит среди остальных.
Лучшее решение не основано на рекурсии.
Если нечетное число дисков, первым ходом переносим первый (самый маленький) диск на финальный стержень, иначе на вспомогательный. Это единственное место, где надо выбрать ход из двух возможных.
Далее на четных ходах переносим со стержня с не-первым диском на другйо стержень с не-первым диском - там единственный вариант (один меньше, другой больше - переносим меньший на больший).
На нечетных ходах переносим первый диск на стержень, который не был задейтствован два хода назад.
Все.
Отличное уточнение! Тут нужно определиться, что для нас предпочтительнее. Если хочется получить менее громоздкий код - рекурсия будет лучшим решением. Если же важна экономия памяти - лучшим выбором будет предложенный вами итеративный подход, поскольку каждый вызов рекурсивной функции требует памяти в stack frame.
Не только памяти. Можно просто переполнение стека получить, если стержней много и/или количество дисков довольно большое.
Все так! Память в stack frame )
«… Несмотря на то, что число рекурсивных вызовов равно 2Numdiscs-1 , глубина рекурсии не превышает значения NumDiscs. …». «Основные концепции структур данных и реализация на С++» Кен Браунси, Издательский дом «Вильямс», 2002. Конкретно для данной задачи. Хотя в общем случае рекурсия имеет известные «неприятные» моменты.
Головоломка Ханойские башни на Java