algorithm - geeksforgeeks - Dos robots en una línea
search and sort algorithms (5)
Me parece que tu algoritmo debería funcionar. La idea en la solución publicada es que ambos robots mantienen un patrón de derecha a derecha a izquierda, lo que significa que están avanzando a cierto ritmo. Pero cuando el robot de la izquierda encuentra el paracaídas del otro, comienza a moverse hacia la derecha a un ritmo más rápido, ya que no se mueve una vez hacia la izquierda como parte de su patrón de desplazamiento, sino que sigue hacia la derecha, alcanzando finalmente al robot en el derecho.
Probablemente conozcas el problema con los dos robots caídos en una línea cuando necesitas programarlos para que se encuentren.
Se lanzan dos robots desde un avión y aterrizan en una sola línea (con posiciones discretas) usando un paracaídas que se deja en el punto de aterrizaje. Los robots están mirando hacia el norte, están separados por una distancia desconocida, y uno ha aterrizado directamente al este del otro.
Los robots ahora deben programarse de manera que se encuentren. Se les puede indicar que se muevan a la izquierda o a la derecha a una posición cercana y que verifiquen si hay un paracaídas en la ubicación actual. Si el otro robot se encuentra, ambos robots se detienen allí y viven felices para siempre.
La verificación del paracaídas puede ejecutar de manera condicional cualquier cantidad de instrucciones y cualquier bloque de instrucciones puede repetirse incondicionalmente. Escriba un programa que ambos robots puedan seguir simultáneamente y qué garrapatas puedan encontrar.
Tienes que crear un algoritmo genérico (un poco pleonástico) que aplique a ambos robots garantiza que los robots se encontrarán. Dejan su paracaídas en el lugar donde se dejan caer y pueden comprobar si en la posición actual hay un paracaídas.
La declaración original está aquí: http://en.wikibooks.org/wiki/Puzzles/Logic_puzzles/Parachuted_Robots También hay una solución que no entiendo. Si alguien puede darle sentido, ayúdenme con un poco de explicación. Cualquier otra solución sería muy apreciada.
Mi primer pensamiento sobre este problema sería programar el robot para que elija aleatoriamente para ir primero a la derecha o a la izquierda, y luego hacer algo como una búsqueda exponencial: primero ir 2 posiciones a la derecha, luego 4 a la izquierda, etc. Si está en una de estas " viajes "en la derecha o la izquierda el robot encuentra el segundo paracaídas (el que fue utilizado por el otro robot), el robot solo buscará en esa dirección. ¿Tiene esto algún sentido?
¡Muchas gracias!
Su solución de "primer pensamiento" debería funcionar también, pero a los robots les llevará más tiempo que la solución que citó en wikibooks . Para recapitular, la solución wikibooks es:
- 10 Ir a la derecha
- 20 Ir a la izquierda
- 30 Ir a la derecha
- 40 Si no es paracaídas GOTO 10
- 50 Ir a la derecha
- 60 GOTO 50
En caso de que no reconozca la sintaxis, el autor intenta imitar a BASIC, donde los números 10-60 son números de línea, y los GOTO son saltos de código.
Las líneas 10-40 tienen ambos robots moviéndose lentamente hacia la derecha. Los pasos "derecha, izquierda, derecha" ralentizan el movimiento hacia la derecha. Podría haber sido simplemente "correcto, espera". La línea 40 busca el paracaídas. Cuando ambos robots aterrizaron en la línea, exactamente uno de ellos estaba a la izquierda del otro. El robot izquierdo finalmente encontrará el otro paracaídas. La derecha nunca lo hará. Cuando el robot izquierdo encuentra el paracaídas del robot derecho, entra en las líneas 50-60, donde se mueve a la derecha sin la ralentización. Ahora que el robot izquierdo se mueve a la derecha más rápido que el robot derecho, la izquierda eventualmente lo alcanzará.
Personalmente, creo que el algoritmo que planteaste es más divertido, ya que ambos robots se balancearían mucho. En cierto modo, es un algoritmo similar, pero la desaceleración crece linealmente con cada paso.
mi programa es en realidad más corto, y funciona como un encanto para:
start: left
skipNext
goto start
next: left
goto next
esto funciona porque el segundo ciclo es más rápido que el primer ciclo
Puedes probar tu programa aquí: http://david-peter.de/parachuting-robots/
Ambos robots se mueven hacia la izquierda hasta que el robot derecho encuentra el paracaídas del robot izquierdo y comienza a correr hacia el robot izquierdo. Entonces chocan.
start: left
skipNext
goto start
goto moveLeftFast
moveLeftFast: left
goto moveLeftFast
Yo hice esto:
start: left
skipNext
goto start
fastL: left
left
goto fastL
La idea es simple: vamos a la izquierda un poco. Uno de los robots (el de la derecha) finalmente chocará con un paracaídas y luego se saltará del bucle del puño, e ingresará el segundo que lo hace ir a la izquierda el doble de rápido.