Este problema se puede modelar de muchas formas. Por ejemplo podemos empezar por definir una estructura para modelar las islas y el barco:
struct Barco
{
int canibales; // Numero de canibales en el barco
int misioneros; // Numero de misioneros en el barco
int ida; // A true si el barco hace el recorrido de ida
};
struct Posicion
{
int canibales; // Numero de canibales en el barco
int misioneros; // Numero de misioneros en el barco
};
Es preferible la estructura a los arrays porque si no, a la hora de depurar el código, hay que recordar en todo momento si 0
se refería a caníbales o a misioneros... y un error en esta parte echa por tierra todo el programa.
Con esto ya podríamos crear una función que nos dijese si un viaje es válido. Podemos entender que un viaje es válido si:
- En la isla origen no quedan más caníbales que misioneros después de partir el barco
- En la isla destino no quedan más caníbales que misioneros después de llegar el barco
- Si en una isla no hay misioneros, podrá haber un número cualquiera de caníbales
- En la isla de origen no puede haber un número negativo de misioneros o caníbales... esto no es como el milagro de los panes y los peces
Que dicho con código podría quedar así:
int ViajeValido(Posicion const* inicio, Posicion const* fin, Barco const* barco)
{
int toReturn = (inicio->misioneros - barco->misioneros >= 0)
&& (inicio->canibales - barco->canibales >= 0);
if( toReturn && inicio->misioneros - barco->misioneros != 0 )
toReturn = (inicio->canibales - barco->canibales <= inicio->misioneros - barco->misioneros);
if( toReturn && fin->misioneros + barco->misioneros != 0 )
toReturn = (fin->canibales + barco->canibales <= fin->misioneros + barco->misioneros);
return toReturn;
}
Y con esto prácticamente ya tenemos los pilares básicos... ahora podemos centrarnos en crear las utilidades, por ejemplo para poder mover al personal de una isla al barco y viceversa:
typedef struct
{
int canibales; // Numero de canibales en el barco
int misioneros; // Numero de misioneros en el barco
int ida; // A 1 si el barco hace el recorrido de ida, 0 en el caso de vuelta
} Barco;
typedef struct
{
int canibales; // Numero de canibales en el barco
int misioneros; // Numero de misioneros en el barco
} Posicion;
Y también, ya puestos, podemos escribir funciones para imprimir el estado tanto de las islas como del barco:
void imprimirIsla(Posicion const* posicion)
{
printf("M:%d C:%d", posicion->misioneros, posicion->canibales);
}
void imprimirBarco(Barco const* barco)
{
if( barco->ida )
{
printf("---->> \\_M:%d_C:%d_/ ", barco->misioneros, barco->canibales);
}
else
{
printf(" \\_M:%d_C:%d_/ <<----", barco->misioneros, barco->canibales);
}
}
Con estos últimos mimbres, la función que debe imprimir el estado queda de lo más simple:
void imprimirEstado(Posicion const* inicio, Posicion const* fin, Barco const* barco)
{
imprimirIsla(inicio);
printf(" | ");
imprimirBarco(barco);
printf(" | ");
imprimirIsla(fin);
printf("\n");
}
Y ya está con esto ya tenemos toda la base montada. Vamos con el main
. Lo primero sería definir los posibles movimientos tanto de ida como de vuelta. Si atendemos a la solución vemos que solo hay 3 posibles motivimientos de ida y 2 de vuelta:
La ida:
- 2 misioneros
- 2 canibales
- 1 misionero y 1 canibal
La vuelta:
- 1 canibal
- 1 misionero y 1 canibal
Es decir:
Barco const ida[] = { { 2, 0, true }, { 0, 2, true }, { 1, 1, true } };
Barco const vuelta[] = { { 1, 0, false }, { 1, 1, false } };
Barco const dummy = { 0, 0, 1 }; // Lo usaremos para imprimir las posiciones inicial y final
Tampoco podemos olvidar definir las posiciones iniciales, es decir, 3 caníbales y 3 misioneros en la isla de origen y nadie en la de destino
Posicion inicio = { 3, 3 };
Posicion fin = { 0, 0 };
Y ahora a planificar los viajes. El algoritmo debe elegir la primera ruta (según toque ida o vuelta) siempre y cuando no sea inválida. Aquí podemos asumir que siempre al menos una de las opciones va a ser válida.
Así, el código para la ida podría quedar así:
for( int i=0; i<3; i++ )
{
Barco const* barco = &ida[i];
if( viajeValido(&inicio, &fin, barco) )
{
MoverAlBarco(&inicio, barco);
imprimirEstado(&inicio, &fin, barco);
MoverALaIsla(&fin, barco);
break;
}
}
Es decir, evaluamos las posibles opciones de la ida y, al encontrar la primera válida, ejecutamos el viaje, esto es, movemos al personal correspondiente de la isla de origen a la de destino y de paso aprovechamos para imprimir el log del viaje
El viaje de vuelta sería igual pero con el array de vuelta
:
for( int i=0; i<2; i++ )
{
Barco const* barco = &vuelta[i];
if( viajeValido(&fin, &inicio, barco) )
{
MoverAlBarco(&fin, barco);
imprimirEstado(&inicio, &fin, barco);
MoverALaIsla(&inicio, barco);
break;
}
}
Y todo esto tenemos que repetirlo indefinidamente hasta que todos los caníbales y misioneros hayan cruzado. Sabremos que han cruzado evaluando la isla destino después del viaje de ida y antes del viaje de vuelta... si ya han llegado todos no hay necesidad de hacer un viaje de vuelta:
imprimirEstado(&inicio, &fin, &dummy);
while(1)
{
for( int i=0; i<3; i++ )
{
Barco const* barco = &ida[i];
if( viajeValido(&inicio, &fin, barco) )
{
MoverAlBarco(&inicio, barco);
imprimirEstado(&inicio, &fin, barco);
MoverALaIsla(&fin, barco);
break;
}
}
if( fin.canibales == 3 && fin.misioneros == 3 )
{
imprimirEstado(&inicio, &fin, &dummy);
break;
}
for( int i=0; i<2; i++ )
{
Barco const* barco = &vuelta[i];
if( viajeValido(&fin, &inicio, barco) )
{
MoverAlBarco(&fin, barco);
imprimirEstado(&inicio, &fin, barco);
MoverALaIsla(&inicio, barco);
break;
}
}
}
Este código lo puedes ver funcionando aquí
Y dicho todo esto, me permito la licencia de avisarte que no copies el programa tal cual. No solo no aprenderás nada sino que se notará que el código no es tuyo. Intenta entender la lógica que hay detrás y exprésala a tu manera. Es la única forma de aprender.