1

Tengo un problema que me trae de cabeza un par de días. Estoy realizando un programa que busque el elemento máximo y mínimo dentro de una matriz dinámica mediante la técnica Divide y Vencerás. La cosa, es que ejecuto el programa y a la hora de dar el resultado, me sale el mensaje de error "Violación de segmento(`core' generado)" se que es por la condición siguiente: fil_ini < fil_fin && col_ini < col_fin pero si la cambio a fil_ini < fil_fin-1 && col_ini < col_fin-1 si me ejecuta sin dar error pero da una solución incorrecta. Ya que lo que yo busco es que mi caso base para guardar el maximo y el minimo es que fil_ini == fil_fin && col_ini == col_fin

¿Que puedo hacer? ¿En que estoy fallando? Como puedo conseguir que de el resultado correcto sin que acceda a un area de memoria no permitida.

El codigo del programa entero es el siguiente: (Como requisito se pide que n (dimensión de matriz) sea potencia de 2)

#include <iostream>
#include <cmath>
#include <cstdlib>
#include <time.h>

using namespace std;



void algoritmo_dyv(int **mat, int fil_ini, int fil_fin, int col_ini, int col_fin, int &max, int &min){
    int centro_f, centro_c;
    int max_1= 0, max_2= 0, max_3= 0, max_4= 0;
    int min_1= 100, min_2= 100, min_3= 100, min_4= 100;

    if(fil_ini < fil_fin-1 && col_ini < col_fin-1){
        centro_f= (fil_ini+fil_fin)/2;
        centro_c= (col_ini+col_fin)/2;
                algoritmo_dyv(mat,fil_ini,centro_f-1,col_ini,centro_c-1,max_1,min_1);   
        algoritmo_dyv(mat,centro_f,fil_fin,col_ini,centro_c-1,max_2,min_2);
        algoritmo_dyv(mat,centro_f,fil_fin,centro_c,col_fin,max_3,min_3);       
        algoritmo_dyv(mat,fil_ini,centro_f-1,centro_c,col_fin,max_4,min_4);
    //COMBINAR

        if(max_1 > max_2 && max_1 > max_3 && max_1 > max_4 && max_1 > max){
            max= max_1;
        }else if(max_2 > max_1 && max_2 > max_3 && max_2 > max_4 && max_2 > max){
            max= max_2;
        }else if(max_3 > max_1 && max_3 > max_2 && max_3 > max_4 && max_3 > max){
            max= max_3;
        }else if(max_4 > max_1 && max_4 > max_2 && max_4 > max_3 && max_4 > max){
            max= max_4;
        }

        if(min_1 < min_2 && min_1 < min_3 && min_1 < min_4 && min_1 < min){
            min= min_1;
        }else if(min_2 < min_1 && min_2 < min_3 && min_2 < min_4 && min_2 < min){
            min= min_2;
        }else if(min_3 < min_2 && min_3 < min_1 && min_3 < min_4 && min_3 < min){
            min= min_3;
        }else if(min_4 < min_1 && min_4 < min_2 && min_4 < min_3 && min_4 < min){
            min= min_4;
        }

    //CASO BASE

    }else{
            max= min= mat[fil_ini][col_ini];
    }
}

int main(int argc, char const *argv[]){
    int n;
    int num;
    int max= 0, min= 100;
    int **mat;
    struct timespec t0, t1;
    double time;

    if (argc < 2) {
        cerr<<"\nError: El programa se debe ejecutar de la siguiente forma.\n\n";
        cerr<<" ./basico tamCaso\n\n";
        exit(-1);
    }

    n= atoi(argv[1]);

    if((n & (n-1)) == 0){
        cout <<"\nDimension es potencia de dos. "<< endl;
    }else{
        cout <<"\nDimension no es potencia de dos. "<< endl;
        exit(1);
    }

    mat= new int*[n];

    for(int i=0; i<n; i++){
        mat[i]= new int[n];
    }

    cout <<"\nLlenando matriz con numeros aleatorios...";

    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            mat[i][j]= rand() % 101;
        }
    }



    cout <<"\nMatriz llena."<< endl;

    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cout << mat[i][j] <<" ";
        }
        cout << endl;
    }

    cout << endl;

    clock_gettime(CLOCK_REALTIME,&t0); 
    algoritmo_dyv(mat,0,n,0,n,max,min);
    clock_gettime(CLOCK_REALTIME,&t1);

    time=(double)(t1.tv_sec -t0.tv_sec) + (double)(t1.tv_nsec - t0.tv_nsec)/(1.e+9);

    cout <<"\nTiempo de ejecucion: "<< time << endl;

    cout <<"\nSoluc "<< max <<" "<< min << endl;

    for(int i=0; i<n; i++){
        delete[] mat[i];
    }

    delete[] mat;

    return 0;
}

Salu2 camaradas!

2
  • Hola. Yo entiendo que si tu matriz va desde 0 hasta n-1, cuando pases ese valor de n a la función, también la deberás de recorrer desde 0 hasta n-1, o te dará el error que describes. Si no te funciona bien el algoritmo será debido a otro problema, pero no al hecho de recorrer el array entre esos valores.
    – exodehm
    Commented el 12 abr. 2020 a las 20:40
  • Si, de tanto tocar se me olvido poner en la llamada a la función de nuevo los n-1 pero aun con eso, me sigue dando ese error
    – Pablont98
    Commented el 12 abr. 2020 a las 22:07

1 respuesta 1

0

El problema es que no estás gestionando correctamente los límites de cada subcaso:

algoritmo_dyv(mat,0,n,0,n,max,min);

Aquí estás asumiendo que n no es un elemento a buscar, es decir, queda fuera de la búsqueda...

algoritmo_dyv(mat,fil_ini,centro_f-1,col_ini,centro_c-1,max_1,min_1);   
algoritmo_dyv(mat,centro_f,fil_fin,col_ini,centro_c-1,max_2,min_2);
algoritmo_dyv(mat,centro_f,fil_fin,centro_c,col_fin,max_3,min_3);       
algoritmo_dyv(mat,fil_ini,centro_f-1,centro_c,col_fin,max_4,min_4);

Aquí sin embargo la cosa cambia... fíjate que a centro_f y centro_c le restas 1 cuando los pasas como límite superior, es decir, que centro_f-1 y centro_c-1 quedan fuera de la búsqueda.

Prueba así:

    algoritmo_dyv(mat,fil_ini,centro_f,col_ini,centro_c,max_1,min_1);   
    algoritmo_dyv(mat,centro_f,fil_fin,col_ini,centro_c,max_2,min_2);
    algoritmo_dyv(mat,centro_f,fil_fin,centro_c,col_fin,max_3,min_3);       
    algoritmo_dyv(mat,fil_ini,centro_f,centro_c,col_fin,max_4,min_4);
1
  • Muchas gracias! Ha funcionado, el programa ya no da violación de segmento! Todo arreglado, lo agradezco mucho, salu2!
    – Pablont98
    Commented el 13 abr. 2020 a las 17:11

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.