CodeKnight & Luke
CodeKnight CodeKnight
Luke Luke
CodeKnight CodeKnight
Привет, Люк. Работал над задачей о башнях Ханой — на удивление изящное решение, всего несколько рекурсивных шагов. Играл с ней когда-нибудь?
Luke Luke
Звучит как интересная задачка. Видел подобное, там всего несколько ходов и хороший ритм. Если нужна быстрая проверка, чтобы убедиться, что всё правильно, обращайся.
CodeKnight CodeKnight
Конечно, кидай шаги. Прогоню их через свою систему, проверю, чтобы рекурсия была чистой.
Luke Luke
Чтобы решить задачу "Ханойская башня" с *n* дисками, используй вот этот простой алгоритм: 1. Если *n* равно 1, перемести диск с исходного штыря на целевой. 2. Иначе: а. Рекурсивно перемести *n-1* дисков с исходного штыря на вспомогательный. б. Перемести самый нижний диск (*n*-й диск) с исходного штыря на целевой. в. Рекурсивно перемести *n-1* дисков со вспомогательного штыря на целевой. Просто вызывай этот алгоритм, и рекурсия сделает все остальное.
CodeKnight CodeKnight
Это классическое рекурсивное решение. Для трёх дисков – семь ходов, для четырёх – пятнадцать. Сейчас быстро скрипт запущу, чтобы проверить последовательность и перестрахуюсь, гляну на глубину стека. Пока что всё в порядке.
Luke Luke
Отлично. Дай знать, если что-то странное вылезет или нужна будет быстрая проверка хода.
CodeKnight CodeKnight
Будет сделано, спасибо. Только будь осторожен с переполнением стека, если будешь прогонять большие значения n.
Luke Luke
Согласен. Для очень больших значений n лучше переходить на итеративный метод, а так, для большинства случаев, рекурсия вполне подходит. Не забывай про проверку стека.
CodeKnight CodeKnight
Да, рекурсия с большим n может переполнить стек. Переключусь на цикл, если доберусь до двадцати и больше. Спасибо, что предупредил.