¿Qué queremos decir generalmente con el tiempo más corto? Encontré un problema de hormigas trepando por un poste en la programación. Se trataba de encontrar el tiempo más corto para que las hormigas cayeran por el poste.
Supongamos que hay varios planes. Por supuesto, primero debe averiguar el tiempo de la última hormiga en dejar caer el poste antes de poder averiguar el tiempo requerido para el plan (= el tiempo de la última hormiga). para dejar caer el poste - la hora de inicio). Luego compare los tiempos requeridos de todas las opciones para encontrar el tiempo más corto.
La solución real es la siguiente (publicada nuevamente desde Internet):
Esta pregunta proviene del libro La belleza de la programación.
Pregunta: Hay un poste de madera de 27 cm. Hay una hormiga en cada una de las cinco posiciones: 3 cm, 7 cm, 11 cm, 17 cm y 23 cm. El poste de madera es muy delgado y no puede pasar dos hormigas al mismo tiempo. Al principio, no está claro en qué dirección está mirando la cabeza de cada hormiga. Solo caminarán hacia adelante o se darán la vuelta, pero no retrocederán. Cuando dos hormigas se encuentran, se darán vuelta y caminarán en direcciones opuestas al mismo tiempo. Supongamos que las hormigas pueden caminar un centímetro por segundo. Escribe un programa para encontrar el tiempo más corto y más largo para que todas las hormigas abandonen el poste de madera.
Solución 1: este puede ser el método en el que pensará la mayoría de la gente (jaja, eso pensé cuando comencé). )
Considera enumerar la orientación inicial de las hormigas y simular el movimiento de cada hormiga para resolver el problema.
Solución 2:
Considere que aunque las dos hormigas se dieron la vuelta y fueron en dirección opuesta después de encontrarse, se puede considerar como dos hormigas que se cruzan después de encontrarse (muchas personas. pueden darse cuenta de repente cuando vean esto). Es decir, se puede considerar que el movimiento de las hormigas es independiente, y si hay reunión o no no es el foco del problema.
De esta forma, aunque la trayectoria de movimiento de cada hormiga es diferente a la original. Pero el tiempo más corto y más largo para que todas las hormigas abandonen el poste de madera se mantienen sin cambios. Solo necesitas calcular el tiempo que tarda cada hormiga en abandonar el poste de madera por separado, y podrás encontrar el tiempo que tardan todas las hormigas en abandonar el poste de madera.
De esta manera, el programa solo necesita atravesar todas las hormigas y calcular el tiempo más largo para que cada hormiga salga del poste de madera (la hormiga camina hacia el extremo más alejado de sí misma), y el el tiempo más corto (la hormiga camina hacia el extremo más cercano a sí misma) (vaya a un extremo del poste) y calcule el valor máximo. Estos dos valores máximos son el tiempo más largo y más corto para que todas las hormigas abandonen el poste de madera.