Primero diré que cualquier pregunta que comience con “Soy demasiado estúpido” es la manera incorrecta de responder la pregunta. Es una forma de buscar una ruta de escape en lugar de llegar a la raíz del problema. Entonces, en lugar de culpar del malentendido a la incapacidad de comprender los conceptos de CS, intente dividir el problema en porciones más pequeñas y hacer preguntas bien definidas para ver qué es lo que lo está tropezando.
Mencionas el problema de las Torres de Hanoi. Antes de hablar sobre hacer esto de manera recursiva, la primera pregunta es entender qué está pasando a un nivel básico. Aquí están las reglas del juego (de la Torre de Hanoi):
El rompecabezas comienza con los discos en una pila ordenada en orden ascendente de tamaño en una varilla, la más pequeña en la parte superior, formando así una forma cónica. El objetivo del rompecabezas es mover toda la pila a otra barra, obedeciendo las siguientes reglas simples:
- ¿Qué es la normalización en el aprendizaje automático?
- ¿Existe una definición matemática o algorítmica de sobreajuste? ¿Hay documentos detallados que definan primero el sobreajuste?
- ¿Qué debo hacer durante el verano antes de mi segundo año como estudiante de informática?
- ¿Qué conocimiento matemático debe tener un estudiante de informática?
- ¿Cómo se puede hacer un chip secuencial solo con chips combinacionales?
- Solo se puede mover un disco a la vez.
- Cada movimiento consiste en tomar el disco superior de una de las pilas
y colocarlo encima de otra pila, es decir, un disco solo se puede mover si
Es el disco superior de una pila. - No se puede colocar ningún disco encima de un disco más pequeño.
Primera pregunta, ¿entiendes estas reglas? Entonces, digamos que tengo las tres pilas a continuación (con Small <Middle <Big).
Paso 0:
Torre 1 = [Grande, Medio, Pequeño]
Torre 2 = []
Torre 3 = []
Puede visualizar estas “pilas” como las torres, donde el último elemento de la pila se puede mover sin mover ningún otro elemento. No podemos mover otro elemento en la pila porque si quisiéramos mover el elemento Medio, no podríamos llegar a él en la torre sin mover primero el elemento Pequeño.
¿Entiendes cómo funcionan las pilas? De lo contrario, puede leer más sobre la estructura de datos de pila, que es un concepto en el que se basa (pila (tipo de datos abstractos)).
¿Cuáles son los movimientos legales de este primer estado? Ya he notado que el único elemento que podemos mover es el elemento Pequeño. Podemos colocar este elemento en la Pila 2 o en la Pila 3. Supongamos que elegimos arbitrariamente ponerlo en la pila 2. La configuración sería entonces
Paso 1:
Torre 1 = [Grande, Medio]
Torre 2 = [Pequeña]
Torre 3 = []
Ahora tenemos dos opciones, podríamos mover Small nuevamente, o podríamos mover el elemento Middle. Dado que mover Small solo nos llevaría a un estado al que podríamos haber llegado antes, mover el elemento Middle parece más interesante.
Pero, ¿dónde podríamos movernos al medio? Si tratamos de mover el Medio a la Torre 2, entonces tendría Medio en la parte superior de Pequeño, pero la regla 3 establece que “no se puede colocar ningún disco encima de un disco más pequeño”, y dado que Pequeño <Medio, Medio no se puede colocar en parte superior de (o después) Pequeño. Entonces, el único lugar donde podemos mover el Medio es a la Torre 3. Esto proporciona la siguiente configuración.
Paso 2:
Torre 1 = [Grande]
Torre 2 = [Pequeña]
Torre 3 = [Medio]
Ahora podemos mover el elemento pequeño o el elemento medio. Si tratamos de mover el elemento Medio, solo podríamos moverlo de regreso a la Torre 1, de donde lo sacamos. Como tenemos otras opciones, veamos qué sucede cuando movemos el elemento Pequeño.
Como Pequeño <Medio y Pequeño <Grande, Pequeño puede ir encima de la Torre 1 o la Torre 3. Como nuestro objetivo es eventualmente mover el elemento Grande, nos gustaría mantenerlo vacío, así que intentemos mover Pequeño a la Torre 3 .
Paso 3:
Torre 1 = [Grande]
Torre 2 = []
Torre 3 = [Medio, Pequeño]
Ahora podemos mover el elemento Big a una nueva torre simplemente colocándolo en la Torre 2.
Etapa 4:
Torre 1 = []
Torre 2 = [Grande]
Torre 3 = [Medio, Pequeño]
Nuestro objetivo ahora es reconstruir la torre en la Torre dos donde hemos colocado Big. Para hacer esto, necesitamos poder movernos al medio. Pero antes de que podamos hacer esto, tenemos que mover Small ya que Small está en la parte superior de la Torre 3 (donde está Middle). Como la Torre 1 ahora está vacía, podemos mover Small a la Torre 1.
Paso 5:
Torre 1 = [Pequeña]
Torre 2 = [Grande]
Torre 3 = [Medio]
Ahora tenemos acceso a Middle y podemos ponerlo encima de la torre 2.
Paso 6:
Torre 1 = [Pequeña]
Torre 2 = [Grande, Medio]
Torre 3 = []
Ahora solo necesitamos mover Small a la parte superior de la Torre 2 para haber movido toda la torre usando solo movimientos legítimos.
Paso 7:
Torre 1 = []
Torre 2 = [Grande, Medio, Pequeño]
Torre 3 = []
¿Entonces le preguntaré si entendió este desglose del problema en sí? Si no, ¿dónde fue su desglose? Tenga en cuenta que si bien hay conceptos de CS en los que se basa esto, todavía no estamos haciendo cosas de CS, así que no piense que si tuvo un problema para entender esto (especialmente si tenía preguntas como “por qué”) no puede entender CS. Si esto le está causando problemas, le recomiendo hacer más ejemplos y jugar más con este concepto.
La pregunta importante sobre este problema es ¿ves algún patrón aquí? Y si no lo haces inicialmente, está bien. Se necesita tiempo para reconocer patrones. Pero observe que en el Paso 4, teníamos una configuración de Torre 1 = [], Torre 2 = [Grande] y Torre 3 = [Medio, Pequeño]. Esta es una estrategia general que intenta hacer en Towers of Hanoi, su objetivo con n elementos es tratar de llegar a una configuración donde tenga la Torre 1 = [], la Torre 2 = [n] y la Torre 3 = [n- 1, n-2, …, 1]. Entonces simplemente necesitamos mover los elementos n-1 a la Torre 2.
Entonces, usando otra palabra CS, se puede pensar en este problema * recursivamente * porque el problema de mover n elementos de la torre 1 a la torre 2 implica mover n-1 elementos a la torre 3, un elemento a la torre 2, y luego n-1 elementos a la torre 2.
También le recomiendo que visite Preguntas frecuentes sobre el Dr. Math: Torre de Hanoi para obtener ayuda adicional sobre este problema.
