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

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

На самом деле, раздел , откуда вы взяли этот код , также предлагает объяснение:

Чтобы переместить n дисков из колышка A в колышек C:

1. переместить n − 1 дисков из A в B. При этом диск #n остается на колышке A
2. переместить диск #n с А на С
3. переместить n − 1 дисков из B в C, чтобы они находились на диске # n

Совершенно очевидно, что сначала вы должны удалить n - 1 диск, чтобы получить доступ к n th. И что вам нужно сначала переместить их на другой колышек, чем там, где вы хотите, чтобы появилась полная башня.

Код в вашем посте имеет три аргумента, кроме количества дисков: A исходный колышек, конечный колышек и временный колышек, на которых диски можно хранить между ними (где подходит каждый диск размером n - 1).

Рекурсия происходит фактически дважды, там, один раз перед writeln, один раз после. Тот, что перед writeln, переместит n - 1 дисков на временную привязку, используя конечную привязку в качестве временного хранилища (аргументы в рекурсивном вызове находятся в другом порядке). После этого оставшийся диск будет перемещен к колышку назначения, и после этого вторая рекурсия заставит переместить всю башню, переместив башню n - 1 из временной колышка в колышек назначения над диском. п.

Answer 2

год назад я прошел курс функционального программирования и нарисовал эту иллюстрацию для алгоритма. надеюсь, это поможет!

(0)  _|_         |          |
    __|__        |          |
   ___|___       |          |
  ____|____  ____|____  ____|____

(1.1) |          |          |
    __|__        |          |
   ___|___      _|_         |
  ____|____  ____|____  ____|____ (A -> B)

(1.2) |          |          |
      |          |          |
   ___|___      _|_       __|__
  ____|____  ____|____  ____|____ (A -> C)

(1.3) |          |          |
      |          |         _|_
   ___|___       |        __|__
  ____|____  ____|____  ____|____ (B -> C)



(2.1) |          |          |
      |          |         _|_
      |       ___|___     __|__
  ____|____  ____|____  ____|____ (A -> B)



(3.1) |          |          |
      |          |          |
     _|_      ___|___     __|__
  ____|____  ____|____  ____|____ (C -> A)

(3.2) |          |          |
      |        __|__        |
     _|_      ___|___       |
  ____|____  ____|____  ____|____ (C -> B)

(3.3) |         _|_         |
      |        __|__        |
      |       ___|___       |
  ____|____  ____|____  ____|____ (A -> B)

Задача 3 колец была разделена на задачу 2 колец (1.x и 3.x)

Answer 3

Есть хорошее объяснение рекурсивной реализации Ханоя на http://www.cs.cmu.edu/~cburch/survey/recurse/hanoiimpl.html.

Суть в том, что если вы хотите переместить нижнюю пластину с палки А на палочку В, вам сначала нужно переместить все меньшие пластины сверху нее с А на С. Затем следует второй рекурсивный вызов - переместить пластины переместился в C обратно на B после того, как ваш базовый случай переместил одну большую тарелку из A в B.

Answer 4

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

Базовый случай: ваша башня имеет размер 1. Таким образом, вы можете сделать это за один ход, от источника напрямую к месту назначения.

Рекурсивный случай: ваша башня имеет размер n> 1. Таким образом, вы перемещаете верхнюю башню размера n-1 в дополнительный колышек (мимо), перемещаете нижнюю «башню» размера 1 к колышку назначения и перемещаете верхняя башня от до до дест.

Итак, в простом случае у вас есть башня высотой 2:

 _|_    |     |
__|__   |     |
===== ===== =====

Первый шаг: переместите верхнюю башню 2-1 (= 1) в дополнительный колышек (средний, скажем так).

  |     |     |
__|__  _|_    |
===== ===== =====

Далее: переместить нижний диск к месту назначения:

  |     |     |
  |    _|_  __|__
===== ===== =====

И, наконец, переместите верхнюю башню (2-1) = 1 к месту назначения.

  |     |    _|_
  |     |   __|__
===== ===== =====

Если вы подумаете об этом, даже если бы в башне было 3 или более, всегда будет пустой дополнительный колышек или колышек со всеми более крупными дисками, которые можно использовать для рекурсии при смене башен.

Answer 5

Предположим, что мы хотим переместить диск с A на C через B, затем:

1. переместите меньший диск в B.
2. переместить другой диск в C.
3. переместить B в C.
4. перейти от А к Б.
5. переместить все из C в A.

Если вы повторите все вышеуказанные шаги, диск перейдет.

Answer 6

Я чувствую боль!

Хотя это старый пост, я думаю, что действительно нужно понять, это не подход "переместить это к этому", а то, что ответ включает использование побочного эффекта рекурсии.

Для меня неоценимой помощью был «Маленький интриган», который учит думать и писать рекурсивные функции.

Однако это учит читателя использовать результаты возвращенного результата в следующем рекурсивном вызове.

В Ханойской башне ответ не в возвращенном результате как таковом, а в наблюдении за возвращенным результатом.

Волшебство происходит в последовательной перегруппировке параметров функции.

Да, проблема действительно в трех частях:

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

На схеме:

(define (th n a b c)
    (if (zero? n) 'done
        (begin
           (th (- n 1) a c b)
           (display (list a c))
           (newline)
           (th (- n 1) b a c))))
