Разбор рекурсивного алгоритма Ханойской башни

Question

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

public class tower { 
    public static void move(int n, int startPole, int endPole) { 
    if (n== 0){ 
     return; 
    } 
    int intermediatePole = 6 - startPole - endPole; 
    move(n-1, startPole, intermediatePole); 
    System.out.println("Move " +n + " from " + startPole + " to " +endPole); 
    move(n-1, intermediatePole, endPole); 
    } 

    public static void main(String[] args) { 
    move(2, 1, 3); 
    } 
} 

Я написал несколько заметок, чтобы помочь мне разобрать код:

move(2,1,3) 
move(1,1,2) 
n==0 

--------going back up 

n==0 
move(1,1,2) 
Move 1 from 1 to 2 
move(2,1,3) 
Move 2 from 1 to 3 

move(2,1,3) 
move(1,2,3) 
n==0 

-------going back up 

n==0 
move(1,2,3) 
Move 1 from 2 to 3 
move(2,1,3) 
?????????? (step is missing) 

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

Я нашел, что итеративный код будет намного легче понять, и я написал рекурсивный алгоритм, основанный на итеративном алгоритме.

Answer 1

move(2,1,3) 
+--move(1,1,2) 
| +--move(0,1,3) 
| | '--(do nothing) 
| +--print "move from 1 to 2" 
| '--move(0,3,2) 
|  '--(do nothing) 
+--print "move from 1 to 3" 
'--move(1,2,3) 
    +--move(0,2,1) 
    | '--(do nothing) 
    +--print "move from 2 to 3" 
    '--move(0,1,3) 
     '--(do nothing) 

Для перемещения п дисков из башни в возвышаться б, вам нужно

1. Переместить верхние п - 1 диски из пути, используя башню c.
2. Переместить нижний диск в башню b.
3. Переместить верхнюю часть спинки поверх предыдущего диска, на башне b.

Шаг 1 и 3 выполняются рекурсивно.

---

/** Moves n discs from startPole to endPole */ 
public static void move(int n, int startPole, int endPole) { 
    if (n == 0) { 
     // Base case: No disk to move. Do nothing. 
     return; 
    } 

    // Calculate the pole that is not startPole and not endPole. 
    // 1 + 2 + 3 = 6 
    // 6 - 1 - 2 = 3 
    // 6 - 1 - 3 = 2 
    // 6 - 2 - 3 = 1 
    int intermediatePole = 6 - startPole - endPole; 

    // Step 1: Move n-1 discs out of the way, to the intermediate pole. 
    move(n-1, startPole, intermediatePole); 

    // Step 2: Move the bottom disc to the destination, the end pole. 
    System.out.println("Move " + n + " from " + startPole + " to " + endPole); 

    // Step 3: Move the n-1 discs back on top of the previous disc, on the end pole. 
    move(n-1, intermediatePole, endPole); 
} 

Answer 2

Я сомневаюсь, что ваша заметка правильная, ее взгляды запутаны.

Когда код выполняется, она работает так:

движение (2,1,3)

превращается в

движение (1,1,2)

(выход) "Переместить 2 от 1 до 3"

шаг (1,2,3)

то время как

движение (1,1,2)

превращается в

движение (0,1,3) не // ничего не делать

(выход) "Переместить 1 от 1 до 2"

движение (0,3,2) // ничего не делать

и

двигаться (1,2,3)

превращается в

двигаться (0,2,1) // ничего не делать

(выход) "Переместить 1 из 2 до 3"

двигаться (0,1,3) // ничего не делать

поэтому его выход:

"Переместить 1 от 1 до 2"

"Переместить 2 от 1 до 3"

"Переместить 1 от 2 до 3"

Непонятным может быть n на выходе.В своем движении() это имеет значение и просто описывает сумму элементов, которые будут перемещаться в этом перемещении (n-1, ..., ...), move (n, ..., ...) и следующий ход (n-1, ..., ...), а не только ход (n, ..., ...).