Turnurile din Hanoi
©2007 Prof. Silvia Doandeş
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
©2007 Prof. Silvia Doandeş
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 !”
©2007 Prof. Silvia Doandeş
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.
©2007 Prof. Silvia Doandeş
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.
©2007 Prof. Silvia Doandeş
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.
©2007 Prof. Silvia Doandeş
Un disc Două discuri
O mutare
Trei mutări
©2007 Prof. Silvia Doandeş
Şapte mutări
Trei discuri
©2007 Prof. Silvia Doandeş
Patru discuri
Cincisprezece mutări
©2007 Prof. Silvia Doandeş
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
©2007 Prof. Silvia Doandeş
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
©2007 Prof. Silvia Doandeş
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
©2007 Prof. Silvia Doandeş
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ă.
©2007 Prof. Silvia Doandeş
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:
©2007 Prof. Silvia Doandeş
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
©2007 Prof. Silvia Doandeş
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
©2007 Prof. Silvia Doandeş
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
Top Related