(th 5 'source 'spare 'destination)

Однако именно отображение параметров функции является решением проблемы и принципиальным пониманием структуры вызовов, подобной двойному дереву.

Решение также передает мощность proof by induction и теплого свечения всем программистам, которые боролись с обычными структурами управления.

Кстати, решение проблемы вручную вполне удовлетворительно.

• считать количество дисков
• если даже, переместите первый диск в запасную колышек, сделайте следующий законный ход (не включая верхний диск). Затем переместите верхний диск к колышку назначения, сделайте следующий законный ход (nittd). Затем переместите верхний диск к исходной колышке, сделайте следующий допустимый ход (nittd) ...
• если нечетно, переместите первый диск к колышку назначения, сделайте следующий допустимый ход (не включая верхний диск). Затем переместите верхний диск на запасную колышек, сделайте следующий законный ход (nittd). Затем переместите верхний диск к исходной колышке, сделайте следующий допустимый ход (nittd) ...

Лучше всего делать, всегда держа верхний диск одной и той же рукой и всегда перемещая эту руку в одном направлении.

Окончательное число ходов для дисков n: 2^n - 1, move n disc to destination находится на полпути в процессе.

Наконец, забавно, как объясняя проблему коллеге, вашей жене / мужу или даже собаке (даже если они ее не слушают) могут закрепить просветление.

Answer 7

Думайте об этом как о стеке с диаметром дисков, представленным целыми числами (4,3,2,1) Первый рекурсивный вызов будет вызван 3 раза и, таким образом, заполняет стек времени выполнения следующим образом

1. Первый звонок: 1. Второй звонок: 2,1. и третий звонок: 3,2,1.

После окончания первой рекурсии содержимое стека времени выполнения выталкивается на средний полюс от наибольшего диаметра до наименьшего (первый в последнем выходе). Затем диск с диаметром 4 перемещается к месту назначения.

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

Answer 8

Прочитав все эти объяснения, я подумал, что должен взвесить метод, который мой профессор использовал для объяснения рекурсивного решения Башен Ханоя. Здесь снова алгоритм с n , представляющим количество колец, и A, B, C, представляющим колышки. Первый параметр функции - это количество звонков, второй параметр представляет исходный колышек, третий - конечный, четвертый - резервный.

procedure Hanoi(n, A, B, C);
  if n == 1
    move ring n from peg A to peg B
  else
    Hanoi(n-1, A, C, B);
    move ring n-1 from A to C
    Hanoi(n-1, C, B, A);
end;

В аспирантуре меня учили, чтобы никогда не было стыдно думать маленькими. Итак, давайте рассмотрим этот алгоритм для n = 5. Сначала задайте себе вопрос , хочу ли я переместить 5-е кольцо с А на В, где остальные 4 кольца? Если 5-е кольцо занимает колышек A и мы хотим переместить его в колышек B, тогда остальные 4 кольца могут быть только на колышке C. В алгоритме выше функция Ханой (n-1, A, C, B) пытается чтобы переместить все эти 4 других кольца на колышек C, чтобы кольцо 5 могло перемещаться из A в B. Следуя этому алгоритму, мы смотрим на n = 4. Если кольцо 4 будет перемещено из A в C, где находятся кольца 3 и меньше? Они могут быть только на колышке B. Далее, для n = 3, если кольцо 3 будет перемещено из A в B, где находятся кольца 2 и 1? На привязке конечно. Если вы продолжите следовать этой схеме, вы можете визуализировать, что делает рекурсивный алгоритм. Этот подход отличается от подхода новичка тем, что он смотрит на последний диск первым, а первый диск последним.

Answer 9

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

У нас есть n количество дисков на исходной башне

Базовый случай: n = 1 Если в башне источника есть только один диск, переместите его в башню назначения.

Рекурсивный регистр: n> 1

• Переместить верхние диски n-1 из башни-источника в башню-помощник
• Переместить единственный оставшийся, n-й диск (после шага 1) в место назначения башня
• Переместите диски n-1, которые сейчас находятся в вспомогательной башне, к месту назначения
  башня, используя исходную башню в качестве помощника.

Исходный код на Java:

private void towersOfHanoi(int n, char source, char destination, char helper) {
    //Base case, If there is only one disk move it direct from source to destination
    if(n==1){
        System.out.println("Move from "+source+" to "+destination);
    }
    else{
        //Step1: Move the top n-1 disks from source to helper
        towersOfHanoi(n-1, source, helper, destination);
        //Step2: Move the nth disk from source to destination
        System.out.println("Move from "+source+" to "+destination);
        /*Step3: Move the n-1 disks(those you moved from source to helper in step1) 
         * from helper to destination, using source(empty after step2) as helper
         */
        towersOfHanoi(n-1, helper, destination, source);
    }
}

Answer 10

void TOH(int n, int a, int b){
        /*Assuming a as source stack numbered as 1, b as spare stack numbered as 2 and  c as target stack numbered as 3. So once we know values of a and b, we can determine c as there sum is a constant number (3+2+1=)6.
       */
int c = 6-a-b;
if(n==1){
    cout<<"Move from "<<a<<" to "<<b<<"\n";
}
else{
    // Move n-1 disks from 1st to 2nd stack. As we are not allowed to move more than one disks at a time, we do it by recursion. Breaking the problem into a simpler problem.
    TOH(n-1, a, c);
    // Move the last alone disk from 1st to 3rd stack.
    TOH(1, a, b);
    // Put n-1 disks from 2nd to 3rd stack. As we are not allowed to move more than one disks at a time, we do it by recursion. Breaking the problem into a simpler problem.        
    TOH(n-1, c, b);
}
}
int main() {

TOH(2, 1, 3);
cout<<"FINISHED                        \n";
TOH(3, 1, 3);
cout<<"FINISHED                        \n";
TOH(4, 1, 3);
return 0;
}