Turnurile din Hanoi Python – înțelegerea recursivității [duplicat] (Programare, Python, Algoritm, Recursivitate, Turnurile Din Hanoi)

heather a intrebat.

Sunt complet nou în Python și în prezent trec peste un tutorial despre The Towers of Hanoi și recursivitate. Am crezut că am înțeles recursivitatea până când au dat acest exemplu:

def moveTower(height,fromPole, toPole, withPole):
    if height >= 1:
        moveTower(height-1,fromPole,withPole,toPole)
        moveDisk(fromPole,toPole)
        moveTower(height-1,withPole,toPole,fromPole)
    #print(withPole)

def moveDisk(fp,tp):
    print("moving disk from",fp,"to",tp)


moveTower(3,"A","B","C")

care tipărește mișcările corecte pentru rezolvarea problemei turnurilor din Hanoi cu 3 discuri: mutarea discului de la A la B mutarea discului de la A la C mutarea discului de la B la C mutarea discului de la A la B mutarea discului de la C la Amo mutarea discului de la C la B mutarea discului de la A la B mutarea discului de la A la B

Întrebarea mea este: cum face acest lucru? ar putea cineva să treacă în revistă liniile de cod, astfel încât să înțeleg cum se imprimă mișcările corecte? Sunt confuz în principal în ceea ce privește modul în care valoarea lui fp și tp se poate schimba de la A la B la C. Îmi cer scuze dacă este o întrebare cam largă! Orice ajutor ar fi foarte apreciat!

Comentarii

  • Poate că acest răspuns este util: stackoverflow.com/a/1223334/3440545 –  > Por AbcAeffchen.
  • Aș sugera să rămânem la print(height, fromPole, toPole, withPole) în partea de sus și să vedeți ce se întâmplă! –  > Por jonrsharpe.
  • Mulțumesc foarte mult tuturor celor care au răspuns! Mă simt mult mai încrezător în înțelegerea mea acum 🙂 –  > Por heather.
5 răspunsuri
pentadecagon

În acest caz simplu poți doar să vizualizezi ce se întâmplă folosind corespunzător prints, astfel:

def moveTower(height,fromPole, toPole, withPole):
    if height >= 1:
        print( "    "*(3-height), "moveTower:", height, fromPole, toPole )
        moveTower(height-1,fromPole,withPole,toPole)
        moveDisk(fromPole,toPole,height)
        moveTower(height-1,withPole,toPole,fromPole)
    #print(withPole)

def moveDisk(fp,tp,height):
    print("    "*(4-height), "moving disk", "~"*(height), "from",fp,"to",tp)


moveTower(3,"A","B","C")

Rezultatul este:

moveTower: 3 A B
     moveTower: 2 A C
         moveTower: 1 A B
             moving disk ~ from A to B
         moving disk ~~ from A to C
         moveTower: 1 B C
             moving disk ~ from B to C
     moving disk ~~~ from A to B
     moveTower: 2 C B
         moveTower: 1 C A
             moving disk ~ from C to A
         moving disk ~~ from C to B
         moveTower: 1 A B
             moving disk ~ from A to B

Comentarii

  • Mulțumesc foarte mult 🙂 în explicația dvs. de ieșire, ați omis un argument din funcția moveTower, (ex. moveTower: 3 A B, când în exemplul meu moveTower(height, fromPole,toPole,withPole)) este acest lucru pur și simplu pentru că al treilea argument nu este utilizat cu adevărat? aș putea să scap de el? –  > Por heather.
  • Acest al treilea argument este redundant, dar convenabil, așa că vă sugerez să îl lăsați în cod. Rezultatul ar trebui să vizualizeze încrucișarea diferitelor operații recursive. –  > Por pentadecagon.
  • de asemenea, în cazul în care aveți în ieșirea dvs., mutarea discului presupun că acest lucru se referă la moveDisk-ul meu? mulțumesc din nou! –  > Por heather.
  • îmi pare rău, știu că asta a fost cu ceva timp în urmă, încă sunt blocat! am revenit la asta astăzi și mi-am dat seama că nu înțeleg cum în această parte a codului: moveTower: 3 A B moveTower: 2 A C moveTower: 1 A B (primele 3 linii) de ce este a 3-a linie, 1 AB nu ar trebui să fie 1 AC? @pentadecagon –  > Por heather.
