Tengo problemas para entender precisamente cómo la prueba por inducción se utiliza para mostrar que en la mayoría tarda $2^n-1$ jugadas para conseguir todos los discos de una clavija a otra. ¿Existen fuentes de ayuda o conocimiento particular que tiene puede ayudar a mí y a otros, entender este problema más intuitivamente?
Respuestas
¿Demasiados anuncios?
Aquí's una prueba. Básicamente, la idea detrás de la inducción es esta: Para resolver el caso con $n$ discos, primero tiene que llegar a la cima $n-1$ de los discos en una clavija de modo que usted puede mover la parte inferior del disco. Por hipótesis inductiva, esto se lleva a $2^{n-1}-1$ se mueve. A continuación, toma un movimiento de la parte inferior del disco donde necesita ir. Entonces usted tiene que resolver el $n-1$ caja del disco nuevo, para obtener de ellos en la parte superior de la parte inferior del disco, que lleva a otro $2^{n-1}-1$ se mueve. Por lo que el número total de movimientos es $$[2^{n-1}-1] + 1 + [2^{n-1}-1] = 2^n - 1.$$
Shabaz
Puntos
403
La prueba va como sigue: para un disco, tarda $1=2^1-1$ movimiento. Asumir hasta discos de $n$ $2^n-1$ toma se mueve. Entonces para $n+1$ discos, primero tienes que mover se mueve el $n$ a una clavija vacía, tomando $2^n-1$. A continuación, mueve disco $n+1$ a la otra clavija vacía, tomar $1$ movimiento. En tercer lugar, mover la torre de discos de $n$ donde es en disco $n+1$, tomando otra vez $2^n-1$ se mueve. El número total de movimientos es $(2^n-1)+1+(2^n-1)=2^{n+1}-1$
Yaro
Puntos
41
Tengo una gran pila de discos en peg Una, no hay discos en peg B, y no de los discos en los peg C.
Mi objetivo es construir un algoritmo para mover n discos de una clavija a otro. Si tan sólo tuviera un algoritmo para mover n-1 discos de una clavija a otro - después de todo, entonces yo podría construir un algoritmo para n en tres sencillos pasos:
- mueva la parte superior de la n-1 discos de a a B
- mover el disco inferior de la a a la C
- mover los n-1 discos de la B a la C.
Es decir, si tengo un algoritmo que funciona para n-1, puede muy fácilmente construir uno (en los tres pasos que acabo de describir) que trabaja para n.
Pero espera - me puedo mover un disco. Así que pongamos a n = 2. Tengo un algoritmo que funciona para 1, así que tengo uno que funciona para los 2. Oh, y ahora puedo conjunto de n = 3...
