Skip to content

Solución: cruzando el puente

by en 07/01/2013

Hola!

Gracias a todos los que habéis dado vuestra solución en los comentarios del post anterior. Aquí va la explicación cómo se resuelve.

Como varios dijísteis, la que parece la mejor estrategia es aquella en la que se hace cruzar el puente continuamente al caminante más rápido. Dado que es necesario traer de vuelta el farol, hacemos cruzar al rápido con todos, para que se encargue de volver con el farol en el menor tiempo posible.

Así, en el primer caso de 4, 6, 7 y 8 minutos, la secuencia óptima es:

  1. Cruzan juntos 4 y 6, tardando 6
  2. Vuelve 4
  3. Cruzan juntos 4 y 7
  4. Vuelve 4
  5. Cruzan juntos 4 y 8

El tiempo total es 6+4+7+4+8=29, como algunos comentábais.

El segundo caso que os proponíamos era 4, 5, 7 y 8, muy parecido al anterior pero que tenía trampa, porque la estrategia óptima resulta ser otra. Es más fácil caer en la cuenta de que hay una alternativa más eficiente con números más extremos, como 4, 5, 100 y 101. En ese caso, parece que hacer cruzar juntos a 100 y 101 puede ser muy beneficioso, porque hemos hecho cruzar a dos lentos “por el precio de uno”. El problema es que hay que llevar el farol de vuelta, y no queremos que sea ninguno de los lentos quién lo haga. La solución es haber hecho cruzar antes a alguno de los rápidos, que esté esperando en el otro lado para devolver el farol traído por los dos lentos.

Con los tiempos 4, 5, 7 y 8 ocurre lo mismo, aunque en mucha menor medida. La forma eficiente de cruzar es:

  1. Cruzan juntos 4 y 5. El 5 se queda al otro lado “de reserva” para volver más adelante
  2. Vuelve 4
  3. Cruzan juntos 7 y 8: dos lentos al precio de uno
  4. Vuelve 5 con el farol
  5. Cruzan juntos 4 y 5

El tiempo total es 5+4+8+5+5=27. Si se siguiera la estrategia de hacer ir y venir al más rápido, el tiempo sería de 28, como algunos dijísteis.

Para saber en cada caso cual de las dos es la estrategia óptima hay que… comparar los tiempos y quedarnos con la mejor 🙂

Si te gusta programar y quieres practicar un poco, puedes resolver un problema muy parecido a éste y probar tu solución aquí.

¡Hasta la próxima!

Anuncios

From → Soluciones

Dejar un comentario

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: