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

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

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

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

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

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

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

...

//peg stacks. Каждый диск представлен его шириной.
Stack[] PegStack = new Stack[3];

// привязка, в которой в настоящее время хранятся диски.
private int OccupiedPegNum = 0;

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

// Переместите num_disks диски из peg from_peg в peg to_peg.
private void MoveDisks(int from_peg, int to_peg,
    int other_peg, int num_disks)
{
    // Посмотрим, есть ли у нас более одного диска для перемещения.
    if (num_disks > 1)
    {
        // У нас есть несколько дисков для перемещения.
        // Рекурсивно перемещать все остальные, кроме одного диска, в другой.
        MoveDisks(from_peg, other_peg, to_peg, num_disks - 1);
    }

    // Переместите оставшийся диск.
    PegStack[to_peg].Push(PegStack[from_peg].Pop());
    this.Refresh();
    System.Threading.Thread.Sleep(Delay);

    if (num_disks > 1)
    {
        // Рекурсивно перемещать другие диски обратно туда, где они принадлежат.
        MoveDisks(other_peg, to_peg, from_peg, num_disks - 1);
    }
}

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

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

(1 оценок, среднее: 5,00 из 5)