Escriba una función / subrutina para ordenar una lista de enteros, estilo Torre de Hanoi .
Se le dará una pila de enteros. Esta es la pila principal.
También te dan dos pilas de ayuda más. Sin embargo, estas pilas auxiliares tienen una propiedad única: cada elemento debe ser más pequeño o del mismo tamaño que el elemento debajo de él. La pila principal no tiene esa restricción.
Tiene la tarea de ordenar la pila principal en su lugar, colocando los enteros más grandes debajo. Su función / subrutina devolverá (o equivalente) el número de movimientos que realizó al ordenar la pila.
Nota: debe ordenar la pila principal en su lugar , sin ordenar en otra pila y llamar a eso la respuesta. Sin embargo, si por alguna razón no puede hacerlo, puede simular las pilas mutables, pero recuerde que esto es del tipo Torre de Hanoi; solo hay 3 clavijas y solo 1 clavija puede estar desordenada.
Su función / subrutina puede inspeccionar cualquier pila en cualquier momento, pero solo puede hacer un movimiento haciendo estallar y empujando. Un solo movimiento es un pop de una pila que se empuja a otra.
Pruebe su función / subrutina para cada permutación de los primeros 6 números naturales. En otras palabras, poner a prueba su función / subrutina para {1},{2},...,{6},{1,1},{1,2},...,{1,6},{2,1},...
(este debe ser un total de o posibilidades (gracias a Howard para corregir mis matemáticas)). La función / subrutina que mueve elementos la menor cantidad de veces gana.61+62+...+66
55986
fuente
6**1+6**2+...+6**6=55986
elementos.Respuestas:
Java: solución óptima (movimientos 1080544)
Esta solución construye un árbol de ruta más corta desde el objetivo y hacia atrás, luego atraviesa la ruta desde el estado inicial hasta el objetivo. Mucho espacio para mejorar la velocidad, pero aún así completa todos los problemas de 55986 en aproximadamente un minuto.
Suponiendo que el algoritmo se implemente correctamente, esta debería ser la mejor solución teórica.
fuente
C - 2547172 para entradas 55986
Aquí hay mucho margen de mejora. Por mi propia cordura, simplifiqué esto para que solo fuera posible inspeccionar el elemento superior de cada pila. Levantar esta restricción autoimpuesta permitiría optimizaciones como determinar el orden final por adelantado y tratar de minimizar el número de movimientos necesarios para lograrlo. Un ejemplo convincente es que mi implementación tiene el peor comportamiento si la pila principal ya está ordenada.
Algoritmo:
Análisis:
fuente
Python,
39838383912258 mueve más de 55986 entradasEsto es muy ineficiente.
Agregaré el número total de movimientos después de que el OP aclare si son para todos esos casos o para otros casos específicos.
Explicación
¿Qué, los comentarios no son lo suficientemente buenos para ti?
Nota para OP: Gracias por no hacer este código de golf.
fuente
[2,1,1]
¿hay alguna manera de obtener[2,1,1].index(1)
2, es decir, comenzar desde el extremo superior?[2,1,1,3,5].index(1)==2
lugar de1
list.index(data)
devuelve el índice del artículodata
enlist
. Yo no sé el índice dedata
decir1
len(list)-(list[::-1].index(1))
Python:
1,688,2931,579,1821,524,0541,450,8421,093,195 movimientosEl método principal es
main_to_help_best
, que consiste en mover algunos elementos seleccionados de la pila principal a la pila auxiliar. Tiene una banderaeverything
que define si queremos que mueva todo dentro de lo especificadodestination
, o si queremos mantener solo el más grande endestination
mientras que el resto en el otro ayudante.Suponiendo que nos estamos moviendo para
dst
usar helperhelper
, la función se puede describir de la siguiente manera:helper
recursivadst
helper
a principaldst
everything
está configurado, mueva recursivamente elementos en main adst
b. De lo contrario, mueva recursivamente elementos en main a
helper
El algoritmo de clasificación principal (
sort2
en mi código) luego llamarámain_to_help_best
coneverything
set toFalse
, y luego moverá el elemento más grande de nuevo a main, luego moverá todo desde el asistente de regreso a main, manteniéndolo ordenado.Más explicaciones incrustadas como comentarios en el código.
Básicamente los principios que utilicé son:
El Principio 3 se implementa al no contar el movimiento si la fuente es el destino anterior (es decir, simplemente cambiamos de principal a help1, luego queremos pasar de help1 a help2) y, además, reducimos el número de movimientos en 1 si lo están moviendo de nuevo a la posición original (es decir, principal para ayudar1 luego ayuda1 a principal). Además, si los
n
movimientos anteriores se mueven todos con el mismo número entero, podemos reordenar esosn
movimientos. Entonces también aprovechamos eso para reducir aún más el número de movimientos.Esto es válido ya que conocemos todos los elementos en la pila principal, por lo que esto puede interpretarse como si veamos en el futuro que vamos a mover el elemento hacia atrás, no debemos hacer este movimiento.
Ejecución de muestra (las pilas se muestran de abajo hacia arriba, por lo que el primer elemento es la parte inferior):
Podemos ver que el peor de los casos es cuando el elemento más grande se coloca en el segundo fondo, mientras que el resto se clasifica. Del peor de los casos podemos ver que el algoritmo es O (n ^ 2).
El número de movimientos es obviamente mínimo
n=1
y,n=2
como podemos ver en el resultado, y creo que esto también es mínimo para valores más grandes den
, aunque no puedo probarlo.Más explicaciones están en el código.
fuente
4
. ¿Qué es esto almacenar el segundo elemento más grande en el segundo ayudante? Qué significa eso?Java -
21290902083142 se mueve en matrices 55986El enlace ideone .
El marco para garantizar que el algoritmo sea correcto:
El algoritmo real:
El caso de prueba:
fuente
C / C ++ no midió movimientos (clavijas: p1, p2, p3) No sé cómo agregar código C ++ que usa STL (problema de formateo). Perder partes del código debido a los formatos de etiqueta html en el código.
Combinar datos de movimiento (n + m) en p2 y p3 a p1.
fuente
hanoi(...)
función Además, tienes 2#include
s que no se compilan. Por favor, publique el código completo.