Ханойская башня: рекурсивный алгоритм

Question

Хотя у меня нет никаких проблем с пониманием рекурсии, я, похоже, не могу обернуться вокруг рекурсивного решения проблемы Ханойской башни. Вот код из Википедии :

procedure Hanoi(n: integer; source, dest, by: char);
Begin
    if (n=1) then
        writeln('Move the plate from ', source, ' to ', dest)
    else begin
        Hanoi(n-1, source, by, dest);
        writeln('Move the plate from ', source, ' to ', dest);
        Hanoi(n-1, by, dest, source);
    end;
End;

Я понимаю базовый случай и концепцию разбиения проблемы на более мелкие части, пока вы не сможете переместить один диск. Однако я не могу понять, как два рекурсивных вызова в неосновном случае работают вместе. Возможно, кто-то может мне помочь? Спасибо.

Answer 1

Как предложили некоторые из наших друзей, я удалил два предыдущих ответа и собрал их здесь.

Это дает вам ясное понимание.

Что такое общий алгоритм ....

Алгоритм:

solve(n,s,i,d) //solve n discs from s to d, s-source i-intermediate d-destination
{
    if(n==0)return;
    solve(n-1,s,d,i); // solve n-1 discs from s to i Note:recursive call, not just move
    move from s to d; // after moving n-1 discs from s to d, a left disc in s is moved to d
    solve(n-1,i,s,d); // we have left n-1 disc in 'i', so bringing it to from i to d (recursive call)
}

вот рабочий пример Нажмите здесь

Answer 2

Первый рекурсивный вызов перемещает все части, кроме самой большой, из источника в, используя dest в качестве вспомогательной стопки. Когда все будет готово, все части, кроме самой большой, будут лежать, а самая большая будет бесплатной. Теперь вы можете переместить самую большую в dest и использовать другой рекурсивный вызов, чтобы переместить все фигуры из by в dest.

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

Answer 3

Ответ на вопрос, откуда программа узнает, что четное значение равно «src» - «aux», а нечетное - «src» - «dst» для открытия хода лежит в программе. Если вы сломаете кулачный ход с 4 дисками, то это будет выглядеть так:

hanoi(4, "src", "aux", "dst");
if (disc > 0) {
    hanoi(3, 'src', 'dst', 'aux');
        if (disc > 0) {
            hanoi(2, 'src', 'aux', 'dst');
                if (disc > 0) {
                    hanoi(1, 'src', 'dst', 'aux');
                        if (disc > 0) {
                            hanoi(0, 'src', 'aux', 'dst');
                                END
                        document.writeln("Move disc" + 1 + "from" + Src + "to" + Aux);
                        hanoi(0, 'aux', 'src', 'dst');
                                END
                        }

также первый ход с 4-мя дисками (даже) идет от Src до Aux.

Answer 4

Все просто. Предположим, вы хотите перейти от А к С

если есть только один диск, просто переместите его.

Если имеется более одного диска, выполните

• переместить все диски (n-1 дисков), кроме нижнего, с A на B
• переместить нижний диск с А на С
• переместить n-1 диски с первого шага с A на C

Имейте в виду, что при перемещении дисков n-1 nth вообще не будет проблемой (если он больше всех остальных)

Обратите внимание, что перемещение дисков n-1 повторяется с той же проблемой снова, пока n-1 = 1, и в этом случае вы будете первым, если (где вы должны просто переместить его).

Answer 5

public static void hanoi(int number, String source, String aux, String dest)
{
    if (number == 1)
    {
        System.out.println(source + " - > "+dest);
    }
    else{
        hanoi(number -1, source, dest, aux);
        hanoi(1, source, aux, dest);
        hanoi(number -1, aux, source, dest);
    }
}

Answer 6

def Hanoi(n, A, B, C):
    if(n==1): print "move plates to empty peg"
    else:
       Hanoi(n-1, A, B, C)
       print "move"+str(n)+" to peg "+C
       Hanoi(n-1, B, C, A)

Answer 7

Здесь идет объяснение. Посмотри на картинку ->

Позвонив по номеру Movetower(3,a,b,c), вы намереваетесь переместить все 3 диска из башни A в башню B. Таким образом, последовательные вызовы ->

1. Movetower(3,a,b,c)  // No Move needed
2. Movetower(2,a,c,b)  // No move needed
3. Movetower(1,a,b,c)  // Here is the time to move, move disc1 from a to b
4. Movetower(2,a,c,b)  // Returning to this call again, this is the time to move disc2 from a to c
5. Movetower(1,b,c,a)  // Again the time to move, this time disc1 from b to c
6. Movetower(3,a,b,c)  // Returning to this call again, this is the time to move disc3 from a to b
7. Movetower(2,c,b,a)  // Not the time to move
8. Movetower(1,c,a,b)  // Here is the time to move, move disc1 from c to a
9. Movetower(2,c,b,a)  // Returning to this call again, this is the time to move disc2 from c to b
10.Movetower(1,c,a,b)  // Here is the time to move, move disc1 from a to b

Надеюсь, это поможет:)

Для анимации: https://www.cs.cmu.edu/~cburch/survey/recurse/hanoiex.html

Answer 8

/ ** * * / пакет com.test.recursion;

/ ** * @author kamals1986 Рекурсивный алгоритм для Ханойской башни * алгоритм растет по мощности (2, n). * / открытый класс TowerOfHanoi {

private static String SOURCE_PEG = "B";

private static String SPARE_PEG = "C";

private static String TARGET_PEG = "A";

public void listSteps(int n, String source, String target, String spare) {
    if (n == 1) {
        System.out.println("Please move from Peg " + source + "\tTo Peg\t"
                + target);
    } else {
        listSteps(n - 1, source, spare, target);
        listSteps(1, source, target, spare);
        listSteps(n - 1, spare, target, source);
    }
}

public static void main(String[] args) {
    long startTime = System.currentTimeMillis();
    new TowerOfHanoi().listSteps(18, SOURCE_PEG, TARGET_PEG, SPARE_PEG);

    long endTime = System.currentTimeMillis();

    System.out.println("Done in " + (endTime - startTime) / 1000
            + "\t seconds");
}

}

Answer 9

Tower (N,source,aux.dest):

1. if N =1 Then
      Write : Source -> dest
      return
   end of if
   

2. переместить диск N-1 из источника peg ​​в aug

   call Tower (N-1, source, dest, aux)
   

3. источник записи -> dest

4. перемещение дисков N-1 из peg aux в peg dest

   call Tower (N-1, source, dest, aux)
   

5. Возвращение

Answer 10

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

Пусть «А», «В» и «С» - три башни. Первоначально буква «А» будет содержать «n» дисков. «B» можно использовать как промежуточную башню, а «C» - целевую башню.

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

1. Переместите n-1 диски из башни 'A' в 'B', используя 'C'
2. Переместить диск с 'A' на 'C'
3. Переместите n-1 диски из башни 'B' в 'C', используя 'A'

Код в Java следующий:

открытый класс TowerOfHanoi {

public void TOH(int n, int A , int B , int C){
    if (n>0){
        TOH(n-1,A,C,B);
        System.out.println("Move a disk from tower "+A +" to tower " + C);
        TOH(n-1,B,A,C);
    }
}

public static void main(String[] args) {
    new TowerOfHanoi().TOH(3, 1, 2, 3);
}   

}