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

Ответ 1

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

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

• переместите n-1 диски с A на B. Это оставляет диск #n один на привязке A
• переместите диск #n с A на C
• переместите n-1 диски из B в C, чтобы они сидели на диске #n

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

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

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

Ответ 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)

Задача трех колец была разбита на 2 проблемы с двумя кольцами (1.x и 3.x)

Ответ 3

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

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

Ответ 4

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

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

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

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

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

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

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

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

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

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

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

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

Ответ 5

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

• переместите меньший диск в B.
• переместите другой диск на C.
• переместите B в C.
• перейти от A к B.
• переместить все из C в A.

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

Ответ 6

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

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

Неоценимую помощь мне оказала "The Little Schemer", которая учит думать и писать рекурсивные функции.

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

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

Магия возникает при успешной перестановке параметров функции.

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

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

В схеме:

(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 - на полпути процесса.

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

Ответ 7

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

• первый вызов: 1. Второй вызов: 2,1. и третий вызов: 3,2,1.

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

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

Ответ 8

Прочитав все эти объяснения, я подумал, что я взвесил метод, который мой профессор использовал для объяснения речного решения Towers of Hanoi. Ниже приведен алгоритм с 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. Сначала зададим вопрос, хочу ли я перенести пятое кольцо из A в B, где находятся остальные 4 кольца? Если пятое кольцо занимает привязку 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? Конечно, на колышке С. Если вы продолжите следовать этому шаблону, вы можете визуализировать то, что делает рекурсивный алгоритм. Этот подход отличается от подхода новичков тем, что он сначала смотрит на последний диск, а первый - на последний.

Ответ 9

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

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

Ответ 10

Это просто. Предположим, вы хотите перейти от A к C

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

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

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

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

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

Ответ 11

Ответ на вопрос, как программа знает, что даже является "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.

Ответ 12

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

Это дает вам четкое понимание.

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

Алгоритм:

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)
}

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

Ответ 13

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);
    }
}

Ответ 14

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;
}

Ответ 15

Вот объяснение. Посмотрите на изображение →

Вызывая 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

Ответ 16

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

У нас есть 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);
    }
}

Ответ 17

Как студент CS, вы, возможно, слышали о математической индукции. Рекурсивное решение Tower of Hanoi работает аналогично - только другая часть действительно не потеряется с B и C, так как полная башня заканчивается.

Ответ 18

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

Пусть 'A', 'B' и 'C' - три башни. "A" будет башней, содержащей "n" диски изначально. "B" может использоваться как промежуточная башня, а "C" - это башня-мишень.

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

• Переместите n-1 диски с башни 'A' на 'B', используя 'C'
• Переместите диск с 'A' на 'C'
• Переместите 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);
}   

}

Ответ 19

Вот мой код решения проблемы Towers of Hanoi, используя рекурсию с golang. `основной пакет

import "fmt"

func main() {
    toi(4, "src", "dest", "swap")
}

func toi(n int, from, to, swap string) {
    if n == 0 {
        return
    }
    if n == 1 {
        fmt.Printf("mov %v %v -> %v\n", n, from, to)
        return
    }
    toi(n-1, from, swap, to)
    fmt.Printf("mov %v %v -> %v\n", n, from, to)
    toi(n-1, swap, to, from)
}`

Ответ 20

Этот пример Python3 использует рекурсивное решение:

# Hanoi towers puzzle
# for each n, you have to move n-1 disks off the n disk onto another peg
# then you move the n disk to a free peg
# then you move the n-1 disks on the other peg back onto the n disk

def hanoi(n):
    if n == 1:
        return 1
    else:
        return hanoi(n-1) + 1 + hanoi(n-1)


for i in range(1, 11):
    print(f"n={i}, moves={hanoi(i)}")

Выход:

n=1, moves=1
n=2, moves=3
n=3, moves=7
n=4, moves=15
n=5, moves=31
n=6, moves=63
n=7, moves=127
n=8, moves=255
n=9, moves=511
n=10, moves=1023

Но, конечно, самый эффективный способ выяснить, сколько ходов, это осознать, что ответы всегда 1 меньше 2 ^ n. Таким образом, математическое решение 2 ^ n - 1

Ответ 21

Только что посмотрел это видео сегодня: Рекурсия 'Super Power' (на Python) - Computerphile, и я думаю, что мы обязательно должны иметь код профессора Торстена Альтенкирха здесь, так как это очень красивая и элегантная часть кода рекурсии и не всегда, что у нас есть качественное видео, чтобы показать в ответе.

def move(f,t) : 
    print("move disc from {} to {}!".format(f,t))

def hanoi(n,f,h,t) : 
    if n==0 : 
        pass
    else :
        hanoi(n-1,f,t,h)
        move(f,t)
        hanoi(n-1,h,f,t)

наша функция hanoi имеет 4 параметра:

• n: количество дисков
• f: источник, откуда диски (откуда)
• h: промежуточный шаг "через" (помощник)
• t: конечная позиция, где мы хотим, чтобы диски были в конце (цель)

>>> hanoi(4,"A","B","C")
move disc from A to B!
move disc from A to C!
move disc from B to C!
move disc from A to B!
move disc from C to A!
move disc from C to B!
move disc from A to B!
move disc from A to C!
move disc from B to C!
move disc from B to A!
move disc from C to A!
move disc from B to C!
move disc from A to B!
move disc from A to C!
move disc from B to C!

Ответ 22

Tower (N,source,aux.dest):

•  

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

• перемещение диска N-1 из источника привязки для привязки aux

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

• источник записи → dest

• перемещение N-1 дисков из привязки aux to peg dest

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

• возвращение

Ответ 23

/**  *  */ пакет 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");
}

}

Ответ 24

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)

Ответ 25

Я также пытаюсь получить рекурсию.

Я нашел способ, я думаю,

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

Мне нужно выяснить 2 вещи:

• предыдущий node
• шаг вид
• после шага, что еще перед вызовом (это аргумент для следующего вызова

Пример

факториала

1,2,6,24,120......... или

1,2 * (1), 3 * (2 * 1), 4 * (3 * 2 * 1,5 * (4 * 3 * 2 * 1)

step = multiple последним node

после шага, что мне нужно, чтобы перейти к следующему node, аннотация 1

ОК

function =

n*f(n-1) 

its 2 steps process
from a-->to step--->b

Я надеялся на эту помощь, просто подумайте о двух thniks, а не о том, как добраться от node до node, но node → step → node

node → шаг - это тело функции step → node - это аргументы другой функции

bye:) надеюсь, я помог