Tower Of Hanoi: algorytm rekurencyjny

Rok temu miałem kurs programowania funkcyjnego i narysowałem tę ilustrację dla algorytmu. mam nadzieję, że to pomoże!

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

Jest dobre wyjaśnienie rekurencyjnej implementacji w http://www.cs.cmu.edu / ~cburch/survey/recurse/hanoiimpl.html .

Podsumowanie jest takie, że jeśli chcesz przenieść dolną płytę z patyczka A do patyczka B, najpierw musisz przenieść wszystkie mniejsze płyty na nią z A do C. drugie wywołanie rekurencyjne polega na przeniesieniu płyt, które przeniosłeś do C z powrotem na B po tym, jak Twój przypadek bazowy przesunął pojedynczą dużą płytę z a do B.

Zgadzam się, że ten nie jest natychmiastowy, gdy na niego patrzysz, ale jest dość prosty, gdy się do niego sprowadzasz.

Przypadek rekurencyjny: twoja wieża ma rozmiar N > 1. Więc przenieść górną wieżę wielkości n-1 do dodatkowego kołka (przez), przenieść dolną "wieżę" wielkości 1 do kołka docelowego, i przenieść górną wieżę z by do dest.

Więc w prostym przypadku, masz wieżę wysokości 2:

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

Pierwszy krok: przesuń górną wieżę z 2-1 (=1) na dodatkowy kołek (powiedzmy środkowy).

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

Następny: przesuń dolny dysk do miejsca docelowego:

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

I na koniec przesuń górną wieżę (2-1)=1 do celu.

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

Jeśli się nad tym zastanowić, nawet jeśli wieża ma 3 lub więcej, zawsze będzie pusty dodatkowy kołek, lub kołek ze wszystkimi większymi dyskami, aby użyć rekurencji podczas zamiany wież.

Załóżmy, że chcemy przenieść dysk z A do C do B wtedy:

1. Przenieś mniejszy dysk do B.
2. Przesuń inny dysk do C.
3. Przenieś B do C.
4. Przesuń z A do B.
Przenieś wszystko z C na A.]}

Jeśli powtórzysz wszystkie powyższe kroki, dysk zostanie przeniesiony.

Czuję ból!

Chociaż jest to stary post, myślę, że to, co naprawdę trzeba zrozumieć, nie jest podejście "przenieś to na tamto", ale że odpowiedź polega na użyciu efektu ubocznego rekurencji.

Nieocenioną pomocą był dla mnie" mały intrygant", który uczy myślenia i pisania funkcji rekurencyjnych.

Uczy to jednak czytelnika korzystania z wyników zwracanego wyniku w następnym wywołaniu rekurencyjnym.

W wieży Hanoi, odpowiedź nie znajduje się w zwracanym wyniku per se, ale w obserwacji zwracanego wyniku.

Magia występuje w sukcesywnej rearanżacji parametrów funkcji.

Tak problem jest naprawdę w trzech częściach:

• przenoszenie mniejszej wieży do zapasowego kołka
• przeniesienie ostatniego dysku do docelowego peg
• przesunięcie pozostałej wieży na zapasowym kołku do kołka docelowego.

W Schemacie:

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

Jednakże jest wyświetlanie parametrów funkcji, które jest rozwiązaniem problemu i najważniejsze zrozumienie struktury podwójnego drzewa podobne do wywołań.

Nawiasem mówiąc, ręczne rozwiązanie problemu jest całkiem satysfakcjonujące.

• policz liczbę dysków
• jeśli parzyste, przesuń pierwszy dysk do zapasowego kołka, wykonaj następny legalny ruch (Nie dotyczy górnej płyty). Następnie przesuń górną płytę do docelowego kołka, wykonaj następny legalny ruch (nittd). Następnie przesuń górną płytę do peg źródłowego, wykonaj następny legalny ruch (nittd)...
• jeśli nieparzyste, przesuń pierwszy dysk do docelowego kołka, wykonaj następny legalny ruch (Nie dotyczy górnego dysku). Następnie przesuń górną płytę do zapasowego kołka, wykonaj następny legalny ruch (nittd). Następnie przesuń górną płytę do peg źródłowego, wykonaj następny legalny ruch (nittd)...

Najlepsze robi się to zawsze trzymając górną płytę tą samą ręką i przesuwając ją zawsze w tym samym kierunku.

