Рекурсивно решить проблему Башни Ханоя в C#

Пример Рекурсивно рисуем двоичное дерево в C# использует рекурсию для рисования ветвей дерева. Хороших примеров рекурсии трудно найти, потому что человеческий мозг обычно мыслит итеративно. Например, если вам нужно нарисовать забор, вы, вероятно, подумаете о том, чтобы начать с одного конца и проложить путь к другому. Вы, вероятно, не считаете, что это условия разделения ограждения на две части и рекурсивные покраски каждого.

Проблема Башни Ханоя имеет хорошее, естественно рекурсивное решение.

Рассмотрим три оранжевые штифты, показанные на рисунке. Цель состоит в том, чтобы переместить кучу зеленых дисков из левого колышка в другой (скажем, средний колышек). Вы можете перемещать только один диск за раз, и вы никогда не сможете разместить большой диск на меньшем диске.

Выяснение того, как это сделать прямо, сложно, но существует простое рекурсивное решение. Сначала рекурсивно перемещайте каждый диск, кроме нижнего, на неиспользуемый привязку (в данном случае правую привязку). Теперь на левом штыре есть только один диск, а на среднем колышке нет дисков, чтобы вы могли переместить оставшийся диск. Теперь рекурсивно переместите другие диски с правого указателя на средний привязку.

Если это слишком запутанно, рассмотрите меньшую проблему только с двумя дисками. Чтобы переместить их слева направо, сначала переместите верхний диск вправо. Затем переместите нижний диск в средний штифт. Наконец, переместите верхний диск в средний колышек. Запустите программу несколько раз, чтобы увидеть, как она работает для большей проблемы. Вы можете отрегулировать константу Delay в коде, чтобы программа работала медленнее или быстрее.

Если это слишком запутанно, рассмотрите меньшую проблему только с двумя дисками. Чтобы переместить их слева направо, сначала переместите верхний диск вправо. Затем переместите нижний диск в средний штифт. Наконец, переместите верхний диск в средний колышек. Запустите программу несколько раз, чтобы увидеть, как она работает для большей проблемы. Вы можете отрегулировать константу Delay в коде, чтобы программа работала медленнее или быстрее.

...

Следующий метод MoveDisks - это ключевая рекурсивная подпрограмма.

MoveDisks принимает параметры, которые сообщают, куда перемещать диски с и до, и какой привязкой он может использовать как «временное» хранилище. Он также принимает параметр, указывающий, сколько дисков нужно перемещать. Чтобы переместить диски, метод рекурсивно вызывает себя, чтобы переместить все, кроме нижнего диска, в привязку «временного хранения», затем перемещает нижний диск и затем перемещает другую обратно из «временного хранилища».

Источник: http://csharphelper.com/blog/2015/08/recursively-solve-the-tower-of-hanoi-problem-in-c/

1 Звезда2 Звезды3 Звезды4 Звезды5 Звезд (Пока оценок нет)

Add a Comment

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