fredtantini

iată ce face. Poziția de pornire este:

A|321
B|
C|

apoi cu moveTower(2,fromA,toC, withB) rezultatul este:

A|3
B| 
C|21

apoi, moveDisk(fromA, toB) face

A|
B|3
C|21

și în cele din urmă moveTower(2,fromC, toB) încheie jocul

A|
B|
C|321

Aceasta este soluția obișnuită pentru Hanoi: mutați turnul de înălțime h-1 la withPole, mutați cel mai mare disc la endPole și mută turnul de înălțime h-1 la endPole.

Acest lucru funcționează pentru că puteți muta fiecare disc din turnul de înălțime h-1 pe cel mai mare disc.

Pentru a face acest lucru moveTower(height-1,w,x) aveți voie să așezați toate discurile rămase în toate cele 3 turnuri.

Astfel, veți moveTower(height-2,y,z) muta apoi al doilea cel mai mare disc la destinație și veți muta din nou turnul de la înălțimea 2.

Edit:Diagrama din acest link descrie cel mai bine ceea ce încerc să spun („O imagine face cât o mie de cuvinte”).

Dacă știți cum să mutați un turn de height-1 atunci, nu trebuie decât să faceți cei 3 pași descriși în algoritmul dumneavoastră. moveDisc este „cazul de bază” (urcă primul pas), moveTower este recursivitatea (cum să treci de la pasul n la n+1).

Codor

Subiectul este acoperit aici, însă abordarea recursivă poate fi confuză dacă nu ești familiarizat cu acest concept. Algoritmul funcționează mai întâi prin mutarea recursivă a tuturor discurilor, cu excepția ultimului (o instanță mai mică a problemei) prin intermediul cuierului cache de la distanță, apoi prin mutarea „efectivă” a ultimului disc la cuierul de destinație și apoi prin mutarea turnului la cuierul inițial. De fapt, bazându-se pe recursivitate, discul de la bază este mutat în cuierul de destinație, ceea ce este imposibil de făcut direct, deoarece nu există o mutare validă. În apelul recursiv, cele trei piese își schimbă rolurile astfel încât întotdeauna o piesă goală devine memoria cache. Acest lucru se înțelege cel mai bine dacă vă imaginați că piesele nu sunt dispuse în linie, ci în cerc. Spre deosebire de alte probleme, aici apelul recursiv are loc mai întâi și apoi se face mișcarea „efectivă”.

Întrebarea poate fi privită ca un duplicat al acestei întrebări.

dilbert

Ar trebui să tipăriți apelul fiecărui moveTower pentru a vedea schimbările în argumentele sale. Recursivitatea propagă de obicei modificările prin argumente. Un număr de secvență este util pentru a arăta ordinea (bineînțeles, și imprimarea în consolă este ordonată).

def seq_nummer():
    num = 0
    while True:
        num += 1
        yield num

seq_num = seq_nummer()

def moveTower(height, fromPole, toPole, withPole):
    print("seq: %d" % seq_num.next())
    print("height: %d, fromPole: %s, toPole: %s, withPole: %s" % (height, fromPole, toPole, withPole))
    if height >= 1:
        moveTower(height-1, fromPole, withPole, toPole)
        moveDisk(fromPole, toPole)
        moveTower(height-1, withPole, toPole, fromPole)

def moveDisk(fp,tp):
    print("moving disk from",fp,"to",tp)

moveTower(3,"A","B","C")

Abhishek Bansal
moveTower(height-1,fromPole,withPole,toPole)

Mutați toate discurile, mai puțin unul, de la polul inițial la polul intermediar, folosind al treilea pol.

moveDisk(fromPole,toPole)

Mutați ultimul disc de la polul inițial la polul final. Acum ultimul disc se află în poziția corectă și nu mai trebuie mutat.

moveTower(height-1,withPole,toPole,fromPole)

Mutați toate discurile de la polul intermediar la polul final, folosind primul pol dacă este necesar.