turnurile din hanoi
DESCRIPTION
Turnurile din Hanoi. Templul Pura Ulu Danau. Legenda. Se spune că, într-un templu din Benares (India), preoţii lucrează încontinuu, mutând discuri de aur de pe un ac de diamant pe altul. - PowerPoint PPT PresentationTRANSCRIPT
Turnurile din Hanoi
Legenda
Se spune că, într-un templu din Benares (India), preoţii lucrează încontinuu, mutând discuri de aur de pe un ac de diamant pe altul. Atunci când lumea a fost creată, preoţilor din Benares le-au fost dăruite 3 ace de diamant şi 64 discuri de aur.
Templul Pura Ulu Danau
Preoţilor li s-a poruncit să depună pe unul din ace toate discurile, în ordine descrescătoare, apoi să mute întregul turn astfel format pe unul din celelalte două ace, mutând câte un disc odată şi fără a pune un disc mai mare peste un disc mai mic. În conformitate cu legenda, Dumnezeu le-a zis oamenilor:”Când veţi termina de mutat
turnul, atunci lumea se va sfârşi !”
Jocul Turnurile din Hanoi
(uneori numit Turnul din Brahma) a fost inventat de matematicianul francez Edouard Lucas, în 1883.El s-a inspirat din legenda unui templu hindus care folosea un astfel de joc pentru disciplina mentală a tinerilor călugări.
Poziţia finalăPoziţia iniţială
Toate discurile de pe primul ax se vor mutape ultimul ax. Jucătorul va căuta să mute turnulde discuri din cât mai puţine mutări.
Exemplu pentru un turn format din 4 discuri.
Regulile jocului
1.La o mutare se deplasează un singur disc.
2. Un disc mai mare nu poate fi pus peste
un disc mai mic.
Un disc Două discuri
O mutare
Trei mutări
Şapte mutări
Trei discuri
Patru discuri
Cincisprezece mutări
Activitate
Care este numărul minim de mutări pentru 5 discuri ? Caută două tipare: unul despre cum trebuie făcute mutările şi altul pentru numărul minim de mutări.
R
Care este numărul minim de mutări pentru 5 discuri ? Caută două tipare: unul despre cum trebuie făcute mutările şi altul pentru numărul minim de mutări.
-Eliberăm discul de bază => 15 mutări-Mutăm discul de bază => o singură mutare-Acoperim discul de bază=> 15 mutări Total: 31 mutări
Activitate
A B C
…
nn-1
12
Orice turn, cu oricât de multe discuri, poate fi mutat folosind
regulile anterioare
Orice turn, cu oricât de multe discuri, poate fi mutat folosind
regulile anterioare
1 3
…
nn-1
12
2
A B C
Este uimitor cum un foarte simplu algoritm recursiv rezolvă această problemă, pentru orice număr de discuri. Soluţia este foarte elegantă şi pare de-a dreptul magică.
Numărul
discurilor
Numărul minim de mutări
1 1
2 21 + 1 = 3, adică 22 - 1 = 4 - 1 = 3
3 23 + 1 = 7, adică 23 - 1 = 8 - 1 = 7
4 27 + 1 = 15, adică 24 – 1 = 16 – 1 = 15
5 215 + 1 = 31, adică 25 – 1 = 32 – 1 = 31
6 231 + 1 = 63, adică 26 – 1 = 64 – 1 = 63
7 263 + 1 = 127, adică 27 – 1 = 128 – 1 = 127
64 264 – 1 = 18.446.744.073.709.551.615 care se citeşte:
18 trilioane, 446 biliarde, 744 bilioane, 73 miliarde, 709 milioane, 551 mii, 615.
Tabelul următor conţine numărul minim de mutări necesare:
Timpul de lucru
Doar pentru distracţie, hai să pretindem că preoţii
mută un disc pe secundă, fără să se oprească.
Cât de mult timp le va lua pentru a muta un turn
format din:
a. 10 discuri.
b. 20 discuri.
c. 50 discuri.
d. 64 discuri.R
Dacă preoţii ar lucra zi şi noapte, făcând o mutare în fiecare secundă, le-ar lua mai mult de 580 miliarde de ani pentru a termina mutarea turnului format din 64 discuri.
Timpul de lucru
Pentru 64 discuri:
18.446.744.073.709.551.615 mutări
580.000.000.000 ani
www.novelgames.com/flashgames/game.php?id=31
www.mathplayground.com/tower_new.html
Turnurile din Hanoi jocuri on-line la adresele:
Turnurile din Hanoi jocuri on-line la adresele:
Turnurile din Hanoi diferite forme ale jocului
Turnurile din Hanoi diferite forme ale jocului