Torres de Hanoi: diferència entre les revisions
Contingut suprimit Contingut afegit
Correcció de format |
Expansió del contingut |
||
Línia 33:
En la versió de la llegenda, amb 64 discs, caldrien <math>2^{64} - 1 = 18446744073709551615</math> moviments; suposant que els monjos fossin capaços d'efectuar un moviment per segon (i per tant, <math>31536000</math> moviments per any), trigarien més de mig bilió d'anys en fer tots els moviments.
=== Resolució iterativa ===
[[Fitxer:Tower_of_Hanoi-3.svg|miniatura|Triangle de Sierpinski obtingut de formar el graf de les configuracions possibles de discs.]]
El problema es pot resoldre de forma [[Iteració|iterativa]]. Concretament, pot ser resolt de la manera més eficient possible comptant en [[binari]] i associant el ritme d'aquest recompte a un ritme determinat de moviments dels discs.<ref>{{ref-publicació |cognom=Maziar |nom=Stepan |títol=Solution of the Tower of Hanoi problem using a binary tree |publicació=ACM SIGPLAN Notices |data=1985 |doi=https://doi.org/10.1145/988327.988330}}</ref> Per fer-ho, es comença comptant des de 0, i s'associa un valor ordenat a cada disc, essent el més petit 0. Sempre que en continuar el recompte només es giri aquest darrer bit de 0 a 1, es mou el disc 0 d'una clavilla cap a la dreta. Si ja estava a la clavilla de més la dreta, es retorna a la primera clavilla. Si el bit de la següent posició canvia de 0 a 1, és el disc 1 el que es mou seguint la mateixa pauta, i així successivament.
El trencaclosques té una versió restringida segons la qual els discs només es poden moure a la clavilla adjacent;<ref>{{ref-publicació |cognom1=Allouche |cognom2=Sapir |nom1=Jean-Paul |nom2=Amir |títol=Restricted Towers of Hanoi and morphisms |publicació=CNRS, LRI, Université París Sud |data=2004 |url=https://webusers.imj-prg.fr/~jean-paul.allouche/allsap.pdf |consulta=15 gener 2021}}</ref> aquesta versió pot ser resolta de manera similar a la d'abans, però utilitzant una [[Sistema ternari|base ternària]]. Aquesta solució no només és la més eficient, sinó que passa per cada possible configuració vàlida per aquell nombre de discs una vegada.
Si es crea un [[Graf (matemàtiques)|graf]] amb totes les possibles configuracions de discs connectades quan el moviment d'una a l'altra és vàlid en la versió no restringida, s'obté el [[triangle de Sierpinski]].<ref>{{citation | last1 = Hinz | first1 = Andreas M. | last2 = Klavžar | first2 = Sandi | last3 = Petr | first3 = Ciril | contribution = 2.3 Hanoi Graphs | doi = 10.1007/978-3-319-73779-9 | edition = 2nd | isbn = 978-3-319-73778-2 | location = Cham | mr = 3791459 | page = 120 | publisher = Birkhäuser | title = The tower of Hanoi—myths and maths | title-link = The Tower of Hanoi – Myths and Maths | year = 2018}}</ref> El mètode de recompte ternari que permet passar per cada possible configuració un cop, correspon a la [[Corba de Sierpiński#Corba de punta de fletxa de Sierpiński|corba de punta de fletxa de Sierpinski]].<ref>{{citation | last1 = Hinz | first1 = Andreas M. | last2 = Parisse | first2 = Daniele | doi = 10.1016/S0723-0869(02)80023-8 | issue = 3 | journal = Expositiones Mathematicae | mr = 1924112 | pages = 263–268 | title = On the planarity of Hanoi graphs | volume = 20 | year = 2002}}</ref>
== Implementació en informàtica ==
| |||