El problema de cuatro personas cruzando el puente

En la oscuridad de la noche, cuatro viajeros llegaron a un puente estrecho sin barandillas. Sin la ayuda de una linterna, de todos modos no se habrían atrevido a cruzar el puente. Desafortunadamente, las cuatro personas solo trajeron una linterna y el puente era muy estrecho, por lo que solo dos personas podían cruzarlo al mismo tiempo. Si cada persona cruza el puente sola, el tiempo requerido para las cuatro personas es 1 2 5 10 minutos; si dos personas cruzan el puente al mismo tiempo, el tiempo requerido es el más lento porque no se afectan entre sí. La pregunta es, ¿cómo diseñar un programa que permita a estas cuatro personas cruzar el puente lo más rápido posible?

Supongamos que estas cuatro personas son A=1, B=2, C=5, D=10

El tiempo consumido es 2+1+12+2= 17 minutos

Lo inteligente de este método es dejar que las dos personas más lentas crucen el puente al mismo tiempo. De esta manera, el tiempo invertido solo lo ocupa la persona más lenta D y la segunda persona más lenta C No. Pasan más tiempo cruzando puentes.

Para probar esto, primero hacemos tres suposiciones:

Demuestre que las suposiciones son verdaderas:

A la velocidad máxima en la noche de A=1 m/s, la longitud del puente es L=1*60=60 m; el alcance efectivo de una linterna LED normal es de al menos 200 m, que es más que suficiente para tratar con un puente pequeño.

Dejemos que A y D crucen el puente primero, D sosteniendo una linterna al frente y A cruzando el puente de manera segura bajo la luz. Cuando A cruza el puente, D se queda quieto en el puente y enfoca la linterna en la dirección que está arriba del puente. B dirige la luz hacia D, se encuentra con D y cruzan el puente juntos. Cuando B cruza el puente, D se queda quieto en el puente, esperando a que C se acerque y luego cruzan el puente juntos. Misión cumplida.

El diagrama esquemático es el siguiente, donde () es la dirección de la luz y ←↓→ es la dirección del movimiento:

El algoritmo es el siguiente:

A y D cruzan el puente juntos, A camina Después de terminar 1L, D caminó 1/10L; D esperó a B en 1/10L, se encontró con B y caminó 9/10L, y D esperó a 9/50L; C en 14/50L y se fue después de encontrarse con C. 36

Ding esperó a C en 14/50L y caminó 36/100L después de encontrarse con C

El ABC anterior cruzó el; puente uno por uno, y tomó 1+2+ 5=8 puntos

D está en 64/100L y camina solo los últimos 36/100L, tardando 3,6 minutos

El; El tiempo que tardan las cuatro personas mencionadas anteriormente en cruzar el puente es 8+3,6 = 11,6 min, mucho menos que 17 min.

La inteligencia de este método es maximizar el uso del espacio del puente y el rango de irradiación. de la linterna Sobre la base de cumplir con los requisitos mínimos de la pregunta, establezca los personajes razonablemente de acuerdo con la realidad para obtener la respuesta final.

Después de más de dos meses, el autor volvió a leer este artículo (publicado anteriormente en Sina Blog), junto con las preguntas planteadas por compañeros anteriores, y encontró dos preguntas:

Pensamientos Cómo responder:

En realidad, es un poco descabellado, pero no hay necesidad de tomárselo tan en serio.