Estrategias. Las torres de Hanoi.

Jul 30, 2008 Codigos C# Tutoriales C# 22 comentarios

Como lo prometido es deuda, empezaremos esta segunda parte del minicurso de Recursividad en C# con el clásico Hanoi, y luego hablaremos sobre algunas técnicas asociadas al uso de la recursividad, como son “Backtracking” y “Divide y Vencerás”. Además, resolveremos paso a paso varios de los clásicos problemas de recursividad.

hanoi3 161x300 Estrategias. Las torres de Hanoi. Según mi profesor de programación (Dr. Miguel Katrib), el juego de las torres de Hanoi es el poder expresivo de la Recursividad, y creo no hay mejor ejemplo que este para empezar a comprender como verdaderamente funciona la recursividad en C#.

El juego consiste en ir moviendo discos de la torre original de la izquierda de modo tal que finalmente queden en la misma posición en la torre de la derecha. Los movimientos de los discos deben hacerse bajo las siguientes restricciones: solo podrá moverse un disco a la vez y nunca podrá ubicarse un disco de mayor diametro sobre uno de menor diametro. La torre del centro puede utilizarse de modo auxiliar para el traspaso de los discos.

En la imagen de la derecha se muestran los movimientos a realizar para mover 3 discos. ¡Imaginen ahora la cantidad de movimientos a realizar para mover 10 discos! Lo que se quiere es un algoritmo que nos diga los movimientos a efectuar para mover una cantidad “n” de discos.

Analicemos ahora el problema:

1- Si la cantidad de discos a mover es 1, entonces movemos el disco de la torre de origen a la torre de destino.
2- Supongamos que sabemos mover n-1 discos desde la torre de origen hasta la torre auxiliar del centro.
3- El tercer paso consiste en mover el disco mayor que ha quedado solo en la torre izquierda hacia la torre de destino.
4- Mover esos n -1 discos desde la torre auxiliar (que hace de origen) hacia la torre de la derecha.

¿Cómo sabemos mover n-1 discos?

Como se podrá notar, este algoritmo se utiliza a si mismo y está basado en el principio de inducción matemática. Además, si no cree que podamos mover n-1 discos, entonces veamos si podemos mover n-2 discos, si tampoco lo cree podemos seguir hasta que tengamos que suponer que sabemos mover 1 disco, lo cual es cierto.

El método Mover a continuación escribirá como salida los movimientos a realizar para mover una cierta cantidad de discos que se le indica como primer parámetro. Los restantes parámetros serían los nombres de las torres de origen, auxiliar y destino.

code1 Estrategias. Las torres de Hanoi.

De modo que cuando haríamos algo como:

code2 Estrategias. Las torres de Hanoi.

La salida sería:

code3 Estrategias. Las torres de Hanoi.

Seguro notaste que cada vez que se hace una llamada recursiva, la cantidad de discos que se pasa como primer parámetro disminuye en 1. De modo que en algún momento la cantidad de discos será 1, y entonces ya no se hará más ninguna llamada recursiva y el método Mover sabrá retornar a quién lo llamó.

Es C# quien lleva todo este proceso de saber como regresar y quien garantiza que los parámetros tengan los mismos valores que tenían antes de haberse hecho la llamada. Si todavía desconfía del trabajo recursivo, intente manualmente seguir el rastro de una llamada original a mover 4 discos.

Estrategia de “Divide y Vencerás”

Una estrategia importante en la recursividad es la llamada “Divide y Vencerás”. La implementación de soluciones basadas en esta estrategia no sería posible sin la recursividad. Dar un concepto de esta técnica o estrategia no es tan complicado. Primero veamos un ejemplo.

Busqueda Binaria

Considere que los elementos de un array de números enteros están ordenados de menor a mayor, por ejemplo {2, 3, 5, 7, 9, 12, 15, 18, 20}. Se quiere saber si el elemento 17 está en el array.

