Simulación de las estructura de datos dinámicas

1. Consulte qué son las torres de Hanoi y exponga brevemente cuál de las estructuras dinámicas utilizará para simular su su comportamiento.

R// Las Torres de Hanói es un rompecabezas o juego matemático inventado en 1883 por el matemático francés Édouard Lucas.¹​ Este juego de mesa individual consiste en un número de discos perforados de radio creciente que se apilan insertándose en uno de los tres postes fijados a un tablero. El objetivo del juego es trasladar la pila a otro de los postes siguiendo ciertas reglas, como que no se puede colocar un disco más grande encima de un disco más pequeño. El problema es muy conocido en la ciencia de la computación y aparece en muchos libros de texto como introducción a la teoría de algoritmos.

La fórmula para encontrar el número de movimientos necesarios para transferir n discos desde un poste a otro es: 2ⁿ - 1

Torres de Hanoi. Te dan un conjunto de tres varillas y nnn discos, con cada disco de un tamaño diferente. Llamemos a las varillas A, B y C, y numeremos los discos desde 1, el disco más pequeño, hasta nnn, el disco más grande. Al principio, todos los nnn discos están en la varilla A, en orden de tamaño decreciente de la parte inferior a la parte superior, de modo que el disco nnn está en la parte inferior y el disco 1 está en la parte superior. Aquí está cómo se ven las Torres de Hanoi para n = 5n=5n, equals, 5 discos:

El objetivo es pasar todos los nnn discos de la varilla A a la varilla B:

¿Suena fácil, verdad? No es tan sencillo, porque tienes que obedecer dos reglas:

1.    Puedes mover solamente un disco a la vez.

2.    Ningún disco puede estar encima de un disco más pequeño. Por ejemplo, si el disco 3 está en una varilla, entonces todos los discos debajo del disco 3 deben tener números mayores que 3.

Puedes pensar que este problema no es terriblemente importante. ¡Al contrario! Cuenta la leyenda que en algún lugar de Asia (Tíbet, Vietnam, India; escoge en Internet qué leyenda te gusta), los monjes están resolviendo este problema con un conjunto de 64 discos y, según la historia, los monjes creen que una vez que terminen de mover todos los 64 discos de la varilla A a la varilla B de acuerdo con las dos reglas, el mundo se acabará. ¿Si los monjes están en lo correcto, deberíamos entrar en pánico?

Primero, vamos a ver cómo resolver el problema de manera recursiva. Vamos a empezar con un caso realmente sencillo: un disco, es decir, n = 1n=1n, equals, 1. El caso de n = 1n=1n, equals, 1 será nuestro caso base. Siempre puedes mover el disco 1 de la varilla A a la varilla B, porque sabes que cualquier disco debajo debe ser mayor. Y no hay nada especial acerca de las varillas A y B. Puedes mover el disco 1 de la varilla B a varilla C si lo deseas, o de la varilla C a la varilla A, o de cualquier varilla a cualquier varilla. Resolver el problema de las Torres de Hanoi con un disco es trivial, y requiere mover el único un disco solamente una vez.

¿Qué pasa con dos discos? ¿Cómo resuelves el problema cuando n = 2n=2n, equals, 2? Puedes hacerlo en tres pasos. Aquí está cómo se ve al principio:

Primero, mueve el disco 1 de la varilla A a la varilla C:

Observa que usamos la varilla C como una varilla libre, un lugar en donde poner el disco 1 para que podamos llegar al disco 2. Ahora que el disco 2 (el disco inferior) está expuesto, muévelo a la varilla B:

Por último, mueve el disco 1 de la varilla C a la varilla B:

Esta solución toma tres pasos, y una vez más no hay nada especial acerca de cómo mover los dos discos de la varilla A a la varilla B. Puedes moverlos de la varilla B a la varilla C al usar la varilla A como la varilla libre: mueve el disco 1 de la varilla B a la varilla A, luego mueve el disco 2 de la varilla B a la varilla C y termina por mover el disco 1 de la varilla A a la varilla C.  

A esta técnica la llamamos recursividad.

Para realizar la simulación es necesario seguir las siguientes reglas: 

Siempre que se llama al método: - Se apila con la dirección de retorno correspondiente - Nos ubicamos al inicio del método. Si terminamos el método: - Desapilamos - Regresamos a la dirección que desapilamos y seguimos trabajando con los datos ubicados en el tope de la pila. 

2. Observe el comportamiento de la fila frente a la taquilla de un banco y exponga brevemente cuál de las estructuras dinámicas utilizará para simular su su comportamiento.

R//: utilizará la estructura de "colas" o "colas de datos" 

Una Cola es una estructura de datos que sigue la Filosofía FIFO “Primero en entrar primero en salir”. Esto quiere decir que el elemento que entre primero a la Cola será el primero que salga y el último que entre será el último en salir. Por ejemplo, cuando vamos a un banco, 

pues cuando llegamos y lo primero que hacemos es tomar un turno, inmediatamente nos damos cuenta que ya había 10 personas primero que nosotros por lo que automáticamente deduces que ellos serán atendidos primero. Si nos damos cuenta en este escenario el primer cliente que llego y solicito un turno será el que sea atendido primero y nosotros que llegamos de último nos atenderán al final. 

3. Suponga que tiene dos fichas del juego de dominó debidamente conectadas así: el 2-3 con el 3-4 y necesita inserta las ficha 3-3 exponga brevemente cuál de las estructuras dinámicas utilizará para simular su su comportamiento.

R//: utilizaría la estructura de "listas", esta estructura se puede añadir elementos a cualquier posición 

en las que se puede añadir elementos en cualquier posición y obtenerlos o borrarlos de cualquier posición y obtenerlos o borrarlos de cualquier posición. en este caso la ficha 3-3 la puedo añadir entre la las fichas 2-3 y 3-4 porque la estructura me lo permite.