Configuración de Hanoi en un movimiento determinado

Question

Estoy interesado en encontrar cuántos discos hay en cada clavija en un movimiento dado en el towers of Hanoi rompecabezas. Por ejemplo, dada n = 3 discos que tenemos esta secuencia de configuraciones para resolver el rompecabezas de forma óptima:

0 1 2 
0. 3 0 0 
1. 2 0 1 (move 0 -> 2) 
2. 1 1 1 (move 0 -> 1) 
3. 1 2 0 (move 2 -> 1) 
4. 0 2 1 (move 0 -> 2) 
5. 1 1 1 (move 1 -> 0) 
6. 1 0 2 (move 1 -> 2) 
7. 0 0 3 (move 0 -> 2) 

Así determinado número de jugadas 5, quiero volver 1 1 1, dada movimiento número 6, quiero 1 0 2 etc.

Esto se puede hacer fácilmente utilizando el algoritmo clásico y deteniéndolo después de un cierto número de movimientos, pero quiero algo más eficiente. La página de wikipedia a la que he vinculado proporciona un algoritmo en la sección Binary solutions. Creo que esto está mal, sin embargo. Tampoco entiendo cómo calculan n.

Si sigue su ejemplo y convierte las posiciones del disco vuelve a lo que yo quiero, da 4 0 4 para discos n = 8 y mueve el número 216. Usando el algoritmo clásico, sin embargo, obtengo 4 2 2.

También hay un algoritmo eficiente implementado en C here que también da 4 2 2 como respuesta, pero carece de documentación y no tengo acceso al documento en el que se basa.

El algoritmo en el enlace anterior parece correcto, pero ¿alguien puede explicar cómo funciona exactamente?

Algunas preguntas relacionadas que yo también estoy interesado:

1. es el algoritmo de Wikipedia realmente mal, o me estoy perdiendo algo? ¿Y cómo calculan n?
2. Solo quiero saber cuántos discos hay en cada par en un movimiento determinado, no en qué paridad está cada disco, que es lo que la literatura parece estar más preocupada. ¿Hay alguna manera más simple de resolver mi problema?

Answer 1

1) Si su algo dice la Wikipedia se rompe supongo que tienes razón ...

2) En cuanto a calcular el número de discos en cada clavija, es bastante straightfoward hacer un recursivo algoritmo para ello:

(no probado, unelegant y posiblemente llena de + -1 código de errores sigue :)

function hanoi(n, nsteps, begin, middle, end, nb, nm, ne) 
    // n = number of disks to mive from begin to end 
    // nsteps = number of steps to move 
    // begin, middle, end = index of the pegs 
    // nb, nm, ne = number of disks currently in each of the pegs 

    if(nsteps = 0) return (begin, middle, end, nb, nm, ne) 

    //else: 

    //hanoi goes like 
    // a) h(n-1, begin, end, middle) | 2^(n-1) steps 
    // b) move 1 from begin -> end | 1 step 
    // c) h(n-1, middle, begin, end) | 2^(n-1) steps 
    // Since we know how the pile will look like after a), b) and c) 
    // we can skip those steps if nsteps is large... 

    if(nsteps <= 2^(n-1)){ 
     return hanoi(n-1, nsteps, begin, end, middle, nb, ne, nm): 
    } 
    nb -= n; 
    nm += (n-1); 
    ne += 1; 
    nsteps -= (2^(n-1) + 1); 
    //we are now between b) and c) 

    return hanoi((n-1), nsteps, middle, begin, end, nm, nb, ne); 

function(h, n, nsteps) 
    return hanoi(n, nsteps, 1, 2, 3, n, 0, 0) 

Si desea effieciency, se debe tratar de convertir esto en una forma iterativa (no debe se duro - no lo haces ed para mantener una pila de todos modos) y encontrar una manera de representar mejor el estado del programa, en lugar de usar 6+ variables de cualquier manera.

Answer 2

Puede utilizar el hecho de que la posición en potencias de dos es fácilmente conocida. Para una torre de tamaño T, tenemos:

Time   Heights 
2^T-1  | { 0, 0, T } 
2^(T-1) | { 0, T-1, 1 } 
2^(T-1)-1 | { 1, T-1, 0 } 
2^(T-2) | { 1, 1, T-2 } 
2^(T-2)-1 | { 2, 0, T-2 } 
2^(T-2) | { 2, T-3, 1 } 
2^(T-2)-1 | { 3, T-3, 0 } 
      ... 
0   | { T, 0, 0 } 

Es fácil de encontrar en la cual entre los niveles de su movimiento k es; simplemente mira log2 (k).

A continuación, observe que entre 2^(a-1) y 2^a-1, hay T-a discos que permanecen en el mismo lugar (los discos más pesados). Sin embargo, todos los otros bloques se moverán, ya que en esta etapa el algoritmo está moviendo la sub-torre del tamaño a. Por lo tanto, use un enfoque iterativo.

Puede ser un poco complicado conseguir la contabilidad correcta, pero aquí tiene los ingredientes para encontrar las alturas para cualquier k, con la complejidad de tiempo O (log2 (T)).

Saludos

Answer 3

If you look at the first few moves of the puzzle, you'll see an important pattern. Each move (i - j) below means on turn i, move disc j. Discs are 0-indexed, where 0 is the smallest disc. 

1 - 0 
2 - 1 
3 - 0 
4 - 2 
5 - 0 
6 - 1 
7 - 0 
8 - 3 
9 - 0 
10 - 1 
11 - 0 
12 - 2 
13 - 0 
14 - 1 
15 - 0 

Disco 0 se mueve cada 2 vueltas, a partir de la curva 1. El disco 1 se mueve cada 4 vueltas, a partir del turno 2 ... Disc i se mueve cada 2^(i + 1) gira, comenzando en el turno 2^i.

Por lo tanto, en un tiempo constante podemos determinar cuántas veces un disco dado se ha movido, m dado:

mueve = (m + 2^i)/(2^(i + 1)) [división de enteros ]

Lo siguiente a tener en cuenta es que cada disco se mueve en un patrón cíclico. A saber, los discos impares se mueven hacia la izquierda cada vez que se mueven (2, 3, 1, 2, 3, 1 ...) y los discos pares se mueven hacia la derecha (1, 3, 2, 1, 3, 2 ...)

Así que una vez que sepa cuántas veces se ha movido un disco, puede determinar fácilmente qué clavija termina tomando el mod 3 (y haciendo un poco de cálculo).