Ostateczna liczba ruchów dla n Dysków to 2^n - 1 move n disc to destination jest w połowie procesu.

Wreszcie, to zabawne, jak Wyjaśnienie problem koledze, żonie/mężowi, a nawet psu (nawet tego nie słuchają) może ugruntować oświecenie.

Po przeczytaniu tych wszystkich wyjaśnień pomyślałem, że rozważę metodę, której użył mój profesor do wyjaśnienia rozwiązania rekurencyjnego Towers of Hanoi. Oto algorytm z N reprezentujący liczbę pierścieni, a A, B, C reprezentujący kołki. Pierwszy parametr funkcji to liczba pierścieni, drugi parametr reprezentuje peg źródłowy, trzeci to peg docelowy, a czwarty to peg zapasowy.

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;

Uczono mnie w szkole, żeby nigdy nie być wstydzę się myśleć mało. Przyjrzyjmy się więc temu algorytmowi dla n = 5. Pytanie, które należy sobie najpierw zadać, to Jeśli chcę przenieść piąty Pierścień Z A do B, gdzie są pozostałe 4 pierścienie? Jeśli piąty pierścień zajmuje peg A i chcemy go przenieść do peg B, to pozostałe 4 pierścienie mogą znajdować się tylko na peg C. w algorytmie powyżej Funkcja Hanoi (n-1, A, C, B) próbuje przenieść wszystkie te 4 inne pierścienie na peg C, więc pierścień 5 będzie mógł przejść z A do B. podążając za tym algorytmem szukamy na n = 4. Jeśli pierścień 4 zostanie przeniesiony z A do C, gdzie są pierścienie 3 i mniejsze? Mogą być tylko na peg B. Następnie, dla n = 3, jeśli pierścień 3 zostanie przeniesiony z A do B, gdzie są pierścienie 2 i 1? Na peg C oczywiście. Jeśli nadal podążasz za tym wzorcem, możesz wizualizować, co robi algorytm rekurencyjny. To podejście różni się od podejścia nowicjusza tym, że patrzy na ostatni dysk pierwszy i pierwszy dysk ostatni.

Pomyśl o tym jak o stosie ze średnicą dysków reprezentowaną przez liczby całkowite (4,3,2,1) Pierwsze wywołanie rekursji zostanie wywołane 3 razy i w ten sposób zostanie wypełniony stos run-time w następujący sposób

Pierwsze połączenie: 1. Drugie wezwanie: 2,1. i trzecie wezwanie: 3,2,1.

Po zakończeniu pierwszej rekurencji, zawartość stosu run-time jest przesuwana do środkowego bieguna od największej średnicy do najmniejszej(pierwsza na końcu). Następnie dysk o średnicy 4 zostaje przeniesiony na miejsce.

Drugie wywołanie rekursji jest takie samo jak pierwsze, z wyjątkiem przeniesienia elementów ze środkowego bieguna do miejsca docelowego.

To proste. Załóżmy, że chcesz przejść z A do C

Jeśli jest tylko jeden dysk, po prostu go przesuń.

Jeśli jest więcej niż jeden dysk, wykonaj

• Przenieś wszystkie dyski (N-1 dyski), z wyjątkiem dolnego z A do B
• przesuń dolny dysk z A do C
• przenieś dyski n-1 z pierwszego kroku z A do C

Należy pamiętać, że przy przenoszeniu dysków n-1 NTH nie będzie problemem (gdy będzie większy niż wszystkie pozostałe)

Zauważ, że przenoszenie dysków n-1 powtarza ten sam problem ponownie, aż n-1 = 1, w którym to przypadku będziesz na pierwszym if (gdzie powinieneś go po prostu przenieść).

ODPOWIEDŹ na pytanie, skąd program wie, że parzyste jest " src " do "aux" , a nieparzyste jest " src " do " dst " dla ruchu otwarcia leży w programie. Jeśli złamiesz fist move z 4 dyskami, to wygląda to tak:

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
                        }

Również pierwszy ruch z 4 płytami (parzystymi) przechodzi z Src do Aux.

Jak zasugerowali nasi znajomi, usunąłem dwie poprzednie odpowiedzi i tutaj się Zgadzam.

Czym jest ogólny algorytm....

Algorytm:

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

Oto przykład roboczy Kliknij tutaj

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

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

