0

Mi código, al compilarlo, lo hace correctamente, pero al ejecutarlo suelta este error y nunca me había pasado. Me he informado por ahí y me han dicho que es porque intento acceder a una zona de memoria 'restringida'. Adjunto por aquí mi código y si alguien me pudiese decir dónde está el problema estaría agradecido. Gracias!

#include <stdio.h>
#include <stdlib.h>
#define N 8     // DEFINIMOS EL NUMERO DE NOMBRES QUE VAN A TENER NUESTRAS VARIABLES MAS ADELANTE

typedef enum {LADRON, POLICIA, PADRE, MADRE, HIJO1, HIJO2, HIJA1, HIJA2, NINGUNA} tPersona;     // DEFINIMOS EL NOMBRE DE LAS VARIBALES A USAR
char* NOMBRES[N] = {"Ladron", "Policia", "Padre", "Madre", "Hijo 1", "Hijo 2", "Hija 1", "Hija 2"}; // DEFINIMOS LAS ETIQUETAS DE NOMBRE QUE TENDRA CADA VARIABLE DEFINIDA ANTERIORMENTE

typedef struct {
    tPersona personas[2];
    int lado;
} tBalsa;

// DEVOLVEMOS MEDIANTE PARÁMETRO SI LA PERSONA ESTA EN UN LADO DE LA ORILLA O EN OTRO

int esta(tPersona persona, tPersona personas[], int numPersonas) {
    int i;

    i = 0;

    while ((i < numPersonas) && (personas[i] != persona)) {
        i++;
    }

    return i < numPersonas;
}

// MEDIANTE ESTE IF SABEMOS SI LAS PERSONAS DEL PROBLEMA ESTÁN JUNTAS O NO

int puedenEstarJuntos(tPersona personas[], int numPersonas) {
    if ((esta(PADRE, personas, numPersonas) && esta(HIJA1, personas, numPersonas) && !esta(MADRE, personas, numPersonas) && !esta(POLICIA, personas, numPersonas)) ||
        (esta(PADRE, personas, numPersonas) && esta(HIJA2, personas, numPersonas) && !esta(MADRE, personas, numPersonas) && !esta(POLICIA, personas, numPersonas)) ||
        (esta(MADRE, personas, numPersonas) && esta(HIJO1, personas, numPersonas) && !esta(PADRE, personas, numPersonas) && !esta(POLICIA, personas, numPersonas)) ||
        (esta(MADRE, personas, numPersonas) && esta(HIJO2, personas, numPersonas) && !esta(PADRE, personas, numPersonas) && !esta(POLICIA, personas, numPersonas)) ||
        (esta(LADRON, personas, numPersonas) && !esta(POLICIA, personas, numPersonas))) {
        return 0;
    } else {
        return 1;
    }
}

// COMPROBAMOS SI NUESTRA BARCA TIENE UN PILOTO PARA POSTERIORMENTE DEDUCIR SI PUEDE ZARPAR

int hayPiloto(tBalsa balsa) {
    return (balsa.personas[0] == POLICIA || balsa.personas[1] == POLICIA ||
            balsa.personas[0] == PADRE || balsa.personas[1] == PADRE ||
            balsa.personas[0] == MADRE || balsa.personas[1] == MADRE);
}

// EN EL CASO DE QUE LA BARCA PUEDA ZARPAR CORRECTAMENTE, PUES CUMPLE TODAS LAS CONDICIONES

int puedeZarpar(tBalsa balsa, tPersona lado0[], tPersona lado1[]) {
    return hayPiloto(balsa) && puedenEstarJuntos(balsa.personas, 2) &&
           puedenEstarJuntos(lado0, N) && puedenEstarJuntos(lado1, N);
}

// DEVOLVEMOS CUANTAS PERSONAS HAY EN LA BALSA, O EL LADO DONDE SE ENCUENTRAN, TODO ELLO MEIDANTE PARÁMETRO

int cuantasHay(tPersona personas[]) {
    int i;
    int n;

    n = 0;

    for (i = 0; i < N; i++) {
        if (personas[i] != NINGUNA) {
            n++;
        }
    }

    return n;
}

// CALCULAMOS EL PROBLEMA MEDIANTE BACKTRACKING EN EL CASO DE QUE EL PROBLEMA SI SE PUEDA   RESOLVER POR ESTE MÉTODO

