Misioneros y caníbales

Pregunta: En este problema, tres misioneros y tres caníbales deben cruzar un río usando un bote que puede transportar a lo sumo dos personas, bajo la restricción de que, para ambas orillas, los misioneros presentes en la orilla no pueden ser superados en número por caníbales. El barco no puede cruzar el río solo sin gente a bordo.

Solución:
Primero consideremos que tanto los misioneros (M) como los caníbales (C) están en el mismo lado del río.
Izquierda Derecha
Inicialmente las posiciones son: 0M, 0C y 3M, 3C (B)

Ahora enviemos 2 caníbales a la izquierda del banco: 0M, 2C (B) y 3M, 1C

Envía un caníbal de izquierda a derecha: 0M, 1C y 3M, 2C (B)

Ahora envía los 2 caníbales restantes a la izquierda: 0M, 3C (B) y 3M, 0C
Envía 1 caníbal a la derecha: 0M, 2C y 3M, 1C (B)

Ahora envía 2 misioneros a la izquierda: 2M, 2C (B) y 1M. 1C

Enviar 1 misionero y 1 caníbal a la derecha: 1M, 1C y 2M, 2C (B)

Envía 2 misioneros a la izquierda: 3M, 1C (B) y 0M, 2C

Enviar 1 caníbal a la derecha: 3M, 0C y 0M, 3C (B)

Envía 2 caníbales a la izquierda: 3M, 2C (B) y 0M, 1C

Enviar 1 caníbal a la derecha: 3M, 1C y 0M, 2C (B)’

Envía 2 caníbales a la izquierda: 3M, 3C (B) y 0M, 0C

• Aquí (B) muestra la posición del barco después de realizar la acción.
Por lo tanto, todos los misioneros y caníbales han cruzado el río a salvo.

Este artículo es una contribución de kaushik . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su artículo por correo a contribuya@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.

Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.