Lo que haremos será buscar el elemento que está en la mitad del array (9 en este caso). Si el elemento que buscamos es igual a este, hemos terminado. De lo contrario, como los elementos del array están ordenados, si el elemento buscado es mayor que el del medio, buscamos a la derecha, si es menor, a la izquierda. En este caso 17 es mayor que 9, y por tanto hay que buscar en {12, 15, 18, 20}. Ahora hacemos lo mismo, en este caso, hay que tomar una decisión, ya que como la cantidad de elementos es par, hay que ver si tomamos como el elemento del centro, el de más a la izquierda o el de más a la derecha (el 15 o el 18). Por ahora lo haremos con el que esté en el centro más a la izquierda (el 15). Como 17 es mayor que 15 buscaremos entonces en {18, 20}. El del medio es el 18. Y como el 18 es mayor que 17, entonces buscaremos en {18}. El elemento medio es el propio 18 que no es igual a 17. Como ya no se puede seguir haciendo subdivisiones, entonces podemos concluir que 17 no está en el array.

Por lo que el código sería el siguiente:

code4 Estrategias. Las torres de Hanoi.
Note como, además de cumplir las 4 reglas de la recursividad, el método recursivo contiene dos llamadas recursivas que se aplican a dos posibles “divisiones” del problema original. Generalmente se considera que los algoritmos que contienen más de dos llamadas recursivas son algoritmos de “Divide y Vencerás”.

Podemos resumir entonces que esta estrategia consta de dos partes.

1- La división. Es donde el problema se divide en problemas más pequeños que a su vez re resuelven recursivamente.
2- La solución del problema original se forma a partir de estos problemas más pequeños.

Hasta aquí la segunda entrega de este tutorial sobre recursividad. De seguro, tienen un poco de dolor de cabeza.

En la tercera parte estaremos hablando de Backtracking (Vuelta atrás), y resolveremos otros problemas asociados con esta otra herramienta de la recursividad.

Para practicar con la estrategia “Divide y Vencerás”, pueden intentar hacer el algoritmo de “Ordenación por mezcla” (Mergesort) recursivo y “Subsecuencia continua de mayor suma”. Trataré de colgar las respuestas de estos algoritmos un poco más adelante.

Si tienen alguna duda o no entienden algo, deje su comentario.

Compartir:

22 comentarios

Forma parte de nuestra discusión y síguela de cerca

Hola que tal, necesito saver como hacer el Hanoi con con un solo codigo fuente utlizando pilas por sierto y que yo de n=* y lo haga…. no tengo idea de como hacerlo y lo necesito en visual por cierto!!

Autor: socieboy | Fecha: Oct 8, 2008.

Hola, como estas?, necesito saber si me puedes ayudar urgentemente en un trabajo sobre recursividad para la universidad! lo tengo que entregar luego y quisiera saber si me puedes responder a mi mail lo antes posible.. asi te puedo mandar el enunciado sobre lo que me piden hacer y el program.cs de lo que llevo. gracias!

Autor: Jorge Preisler | Fecha: Oct 21, 2008.

socieboy, estoy trabajando en lo del Hanoi con pilas, tal vez mañana lo publique, pero tengo mucho trabajo y cosas de la escuela.

Jorge, te envié un email. Puedes mandarme lo que tienes hecho del proyecto a ver si busco algo de tiempo para ayudarte en lo que pueda.

Un saludo, y pasen por aquí a cada rato.

Autor: admin | Fecha: Oct 24, 2008.

hola, yo tengo una peticion parecida a la de jorge. ojala me puedas ayudar xD. t dejo mi correo

Autor: panchulo | Fecha: May 30, 2009.

hola! me podrias ayudar con un trabajo pliss??
si no es mucha la molestia

de antemano gracias
saludos

Autor: Rosana | Fecha: May 30, 2009.

Rosana y panchulo, en verdad no tengo tiempo para resolver problemas o trabajos un poco extensos, además, no sería muy buena práctica. Lo ideal sería que tuvieran una parte del ejercicio hecho y yo los ayudo en alguna duda específica.

Autor: admin | Fecha: Jun 5, 2009.

tomas mi hermano jaja felicidades por tu sitio, sube el ejercicio de recursividad DESCOMPON EN SUMANDOS, ese me gusta cantidad ademas esta bueno, dale cuidate mi herma

Autor: Paulo | Fecha: Jun 8, 2009.

Hola, gracias por tus post, pero para comentarte que ni copiando al pie de la letra el código de HANOI, me sale que puedo estar haciendo mal, pues veo que simpre utilizan el mismo algoritmo en todas partes.

static void Main(string[] args)
{
int n = 3;
hanoi(n, “Izquierda”, “Centro”, “Derecha”);
Console.ReadLine();

}
static void hanoi(int num_discos, string org, string aux, string dest)
{
if (num_discos == 1)
Console.WriteLine(“{0} -> {1}”, org, dest);
else
{
hanoi(num_discos – 1, org, dest, aux);
Console.WriteLine(“{0} -> {1}”, org, dest);
hanoi(num_discos – 1, aux, dest, org);
}

}
Ahy te dejo el código si alguien o tu ves algo raro ayuda porfa

Autor: Ingphillip | Fecha: Nov 15, 2009.

que pena ya encontre el error jejej soy my nivatis

Autor: Ingphillip | Fecha: Nov 16, 2009.

Que buena la pagina, busque mucho en la web una pagina como esta, que te muestre con ejemplos claros y no te hablen de cosas que solo te hacen confundir, Felicitaciones por la pagina, sigan adelante Saludos

Autor: Nilo | Fecha: Jul 28, 2010.

[...] Recursividad con C# 2da parte Recursividad con C# 3ra parte Compartir:EmailImprimirCompartirRedditDiggPublicar esto [...]

Autor: Recursividad con C#. Ejercicios resueltos | puntopeek | Fecha: Oct 1, 2010.

Muy buena esta pagina, nunca habia visto que explicaran asi, ademas de los ejemplos…… Buenisiimoo

Gracias por tu ayuda

Autor: SkaLoRe | Fecha: Oct 18, 2010.

Hola a todos, la duda mia es la siguiente…
En la escuela me mandaron un ejercicio de las torres de hanoi pero unas restricciones, les explico:
Me dicen q no puedo ir de la torre A directo a la torre C, es decir para 2 discos la solucion no seria 3, seria 8, asi queda…
mover de 1 a 2
mover de 2 a 3
mover de 1 a 2
mover de 3 a 2
mover de 2 a 1
mover de 2 a 3
mover de 1 a 2
mover de 2 a 3
no encuentro via de resolverlo… en si lo q estoy buscando una formula para saber la cantidad de movimientos q es lo q me piden…
otro ejemplo q me dan es con 7 discos, q en el original se hace con 127 mov, en este se hace con 2186 mov.
Plis agradezco cualquier ayuda…

Autor: JROC | Fecha: Ene 21, 2012.

@jROC: Ese problema no son las torres de Hanoi ;) lo que buscas es una fórmula de recurrencia, no se si habrás oido hablar de ellas, una de las más famosas es la de Fibonacci, ahora mismo no me puedo poner a resolver este problema, pero seguro en Google hay bastante info.

Autor: Tomy | Fecha: Ene 22, 2012.

vos fijate que si podes poner el programa completo pero qu no sea muy avanzado (la simulacion de 8 discos) te lo agradesco

Autor: alguien | Fecha: Mar 14, 2012.

@alguien, eso está un poco complicado, pero veremos que se puede hacer… por ahi hay algunas simulaciones en applets de Java.

Autor: Tomy | Fecha: Mar 23, 2012.

Hola, como podria quedar una formula para solucionar el juego con 5 torres y 11 fichas.

Autor: granada | Fecha: May 18, 2012.

a y como podría relacionarlo con el ábaco.

Autor: granada | Fecha: May 18, 2012.

Hola, como esta buenas noches necesito saber si me puedes ayudar urgentemente en un trabajo sobre recursividad para la universidad! lo tengo que entregar luego y quisiera saber si me puedes responder a mi mail lo antes posible.. asi te puedo mandar el enunciado sobre lo que me piden hacer y el program.cs de lo que llevo. gracias
me madaron en visual studio 2008 en c# quiero que me indiques de todos los discos del 3 al disco 8 por favor y me mades enseguida

Autor: karolina lopez | Fecha: Jun 12, 2012.

Excelente Tomas justo lo que andaba buscando…

Autor: Eugenio | Fecha: Nov 17, 2012.

porfa quisiera saber si tienes el codigo fuente del problema de las 8 reynas de recursividad y de la salida de un laberiento en c# en modo consola espero tu respuesta seria realmente agradecido de su parte

Autor: jose | Fecha: Ene 13, 2014.

@jose: Hace un tiempo escribí un post sobre las 8 reinas y la salida del laberinto, aqui tienes el link: http://www.puntopeek.com/codigos-c/recursividad-con-c-3/

Autor: Tomy | Fecha: Feb 4, 2014.

Escribe tu comentario

Requerido.

Requerido. No público.

Si tienes alguno.