1

Necesito solucionar el tema de "misioneros y caníbales", el cual consta en transportar 3 misioneros y 3 caníbales por medio de un bote del lado "A" hacia el lado "B". se tienen las siguientes restricciones: 1.- En el bote solo entran 2 personas y debe haber al menos 1 para que este se mueva de lado a lado. 2.- No puede en ningún caso quedar en cualquiera de los lados una cantidad de Caníbales mayor a la de los misioneros, de lo contrario, se considera una "opción inválida". 3.- el problema se resuelve cuando los 3 misioneros y 3 caníbales son trasladados del Lado A hacia el Lado B.

adjunto foto de la solución al problema:

introducir la descripción de la imagen aquí

Debo realizarlo programando en C y no me manejo mucho en el tema de este lenguaje actualmente tengo este código:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct Estados{
    int Orillas[2][2];
    int Bote;
    int ind_viaje;
    int EstadoAnterior;
} Estado;


int ValidarEstado(Estado *e)
{
    if(e->Orillas[0][0] < 0 || e->Orillas[0][1] < 0 ||
        e->Orillas[1][0] < 0 || e->Orillas[1][1] < 0 ||
        e->Orillas[0][0] > 3 || e->Orillas[0][1] > 3 ||
        e->Orillas[1][0] > 3 || e->Orillas[1][1] > 3)
        return 0;

    if((e->Orillas[0][0] < e->Orillas[0][1] && e->Orillas[0][0] > 0) ||
        (e->Orillas[1][0] < e->Orillas[1][1] && e->Orillas[1][0] > 0))
        return 0;

    return 1;
}

void Trasladar(Estado *Destino, Estado *Origen, int *viaje)
{
    memcpy(Destino, Origen, sizeof(*Origen));

    Destino->Orillas[Destino->Bote][0] -= viaje[0];
    Destino->Orillas[Destino->Bote][1] -= viaje[1];

    Destino->Bote = Destino->Bote ? 0 : 1; 

    Destino->Orillas[Destino->Bote][0] += viaje[0];
    Destino->Orillas[Destino->Bote][1] += viaje[1];
}

void ImprimirEstado(Estado *e)
{
    printf("Misioneros: %i Canibales: %i | %s | Misioneros: %i Canibales: %i\n",
        e->Orillas[0][0], e->Orillas[0][1],
        e->Bote ? " --------- \\__/ " : " \\__/ --------- ",
        e->Orillas[1][0], e->Orillas[1][1]);
}

int main()
{
    Estado inicio = { {{3, 3}, {0, 0}}, 0, 0 };
    Estado fin = { {{0, 0}, {3, 3}}, 1, 0 };
    Estado nuevo, *copia;
    /*Opciones de Viajes*/
    int viajes[5][2] = { {0, 1}, {1, 0}, {1, 1}, {2, 0}, {0, 2} };
    int i;

    return 0;
}

Tengo entendido que debo ir comparando los estados que ya he utilizado con el nuevo estado (movimiento) y luego al terminar, imprimir todos los estados que fueron utilizadas, tanto correctas como incorrectas, pero no logro idear esta parte del código.

Estoy programando con sublime text 3 y utilizando MinGW - gcc en WINDOWS.

Si alguien puede orientarme u ayudarme a completar el código, se los agradezco de antemano.

3
  • 2
    No tengo ni la más mínima idea de qué significa lo de misioneros y caníbales. En concreto ¿Cuál es tu pregunta? Commented el 11 sept. 2020 a las 20:10
  • 4
    Deberías aclarar que estás tratando de resolver el acertijo de los misioneros y caníbales y dar una pequeña explicación del mismo, además indica dónde tienes problemas y los errores que recibes. Sin ese contexto, igual la gente cree que hablas de una película de bajo presupuesto de los 80. Saludos Commented el 11 sept. 2020 a las 20:15
  • Te recomiendo aprender sobre autómatas en tu caso, en lenguaje C, esto te ayudará para abstraer tu problema en una máquina de estados con la que se te facilitará mucho el trabajo y la programación. Es una posible forma de encontrar una solución. Así como está tú código es complicado entender que debes hacer o cómo llegar a una solución. Puedes checar esta liga
    – RedSalas
    Commented el 11 sept. 2020 a las 21:29

1 respuesta 1

4

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.

1
  • muchas gracias, si estaba leyendo el primer código que compartiste anteriormente y vi que era de c++, gracias por haberlo realizado también en C Commented el 12 sept. 2020 a las 4:13

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.