eo eo eo pt eo eo eo eo eo eo eo eo zh zh zh zh zh zh zh zh eo eo eo eo eo eo eo eo lt eo eo eo eo de es eo eo eo eo eo sv ur eo eo eo eo es eo eo eo eo eo eo eo eo tr fi eo eo it eo eo eo eo eo eo eo eo eo eo eo eo ar bg bn ca hbs_lat da de en es eu fa fi fr he hi hu hy id is it ja ko lb nl nb pa pl pt ro ru sl sq hbs_lat sv th tr fy ur vi zh eo eo eo eo eo eo eo eo eo
Turoj de Hanojo - Vikipedio
El Vikipedio, la libera enciklopedio
La turoj de Hanojo estas logika enigmo. Ĝi postulas transmeti konuso-forman turon el rondaj diskoj al alia loko sub jenaj kondiĉoj:
ekzistas krom la komenca kaj fina lokoj de la turo nur unu libera loko, kie eblas "parki" diskojn
en ĉiu movo eblas transmeti nur la plej supran diskon de iu turo
eblas meti diskon nur sur pli grandan diskon
La ludon inventis verŝajne la franca matematikisto Edouard Lucas en 1883. Li prezentis la (fikcian) historion, ke barataj monaĥoj en Benares laboras pri la transmetado de 64-diska turo laŭ tiuj reguloj; post sukcesa transmeto la mondo finiĝos. La ironio de la historio estas, ke la transmetado de n-diska turo postulas 2n−1 movojn. 64-diska turo do postulas 18.446.744.073.709.551.615 movojn. Farante unu movon en sekundo oni bezonus preskaŭ 585 miliardojn da jaroj. (Oni taksas la ĝisnunan aĝon de la universo je 13–20 miliardoj da jaroj.)
La algoritmo por transmetado estas simpla: Por transmeti turon de unu disko oni simple transmetas tiun diskon. Por transmeti n-diskan turon oni transmetas ĝian (n−1)-diskan supron al la inter-loko, la bazan diskon al la fina loko kaj la "parkitan" turon sur tiun bazan diskon. El tio sekvas, ke ĉe turo el para nombro da diskoj necesas meti la unuan (supran) diskon sur la inter-lokon, ĉe malpara nombro sur la finan lokon.
Laŭ tiu algoritmo rezultas, ke (ĝis tur-alto de tri) disko ripozas ĉiam sur la senpere pli granda disko aŭ sur iu bazloko. Kvankam oni emas supozi, ke per devio de tiu "regulo" eblas plirapidigi la procezon, ne estas tiel. (Se ekzistas pli ol unu libera inter-loko, la problemo komplikiĝas.) Ekzemplo de turo kun tri diskoj (sep movoj):
X XXX XXXXX -------___-------___-------
XXX XXXXX X -------___-------___-------
XXXXX XXX X -------___-------___-------
X XXXXX XXX -------___-------___-------
X XXX XXXXX -------___-------___-------
X XXX XXXXX -------___-------___-------
XXX X XXXXX -------___-------___-------
X XXX XXXXX -------___-------___-------
Vivaj ekzemploj[redakti | redakti fonton]
Turo el tri diskoj[redakti | redakti fonton]
Turo el kvar diskoj[redakti | redakti fonton]
Turoj de Hanojo en la Vikimedia Komunejo (Multrimedaj datumoj)
Kategorio Turoj de Hanojo en la Vikimedia Komunejo (Multrimedaj datumoj)
Informoj pri la paĝo
Citi ĉi tiun artikolon
Ĉi tiu paĝo estis lastafoje redaktita je 03:30, 15 dec. 2015.
La teksto disponeblas laŭ la permesilo Krea Komunaĵo Atribuite-Samkondiĉe 3.0 Neadaptita; eble aldonaj kondiĉoj aplikeblas. Vidu la uzkondiĉojn por detaloj.
Regularo pri respekto de la privateco
Vidigo por porteblaj aparatoj