agosto 27, 2012

Las Torres de Hanoi


El siguiente pseudocódigo muestra el uso de una función recursiva para resolver el problema de las torres de Hanoi para cualquier número de anillos con tres torres, en este escenario se consideran tres anillos. Recordemos que las rutinas recursivas son aquellas que hacen llamadas a sí mismas y siempre deben tener un llamada inicial y una condición final.

En este ejemplo la llamada inicial a la rutina MoverAnillo es especificando el anillo mayor 3, la torre A Origen, la torre B Libre y la torre C Destino. En la primera llamada se volverá a llamar la rutina MoverAnillo pero ahora para el anillo 2 e intercambiando las torres Destino y Libre, y así recursivamente hasta llegar al anillo más chico, el 1. Al llegar al anillo 0 se se alcanza la condición final y regresa el control a cada una de las llamadas anteriores en perfecto orden inverso.

Ahora sí, el anillo 1 se mueve de la torre Origen al Destino, y el anillo 2 del Origen al Libre y así sucesivamente hasta que todos los anillos quedan en la torre origen. Para tres anillos se requieren siete movimientos: A => C , A => B , C => B , A => C , B => A , B => C , A => C

MoverAnillo(3, A, B, C)

RUTINA MoverAnillo(Anillo, Origen, Libre, Destino)
   SI Anillo es igual a 0 ENTONCES
         SIN movimiento
      SINO ENTONCES
         MoverAnillo(Anillo-1, Origen, Destino, Libre)
         MOVER Disco de Origen a Destino
         MoverAnillo(Anillo-1, Libre, Origen, Destino)
      FIN SI
   FIN RUTINA



No hay comentarios:

Publicar un comentario en la entrada