Turnul din Hanoi - rezolvarea cu algoritmi si structuri de date problemă
Puzzle din Turnurile din Hanoi a fost inventat de matematicianul francez Eduardom Lukasom în 1883. El a fost inspirat de o legenda care spune castelul hindus, în cazul în care a stabilit obiectivul pentru preoții tineri. În vremurile timpurii au fost date trei tije și un teanc de șaizeci și patru discuri de aur, fiecare dintre care este puțin mai mică decât cea anterioară. A fost necesar pentru a rearanja toate discurile de la un bar la altul, ca urmare a două condiții stricte. În primul rând, la un moment dat, puteți muta doar un singur disc. În al doilea rând, nu puteți pune un disc mare pe partea de sus a unul mai mic. Preoții au lucrat (și lucrează în ziua de azi) foarte spor, zi și noapte, se deplasează în fiecare secundă un singur disc. Legenda spune că atunci când termină activitatea lor, castelul se va transforma în praf, iar lumea va dispărea.
Deși legenda și interesant, nu trebuie să vă faceți griji cu privire la sfârșitul iminent al lumii. Numărul de lovituri necesare pentru transpunerea corectă a turnului celor 64 de discuri, este egal cu \ (2 ^ -1 = 18,446,744,073,709,551,615 \). La o viteză de un viraj pe secundă, este nevoie \ (584942417355 \) ani! cifra mare pentru un astfel de simplu la prima vedere, puzzle-ului.
Figura 1 prezintă un exemplu de configurație de disc în călătorie mijlocul lui de la primul la al treilea cuier. Rețineți că (așa cum este reglementată de regulile) conduce pe fiecare dintre picioare sunt formate în așa fel încât mai mic este întotdeauna situată pe mare. Dacă nu ați încercat să rezolve acest puzzle, puteți încerca chiar acum. Pentru că nu are nevoie de roți reale și tije - de lucru și un teanc de cărți sau bucăți de hârtie.
Figura 1: Exemplu de locație de disc Turnul din Hanoi.
Cum putem rezolva această problemă recursiv? De ce ar începe? Care este cazul de bază aici? Să ne gândim la asta de la capăt la început. Să presupunem că inițial pe prima tijă pe care este un turn de cinci discuri. Dacă știți deja cum să se mute patru dintre ele pe al doilea cuier, puteți schimba cu ușurință la tija de antrenare inferioară №3, și apoi trecerea la același turn cu tija №2. Dar ce se întâmplă dacă nu ai nici o idee cum să se mute turnul din primele patru? Să presupunem că se știe cum să se mute turnul de sus trei discuri în a treia cuier. Apoi, cu mișcarea de-a patra dificultăți ar putea apărea: Pune-l pe al doilea bar, iar apoi a pus pe partea de sus a celor care sunt înșirate pe a treia. Dar, dacă nu știi cum să se mute trei? Ei bine, puteți schimba turnul de două discuri de pe tija №2, iar al treilea - pe tija №3, apoi a pus pe partea de sus a unui turn al celor două. Dar dacă încă nu înțeleg cum se face? Sunt sigur că veți fi de acord să se mute un disc pe al treilea cuier floare la ureche - nu există nimic banal. Se pare ca în cazul de bază, precum?
Aici este o schemă generală a modului în care să se mute turnul cu o tijă sursă predeterminată folosind intermediar:
- turn Mutare (număr de discuri - 1) la peg intermediar, folosind predeterminate.
- Puneți discul rămas într-o anumită tijă.
- Muta turnul din care rămâne pe unitatea arborelui intermediar la destinație, folosind peg original.
Atâta timp cât vom urma regula pe care o unitate mai mare în partea de jos a stivei, cele trei etape descrise pot fi folosite recursiv de prelucrare unități de stocare mai mari, ca și în cazul în care acestea nu au fost acolo. Singurul lucru pe care am ratat în diagrama de mai sus - este identificarea cazului de bază. Cel mai simplu Turnul din Hanoi - un turn de același disc. În acest caz, avem nevoie doar pentru a muta un singur disc la destinația finală. Turnul de un singur disc va fi cazul nostru de bază. De altfel, schema de pașii de mai sus duc la ea, de fiecare dată reducând înălțimea unității turn de la punctele 1 și 3. Listarea 1 arată codul în Python pentru rezolvarea Turnurile din Hanoi.
Rețineți că Listarea 1 este aproape identic cu descrierea verbală. Cheia pentru simplitatea algoritmului pe care o facem două apel recursiv diferite, unul în linia 3, iar al doilea - în linia 5. În linia 3, vom muta toate discurile cu excepția partea de jos, de la inițial la arborele intermediar. Linia următoare rearanjează pur și simplu discul inferior în poziția sa finală. Apoi, în linia 5 vom muta turnul de la arborele intermediar pe partea de sus a celui mai mare disc. Cazul de bază este detectată când înălțimea turnului este egală cu zero. În acest caz, nu se întâmplă nimic, așa că funcția moveTower se întoarce gol. La procesarea cazului de bază, este important să ne amintim că o simplă întoarcere de moveTower - este ceea ce permite în cele din urmă funcția moveDisk să fie numit.
moveDisk Funcția. prezentat în Listarea 2. foarte simplu. Tot ceea ce face ea - se imprimă că unitatea a fost mutat de la un bar la altul. Dacă tastați și începe programul moveTower. vei vedea cum ea va scrie o soluție foarte eficientă pentru a puzzle-ului.
Programul ActiveCode 1 conține o soluție completă pentru problema cu cele trei discuri.
Rulați Salvare încărcare Afișează în Codelens
soluție recursivă a problemei Turnurile din Hanoi. (Hanoi)
Acum, că puteți vedea codul pentru moveTower. și moveDisk. vă întrebați de ce nu avem o structură de date care să urmărească în mod explicit care discul pe care se află tija. Iată un sfat: dacă urmăriți în mod explicit drive-uri, va trebui să utilizați trei obiecte stivă - una pentru fiecare nucleu. Răspunsul este în faptul că Python ne oferă stive implicit și atunci când avem nevoie de ea.