Istnieją trzy wieże: wieża źródłowa, Wieża docelowa i Wieża pomocnicza. Wieża źródłowa ma wszystkie dyski, a twoim celem jest przeniesienie wszystkich dysków do wieży docelowej i upewnij się, że w ten sposób nigdy nie umieszczasz większego dysku na mniejszym dysku. Możemy rozwiązać ten problem używając rekurencji w poniższych krokach:

Mamy N liczby dysków na wieży źródłowej

Przypadek podstawowy: n = 1 Jeśli w source tower znajduje się tylko jeden dysk, przenieś go do miejsca docelowego Wieża.

Przypadek rekurencyjny: n >1

• Przenieś górne dyski n-1 z wieży źródłowej do wieży pomocniczej
• Przenieś jedyny pozostały n-ty dysk (po kroku 1) do miejsca docelowego Wieża
• Przenieś dyski n-1, które są teraz w wieży pomocniczej, do miejsca przeznaczenia
  tower, używając source tower jako pomocnika.

Kod źródłowy w Javie:

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

Pierwsze wywołanie rekurencyjne przenosi wszystkie kawałki z wyjątkiem największego ze źródła do używając dest jako stosu pomocniczego. Po wykonaniu wszystkie elementy z wyjątkiem największego będą leżeć obok i największy jest wolny. Teraz możesz przenieść największy do dest i użyć innego rekurencyjnego wywołania, aby przenieść wszystkie elementy z by do dest.

Wywołania rekurencyjne nie będą wiedzieć nic o największym kawałku( tzn. zignorują go), ale to jest w porządku, ponieważ wywołania rekurencyjne będą miały do czynienia tylko z kawałki, które są mniejsze, a tym samym mogą być swobodnie przenoszone na i z największego elementu.

Jako student CS, być może słyszałeś o indukcji matematycznej. Rekurencyjne rozwiązanie Tower Of Hanoi działa analogicznie - tylko inna część jest naprawdę nie zgubić się z B I C, jak były pełne Wieża kończy się.

W prostym sensie chodzi o to, aby wypełnić inną wieżę spośród trzech zdefiniowanych wież w tej samej kolejności dysków, co obecnie, bez większego dysku nakładającego się na mały dysk w dowolnym momencie podczas procedury.

Algo jest następujące:

1. Przenieś dyski n-1 z wieży " A " do " B " za pomocą "C"
2. ruch a dysk od " A " do " C "
3. Przenieś dyski n-1 z wieży " B " do " C " za pomocą "A"

Kod w Javie wygląda następująco:

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

}

Oto Wyjaśnienie. Spójrz na zdjęcie - >

Dzwoniąc Movetower(3,a,b,c), zamierzasz przenieść wszystkie 3 dyski z wieży A do wieży B. Więc wywołania sekwencyjne to - >

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

Mam nadzieję, że pomoże:)

Dla animacji: https://www.cs.cmu.edu / ~cburch/survey/recurse/hanoiex.html

Oto Mój kod rozwiązania problemu Towers of Hanoi przy użyciu rekurencji z golangiem. "package main

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

Tower (N,source,aux.dest):

1.  

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

2. Przenieś dysk N-1 ze źródła peg do Peg aux

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

3. write source - > dest

4. Przenieś dyski N-1 z peg aux do peg dest

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

5. return

/** * */ pakiet com.test.recursion;

/** * @ autor kamals1986 algorytm rekurencyjny dla problemu Tower Of Hanoi * algorytm rośnie przez moc (2, n). */ public class 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");
}

}

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)

Ja też próbuję uzyskać rekurencję.

I found a way i think,

Myślę o tym jak o łańcuchu kroków (Krok nie jest stałą może się zmienić w zależności od poprzedniego węzła)

Muszę rozgryźć 2 rzeczy:

1. poprzedni węzeł
2. rodzaj kroku
3. po kroku co jeszcze przed wywołaniem (jest to argument dla następnego wywołania

Przykład

Factorial

1,2,6,24,120 ......... lub

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

Krok=wielokrotność przez ostatni węzeł

Po kroku co muszę dostać się do następnego węzła,abstract 1

Ok

function =

n*f(n-1) 

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

Miałem nadzieję, że ta pomoc, po prostu pomyśl o 2 thniks, nie jak dostać się z węzła do węzła, ale node-- > step-- > node

Node-- > step jest ciałem funkcji krok-- > węzeł jest argumentem innej funkcji

Bye:) hope i helped