int sePuedeResolver(tPersona lado0[], tPersona lado1[], tBalsa balsa) {
    if (cuantasHay(lado0) == 0) {
        return 1;
    }

    for (int i = 0; i < N; i++) {
        for (int j = i + 1; j < N; j++) {
            if (balsa.lado == 0 && lado0[i] != NINGUNA && lado0[j] != NINGUNA) {
                balsa.personas[0] = lado0[i];
                lado0[i] = NINGUNA;
                balsa.personas[1] = lado0[j];
                lado0[j] = NINGUNA;
            } else if (balsa.lado == 1 && lado1[i] != NINGUNA && lado1[j] != NINGUNA) {
                balsa.personas[0] = lado1[i];
                lado1[i] = NINGUNA;
                balsa.personas[1] = lado1[j];
                lado1[j] = NINGUNA;
            }

            if (puedeZarpar(balsa, lado0, lado1)) {
                // MEDIANTE ESTE MÉTODO, CAMBIAMOS LA DIRECCION DE NUESTRA BARCA
                balsa.lado++;
                balsa.lado %= 1;

                // BAJAN DE LA BALSA EN EL PUNTO DE DESTINO
                if (balsa.lado == 0) {
                    lado0[i] = balsa.personas[0];
                    balsa.personas[0] = NINGUNA;
                    lado0[j] = balsa.personas[1];
                    balsa.personas[1] = NINGUNA;
                } else if (balsa.lado == 1) {
                    lado1[i] = balsa.personas[0];
                    balsa.personas[0] = NINGUNA;
                    lado1[j] = balsa.personas[1];
                    balsa.personas[1] = NINGUNA;
                }

                if (sePuedeResolver(lado0, lado1, balsa)) {
                    return 1;
                }
            } else {
                // BAJAN DE LA BALSA EN EL PUNTO DE ORIGEN
                if (balsa.lado == 0) {
                    lado0[i] = balsa.personas[0];
                    balsa.personas[0] = NINGUNA;
                    lado0[j] = balsa.personas[1];
                    balsa.personas[1] = NINGUNA;
                } else if (balsa.lado == 1) {
                    lado1[i] = balsa.personas[0];
                    balsa.personas[0] = NINGUNA;
                    lado1[j] = balsa.personas[1];
                    balsa.personas[1] = NINGUNA;
                }
            }
        }
    }

    return 0;
}

// DEFINICION PARA SABER SI PODEMOS CALCULAR MEDIANTE BACKTRACKING EL PROBLEMA PROPUESTO, SI NO SE PUEDE EL PROGRAMA NO CONTINUARÁ

int main() {
    tPersona lado0[N] = {LADRON, POLICIA, PADRE, MADRE, HIJO1, HIJO2, HIJA1, HIJA2};
    tPersona lado1[N] = {NINGUNA, NINGUNA, NINGUNA, NINGUNA, NINGUNA, NINGUNA, NINGUNA, NINGUNA};
    tBalsa balsa = {{NINGUNA, NINGUNA}, 0};

    if (sePuedeResolver(lado0, lado1, balsa)) {
        printf("El programa se puede resolver por Backtracking\n");         // EN EL CASO DE QUE SE PUEDA RESOLVER
    } else {
        printf("Sin solucion, no se puede resolver por Backtracking\n");        // EN EL CASO DE QUE NO SE PUEDA RESOLVER
    }

    return 0;
}

Adjunto el resultado al ejecutar:

vboxuser@Ubuntu22:~/Escritorio$ ./a.out

Violación de segmento (`core' generado)

1 respuesta 1

1

Al depurar el programa con gdb obtengo la siguiente información:

Program received signal SIGSEGV, Segmentation fault.
0x0000005555556978 in esta (persona=PADRE, personas=0x7fff800080, numPersonas=<error reading variable: Cannot access memory at address 0x7fff7ffffc>) at C++/test.c:15
15      int esta(tPersona persona, tPersona personas[], int numPersonas) {

El problema parece estar en el parámetro numPersonas. Extraño cuánto menos ya que no es un puntero ni un arreglo.

Si hago un backtrace obtengo la siguiente información:

#1  0x0000005555556a20 in puedenEstarJuntos (personas=0x7fff800080, numPersonas=2)
at C++/test.c:30
#2  0x0000005555556dac in puedeZarpar (balsa=..., lado0=0x7fffffef40, lado1=0x7fffffef20)
at C++/test.c:52
#3  0x000000555555705c in sePuedeResolver (lado0=0x7fffffef40, lado1=0x7fffffef20, balsa=...)
at C++/test.c:94
#4  0x0000005555557140 in sePuedeResolver (lado0=0x7fffffef40, lado1=0x7fffffef20, balsa=...)
at C++/test.c:112

Revisé las líneas que menciona pero no ví nada fuera de lugar.

Lo que llamó mí atención fue que si hago un backtrace completo obtengo que hay 74862 frames en el stack. Es decir, se han llamado 74861 funciones previamente y están esperando a que la función actual retorne.

Mí hipótesis es que el stack está saturado y sucede lo que se conoce como Stackoverflow.

No es una razón alejada de la realidad ya que la función sePuedeResolver se llama a sí misma en el código.


Algunas formas reducir las posibilidades de que esto ocurra son:

  • Limitar la recursión. Lo más simple es agregar un parámetro que controle la recursión y que cada llamada aumente el valor:

    // La función en tu código no es exactamente así, pero sirve de ejemplo
    int sePuedeResolver(tPersona lado0[], tPersona lado1[], tBalsa balsa, int profundidad = 1){
        // 10000 es el máximo de recursión
        if (profundidad > 10000)
            return 0;
    
        ...
    
        sePuedeResolver(lado0, lado1, balsa, profundidad + 1);
    }
    
  • Reemplazar la recursión.

    Por ejemplo tienes una función que calcula el factorial de un número:

    int factorial(int n){
        if (n <= 0)
            return 1;
    
        return n * factorial(n - 1);
    }
    

    Normalmente puedes hacer una función que haga lo mismo sin recursión. Así:

    int factorial(int n){
        int fac = 1;
        for (int i = 2; i <= n; i++)
            fac *= n;
    
        return fac;
    }
    
1
  • Buenas Mateo, entiendo lo que me quieres comentar. He intentado corregir mi código sin ningún resultado. Por favor, ¿Me podrías presentar cuales serian las modificaciones que harías?. Muchas gracias.
    – HÉCTOR
    Commented el 17 dic. 2022 a las 10:38

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.