[SER222] Recurrences (3/7): Solving Towers of Hanoi
Summary
TLDREl video explica el algoritmo para resolver el problema de las Torres de Hanoi. Se discute la estrategia de mover los discos más pequeños primero, luego los más grandes y finalmente los restantes más pequeños. Se presenta el pseudocódigo para resolver el rompecabezas con 'n' discos, incluyendo la función 'move' para trasladar un disco de un poste a otro. El vídeo detalla los pasos del algoritmo: mover 'n-1' discos al poste temporal, trasladar el disco más grande al poste final y, por último, mover los 'n-1' discos restantes al poste final. La explicación termina con la pregunta de cuántas movimientos se necesitan para resolver el rompecabezas.
Takeaways
- 🧩 El algoritmo de Torres de Hanoi resuelve el problema mediante la descomposición en subproblemas más pequeños.
- 📜 El pseudo código dado tiene cuatro parámetros: Start (inicio), Temp (temporal), End (final) y n (tamaño de la torre).
- ⚙️ Move es una función encapsulada que realiza la operación básica de mover un disco de una varilla a otra.
- 🧱 El caso base ocurre cuando n es igual a 1, lo que significa que solo hay un disco para mover, resolviéndose sin recurrencia.
- 🔁 Para n mayor que 1, se necesita aplicar tres pasos que involucran la recursividad para mover los discos.
- 🔀 Primero, se mueve el subgrupo de discos n-1 desde Start a Temp usando End como espacio temporal.
- ➡️ Luego, el disco más grande se mueve de Start a End directamente.
- 🔄 Finalmente, se mueve el subgrupo de discos n-1 desde Temp a End para completar el problema.
- 🎯 El algoritmo sigue tres pasos principales: mover una torre pequeña, mover el disco más grande, y mover la torre pequeña nuevamente.
- ⏱️ Al final, la solución busca determinar cuántos movimientos requiere este método para resolver el problema completo.
Q & A
¿Cuál es el propósito del algoritmo de las Torres de Hanói presentado en el video?
-El propósito del algoritmo es resolver el problema de las Torres de Hanói para una cantidad 'n' de discos, moviéndolos de una torre inicial a una torre final utilizando una torre temporal.
¿Qué representa la variable 'n' en el pseudocódigo?
-'n' representa el tamaño de la torre, es decir, el número de discos que se desea mover de la torre inicial a la torre final.
¿Qué sucede cuando 'n' es igual a 1 en el pseudocódigo?
-Cuando 'n' es igual a 1, el problema se reduce a un caso base, donde solo se necesita mover un disco directamente de la torre inicial a la torre final sin necesidad de recurrir a más pasos.
¿Cuáles son los cuatro parámetros principales en el pseudocódigo?
-Los cuatro parámetros son: 'Start', la torre de inicio; 'Temp', la torre temporal; 'End', la torre final; y 'n', que indica el número de discos en la torre.
¿Cuál es el rol de la torre temporal en la solución?
-La torre temporal ('Temp') se utiliza como espacio intermedio para mover discos mientras se transfiere el resto desde la torre inicial a la torre final.
¿Qué representa la función 'move' en el algoritmo?
-La función 'move' encapsula la acción de mover un disco de una torre a otra. Es una operación básica dentro del algoritmo.
¿Cómo se divide el problema cuando 'n' es mayor que 1?
-Cuando 'n' es mayor que 1, el problema se divide en tres pasos: primero, mover 'n-1' discos de la torre inicial a la torre temporal; luego, mover el disco más grande a la torre final; y finalmente, mover los 'n-1' discos desde la torre temporal a la torre final.
¿Qué acción se realiza después de mover el disco más grande a la torre final?
-Después de mover el disco más grande a la torre final, se mueve la torre de tamaño 'n-1' que estaba en la torre temporal a la torre final.
¿Cuántos movimientos realiza el algoritmo para resolver el problema?
-El número total de movimientos realizados por el algoritmo depende de la cantidad de discos 'n'. El video plantea esta pregunta, pero no proporciona una respuesta exacta en este momento.
¿Por qué es importante el uso de la recursión en el algoritmo?
-La recursión es crucial en el algoritmo porque permite descomponer el problema en subproblemas más pequeños, moviendo torres parciales de discos hasta que se alcanza el caso base con 'n=1'.
Outlines
🔍 Introducción a la solución del problema de las Torres de Hanoi
Ruben Acuña presenta el tema del video: la solución algorítmica para el problema de las Torres de Hanoi. Se refiere al concepto general de mover torres más pequeñas, luego discos más grandes, y finalmente una torre más pequeña para resolver el rompecabezas. También introduce el pseudocódigo que explica cómo resolver el problema para un número 'n' de discos y menciona que los movimientos entre varillas ya están modelados en una estructura de datos preexistente.
📜 Explicación del pseudocódigo para las Torres de Hanoi
Se presenta el pseudocódigo para resolver las Torres de Hanoi, que incluye cuatro parámetros principales: 'Start' (varilla inicial), 'Temp' (varilla temporal), 'End' (varilla final), y 'n' (tamaño de la torre). Ruben describe cómo se configuraría el problema inicialmente, con los discos comenzando en la primera varilla, usando la varilla del medio como temporal, y moviéndolos al final en la tercera varilla.
🔢 Caso base del algoritmo
El caso base del algoritmo se activa cuando 'n' es igual a 1, lo que significa que solo hay un disco por mover. En este escenario, el único paso necesario es trasladar el disco de la varilla inicial a la varilla final sin recurrir a recursión, ya que el problema es trivial con un solo disco.
↪️ Descomposición recursiva del problema
Cuando 'n' es mayor que 1, el problema se vuelve más complejo y requiere tres pasos. El primero es mover 'n-1' discos desde la varilla inicial a la varilla temporal, usando la varilla final como apoyo. En este caso, por ejemplo, se moverían dos discos desde la varilla 1 a la varilla 2, dejando el disco más grande en la varilla inicial.
⬆️ Movimiento del disco más grande
Una vez que los discos más pequeños se han movido a la varilla temporal, el disco más grande que queda en la varilla inicial se puede trasladar directamente a la varilla final, que es su destino.
🔄 Completar el rompecabezas
En el último paso, los discos en la varilla temporal se mueven a la varilla final para completar el rompecabezas. Ruben muestra cómo estos tres pasos se corresponden con las líneas de pseudocódigo, y al final del proceso, todos los discos se trasladan de la varilla inicial a la varilla final, resolviendo el rompecabezas.
Mindmap
Keywords
💡Torres de Hanoi
💡Recursividad
💡Caso base
💡Algoritmo
💡Varillas
💡Discos
💡Pseudo código
💡Función mover
💡Complejidad del algoritmo
💡Descomposición del problema
Highlights
Introduction to the Towers of Hanoi algorithm
Explanation of the general strategy for solving the puzzle
Pseudo code for an algorithm to solve Towers of Hanoi with 'n' disks
Assumptions about the data structure for rods and disks
Encapsulation of the move functionality
The importance of the move operation in the algorithm
Parameters of the Towers of Hanoi pseudo code
Role of Start, Temp, and End rods in the algorithm
Explanation of the tower size variable 'n'
Base case for a tower of size one
Recursive steps for towers greater than one disk
First recursive step: Moving n-1 disks to the temp rod
Second recursive step: Moving the largest disk to the end rod
Third recursive step: Moving the n-1 disks from temp to end
Mapping the recursive steps to the pseudo code
Completion of the puzzle by moving all disks to the end rod
Question about the number of moves required by the algorithm
Transcripts
- [Ruben Acuña] In this video, I want to discuss
the actual algorithm for solving Towers of Hanoi.
So, as previously discussed,
there is kind of this general notion
of how we can move smaller towers and then larger disks
and then a smaller tower again,
in order to solve the general problem, right?
Solve the general puzzle.
So the pseudo code that does it is actually here on
the right hand side.
So this is the pseudo code for an algorithm
that could play a game of Towers of Hanoi for
an "n" sized number of disks.
So we have some basic assumptions.
First of all we're going to say that the rods and disks
are already modeled with some data structure,
we're not gonna talk about that right,
this is just pseudo code.
And then that's gonna be kind of encapsulated
by something called move.
So there's some bit of functionality out there
which encapsulates moving a disk
from one particular rod to another one.
Alright, so we're just gonna say that's out there.
Um, and that will actually end up being,
because that's kind of a basic operation
and it will take a little bit of time,
be the thing that we write a growth function for.
Okay, so let's take a look at the code
on the right hand side.
So we have our Towers of Hanoi pseudo code here.
So you can see that there are four parameters
to this bit of pseudo code.
So, Start is basically, what rod do we want to start on,
Temp is the working one, right?
There's three that are available to us, right?
So where can we put kind of spare things.
And then End which is the last rod right?
The one where I wanna move everything to it.
Final variable there, n, is the tower size, right?
How many disks do I want to use?
So the first time I call this, right, if I were trying to
solve the Towers of Hanoi problem, I would say that Start is
one, because all the disks initially start there
on the left hand side.
They use the middle rod as a kind of, a temporary space
to move things, and I'm trying to move
them to the End, right? The third most, rod.
In the example we did by hand we had three disks
so, n initially would be three.
That's how things would start out.
Take a look at this program, what exactly is happening?
First we have, if n equal one.
So this is our, kind of our base case, right,
the simplest possible puzzle I could solve,
happens to be when I'm moving one disk from
one tower to another.
In that case, basically it's given
that it's gonna work for me.
So, in that case if I have a tower of size one
what I, the only thing I need to do is call move
to go from Start to End.
So I'm moving one final piece.
So, that's the simplest tower I could possibly move,
don't require any recursion there, everything is good.
Else, right, n is the greater than one, so it's at least two
I need to do a little bit of more work.
So there's three steps in here,
that we had basically talked about when we looked
at doing the trace by hand of
how exactly we'd move things along.
So the first line is going to move n minus one disks
from the first tower,
to the, uh last tower.
Well to the temp tower.
So the parameters, right, the parameters
are set up so the first thing is you're,
where you're getting disks from,
the last thing is where you're getting disks to.
So what this line is saying is,
take disks from the start tower, starting tower,
use the n tower as a temporary and the temporary
as the target, right, so we're moving n minus to, right,
meaning for example here, n minus one,
meaning here for example two items, right,
from that first tower to the middle tower.
Alright, that's where we're doing our, kind of our first
partial decomposition of this tower, right?
To move a couple parts of it.
So we do that, first thing.
And here right, the way this code is looking, right, is
we're moving from Start to Temp, right.
So, we're moving from rod one to rod two.
Rod three is where our End is,
we don't want to touch that right now.
The second step is to move from Start to End, right.
After you move that, that smaller tower, right the
n minus one tower, off of that starting rod,
that means the only thing left there is the biggest disk.
So that biggest disk, I can move it where it finally belongs
right, it belongs on the right hand side, on that peg.
So that moves from one to three.
Right, this is from one to two, this is from
one...
to three.
Then we can go over here and basically say,
okay I need to finish my work,
which my work is to then to go from,
from the middle point, right, the Temp, right,
which is, which is number two, over to number three.
Right, I have at this point, right, so, so,
if I jump back to my other slide for a second,
alright, my initial process is basically to say
okay I'm going to from that initial state to the state
where I have, the n minus one tower moved to the middle,
right, that's, that's here.
Then I also move that one piece,
from the first to the very end,
and then once I have that,
I move the two pieces from the middle to the very end.
Which gets me this over here.
Right, so those are the three things that are basically
the map to these different pieces of code over here, right.
We do, we move a smaller tower,
move one piece and then move the smaller tower.
At the end of the day, well hey, we've moved everything
from the starting peg to the ending one.
So in that case, right, we've moved everything along
and we've at least, you know, solved the puzzle.
So now the question is, just how many moves does
this particular method make?
Voir Plus de Vidéos Connexes
[SER222] Recurrences (2/7): Towers of Hanoi
[SER222] Recurrences (4/7): Guessing a Growth Function
Solucionar ecuaciones lineales | Ejemplo 6
Solución de ecuaciones lineales | Ejemplo 5
44. Integral de una función trigonométrica elevada a exponente (completando derivada)
05. Integral de una constante (Pi al cuadrado)
5.0 / 5 (0 votes)