Matemáticas Discretas TC1003cb.mty.itesm.mx/tc1003/lecturas/tc1003-082.pdfHanoi Portada Links Solucion´ Recursión: Solución de Problemas Matemáticas Discretas - p. 2/7 Recursión:

Recursión: Solución de Problemas Matemáticas Discretas - p. 1/7

Matemáticas DiscretasTC1003

Recursión: Solución de ProblemasDepartamento de Matemáticas / Centro de Sistema Inteligentes

ITESM

HanoiPortadaLinksSolucion


Recursión: Las Torres de Hanoi

En 1883 el matemático fran-cés Édouard Lucas (4/april/1842-3/october/1891) inventó un rom-pecabezas que llamó Las Torresde Hanoi.




En 1883 el matemático fran-cés Édouard Lucas (4/april/1842-3/october/1891) inventó un rom-pecabezas que llamó Las Torresde Hanoi. El juego consistía deocho discos de madera con hoyosen su centro, los cuales se apila-ban en tamaño decreciente en unposte en una fila de tres postes.




En 1883 el matemático fran-cés Édouard Lucas (4/april/1842-3/october/1891) inventó un rom-pecabezas que llamó Las Torresde Hanoi. El juego consistía deocho discos de madera con hoyosen su centro, los cuales se apila-ban en tamaño decreciente en unposte en una fila de tres postes.




En 1883 el matemático fran-cés Édouard Lucas (4/april/1842-3/october/1891) inventó un rom-pecabezas que llamó Las Torresde Hanoi. El juego consistía deocho discos de madera con hoyosen su centro, los cuales se apila-ban en tamaño decreciente en unposte en una fila de tres postes. Eljugador debería cambiar todos losdiscos de un poste a otro,




En 1883 el matemático fran-cés Édouard Lucas (4/april/1842-3/october/1891) inventó un rom-pecabezas que llamó Las Torresde Hanoi. El juego consistía deocho discos de madera con hoyosen su centro, los cuales se apila-ban en tamaño decreciente en unposte en una fila de tres postes. Eljugador debería cambiar todos losdiscos de un poste a otro, siempremoviendo de uno en uno y




En 1883 el matemático fran-cés Édouard Lucas (4/april/1842-3/october/1891) inventó un rom-pecabezas que llamó Las Torresde Hanoi. El juego consistía deocho discos de madera con hoyosen su centro, los cuales se apila-ban en tamaño decreciente en unposte en una fila de tres postes. Eljugador debería cambiar todos losdiscos de un poste a otro, siempremoviendo de uno en uno y nun-ca apilando un disco sobre otro demenor tamaño.



Las Torres de Hanoi: Portada Juego

THE TOWER OFHANOÏ

AUTHENTIC BRAINTEASER OF THE

ANAMITES

A GAME BROUGHTBACK FROM

TONKIN

BY PROFESSOR N.CLAUS (OF SIAM)

Mandarin of theCollege of

Li-Sou-Stian!



Las Torres de Hanoi: Links

■ Un applet en:http://www.mazeworks.com/hanoi/

■ Un juego interactivo en:http://www.ability.org.uk/tower.html

■ Información:http://www.cut-the-knot.org/recurrence/hanoi.shtml



Las Torres de Hanoi: Solución

Suponga 3 postes:




Suponga 3 postes:■ Poste origen: donde se encuentran ahora los

discos.





discos.■ Poste meta: donde se deberán colocar los

discos.






discos.■ Poste auxiliar: donde se pueden hacer

movimientos.






discos.■ Poste auxiliar: donde se pueden hacer

movimientos.



Caso BaseSi hay un sólo disco (n=1) sólo colóquelo en enposte meta.



Caso BaseSi hay un sólo disco (n=1) sólo colóquelo en enposte meta.Paso InductivoSuponga un pilar con k + 1 discos en un poste“origen” y que se desean colocar en el poste“meta”.



Caso BaseSi hay un sólo disco (n=1) sólo colóquelo en enposte meta.Paso InductivoSuponga un pilar con k + 1 discos en un poste“origen” y que se desean colocar en el poste“meta”. Suponga también que se tiene una formade colocar k discos de un poste cualquiera a otroposte cualquiera usando un poste auxiliar paramovimientos (Hipótesis Inductiva).



Caso BaseSi hay un sólo disco (n=1) sólo colóquelo en enposte meta.Paso InductivoSuponga un pilar con k + 1 discos en un poste“origen” y que se desean colocar en el poste“meta”. Suponga también que se tiene una formade colocar k discos de un poste cualquiera a otroposte cualquiera usando un poste auxiliar paramovimientos (Hipótesis Inductiva). Entonces unaestrategia de solución será:



Caso BaseSi hay un sólo disco (n=1) sólo colóquelo en enposte meta.Paso InductivoSuponga un pilar con k + 1 discos en un poste“origen” y que se desean colocar en el poste“meta”. Suponga también que se tiene una formade colocar k discos de un poste cualquiera a otroposte cualquiera usando un poste auxiliar paramovimientos (Hipótesis Inductiva). Entonces unaestrategia de solución será:■ Mover los k primeros discos del poste origen al poste auxiliar con

el proceso solución dado en la hipótesis inductiva,





■ Una vez liberado el disco k + 1, moverlo del poste origen al postemeta, y





■ Una vez liberado el disco k + 1, moverlo del poste origen al postemeta, y

■ Mover los k discos del poste auxiliar al poste meta con el procesode la hipótesis inductiva.



Hanoi( n, origen, distino, auxiliar)if (n == 1) then

printf(“Disco %d: de %da %d\n”,1,origen,destino);else

Hanoi(n-1,origen,auxiliar,destino);printf(“Disco %d: de %d

a %d\n”,n,origen,destino);Hanoi(n-1,auxiliar,destino,origen);

end if







end ifEjecutar

Hanoi(8,1,2,3)







end ifEjecutar

Hanoi(8,1,2,3)

¿¿Total de movimientos para mover n discos??







end ifEjecutar

Hanoi(8,1,2,3)

¿¿Total de movimientos para mover n discos??

a1 = 1, y ak+1 = ak + 1 + ak = 2 ak + 1

Documents

Matemáticas Discretas TC1003cb.mty.itesm.mx/tc1003/lecturas/tc1003-082.pdfHanoi Portada Links Solucion´ Recursión: Solución de Problemas Matemáticas Discretas - p. 2/7 Recursión: