2

He actualizado mi código siguiendo las pautas puntualizadas por las respuestas. La excepción StackOverflow no se ha vuelto a producir, ya que no hay recursividad infinita. Sin embargo, vuelvo a tener un problema: cuando le doy una matriz de orden 8 no devuelve la suma de los elementos de LA MATRIZ. Y es que modifiqué el código para ello en la función main, ya que la función equisuma lo que devuelve es la suma de los elementos de la submatriz equisuma. El enunciado del problema especifica que la matriz que se le da es cuadrada y de N potencia de 2, así que no hay que elaborar el código teniendo en cuenta que la matriz puede no ser cuadrada o de N potencia distinta a 2.

Aquí adjunto mi código actualizado. Muchas gracias por adelantado:

#include <stdio.h>
typedef int MatrizEntero[10][10];


void main( ) {
int ancho;
int resultado;
printf("Deme el ancho de la matriz");
scanf("%d", &ancho);
resultado=equisuma( 0, 0, ancho );
if(ancho>2){
  if(resultado!=-1){
      resultado=resultado*ancho;


  printf("El resultado es %d", resultado);
  }
  else{
      printf("El resultado es %d", resultado);
     }


    }
  if(ancho==2){
  printf("El resultado es %d", resultado);

   }
   }



   int equisuma( int x, int y, int n ) {

   MatrizEntero m={{1,1,1,1,1,1,1,1}, {1,1,1,1,1,1,1,1}, {1,1,1,1,1,1,1,1}, {1,1,1,1,1,1,1,1}, {1,1,1,1,1,1,1,1}, {1,1,1,1,1,1,1,1}, {1,1,1,1,1,1,1,1}, {1,1,1,1,1,1,1,1}};

   int res = 0;
   int sub = 0; //submatriz
   int subSize = 0;//tamaño de submatriz

   if( n == 2 ) {
// Suma de los cuatro elementos
   res = m[x][y] +
         m[x+1][y] +
         m[x][y+1] +
         m[x+1][y+1];

    } else {
// Tamaño de las submatrices
subSize = n / 2;

res = equisuma( x, y, subSize );

if( res != -1 ) {
  sub = equisuma( x + subSize, y, subSize );
  if( ( sub == -1 ) || ( sub != res ) )
    res = -1;
}

if( res != -1 ) {
  sub = equisuma( x, y + subSize, subSize );
  if( ( sub == -1 ) || ( sub != res ) )
    res = -1;
}

if( res != -1 ) {
  sub = equisuma( x + subSize, y + subSize, subSize );
  if( ( sub == -1 ) || ( sub != res ) )
    res = -1;
}
   }

   return res;
   }
5
  • Le quité la etiqueta C# a tu pregunta, porque ese es otro lenguaje de programación que no estás usando es tu código.
    – sstan
    Commented el 6 nov. 2016 a las 16:01
  • De acuerdo, gracias.
    – user22070
    Commented el 6 nov. 2016 a las 21:47
  • No entiendo exactamente lo que quieres hacer. En la matriz de tu ejemplo, { {1 ,1, 1, .... }, ¿ cual sería el resultado esperado ?
    – Trauma
    Commented el 8 nov. 2016 a las 14:21
  • El resultado esperado tendría que ser la suma de los elementos de esa matriz, es decir, 64. Si es equisuma tiene que devolver la suma de todos los elementos de la matriz.
    – user22070
    Commented el 8 nov. 2016 a las 14:26
  • No comprendo por qué razón editas una pregunta que ya tiene una respuesta aceptada. Voy a revertir la edición a la última, y si tienes una nueva pregunta que hacer, pues haz eso, una nueva pregunta. De otra forma, dejas como inválidas las respuestas anteriores.
    – jachguate
    Commented el 13 nov. 2016 a las 18:07

3 respuestas 3

1
int equisuma(MatrizEntero m, int nf, int nc){
  if(nf==2 && nc==2){
    // Calcula la suma
  }
  else{
    // Recursividad con nf/2 y nc/2
  }
}

Imaginemos que a la función le pasamos una matriz de 6x6:

  • Como no es una matriz de 2x2 tenemos recursividad, nf/2=nc/2=3
  • Como sigue sin ser una matriz de 2x2 seguimos con la recursividad. Ahora nf/2=3/2=1
  • Sigue sin ser una matriz de 2x2... nf/2=1/2=0.
  • 0x0 sigue sin ser una matriz de 2x2... ahora empieza lo divertido: 0/2=0. El cálculo anterior implica que la función va a entrar en recursividad infinita hasta que la pila se desborde.

Si quieres resolver este problema con recursividad tienes que tener en cuenta que las dimensiones de la matriz pueden no ser divisibles entre 2.

Por otro lado, tu código está asumiendo que la matriz debe ser cuadrada... y sin embargo pides número de filas y de columnas por separado. En el momento en el que tu matriz no sea cuadrada te vas a encontrar con el mismo problema de recursividad infinita.

Otro problema que tienes es que tu función recursiva únicamente recibe el número de filas y de columnas, pero no indica en qué fila/columna debe empezar el conteo. El resultado es que, de funcionar, únicamente realizará el conteo de las primeras posiciones de la matriz: de (0,0) a (2,2).

Soluciones hay varias y todas pasan por replantearse la forma de operar con la recursividad.

Una posibilidad sería evitar la división. Puedes optar por fragmentar la matriz en cuadrículas de 2x2. Tienes que tener en cuenta que las cuadrículas que queden en los bordes de la matriz pueden acabar siendo de 1x2 y de 2x1.

// función auxiliar para sumar los valores de una matriz de, como mucho, 2x2
int suma2x2(MatrizEntero m, int f, int c, int nf, int nc)
{
  int toReturn = 0;

  int maxf = MIN(f+2,nf);
  int maxc = MIN(c+2,nc);

  for( int i=f ; i<maxf; ++i)
  {
    for( int j=c ; j<maxc; ++j)
    {
      toReturn += m[i][j];
    }
  }

  return toReturn;
}

// Función recursiva.
int equisuma(MatrizEntero m, int nf, int nc, int indexf, int indexc)
{
  int toReturn = suma2x2(m,indexf,indexc,nf,nc);

  if( indexc == 0 && indexf < nf) 
  {
    // Avanzamos al siguiente grupo por filas
    toReturn += equisuma(m,nf,nc,indexf+2,0);
  }

  if( indexc < nc )
  {
    // Avanzamos al siguiente grupo por columnas
    toReturn += equisuma(m,nf,nc,indexf,indexc+2);
  }

  return toReturn;   
}

Esta versión funciona de la siguiente manera:

  • Divide la matriz de grupos de 2x2
  • Empieza en (0,0) e inicia una primera iteración avanzando por filas: (0,0) (2,0), ...
  • Para cada iteración en las filas, realiza una segunda iteración por columnas: Para (0,0) -> (0,2), (0,4), ... Para (2,0) -> (2,2), (2,4), ...

Como ves, las funciones recursivas suelen necesitar como argumentos valores intermedios. Esto puede complicar un poco su uso ya que hay que inicializar correctamente dichos valores para que la función haga su trabajo como es debido.

Para simplificar su uso lo recomendable en estos casos es crear una función privada que realice la recursividad propiamente dicha y una función pública que omita los valores temporales y de inicio a la recursividad:

// La función equisuma del ejemplo anterior renombrada
int equisuma_priv(MatrizEntero m, int nf, int nc, int indexf, int indexc);

// Función pública
int equisuma(MatrizEntero m, int nf, int nc)
{
  return equisuma_priv(m,nf,nc,0,0);
}

int main()
{
  // ...
  resultado=equisuma(mat,n,m);
  // ...
}

La gran ventaja de usar este sistema es que si modificas el algoritmo y la nueva versión requiere diferentes parámetros no tienes que modificar todo tu código, basta con tocar la implementación de la función pública.

Un saludo.

0

Te propongo este otro planteamiento, que utiliza la recursividad.

Los parámetros de la función son:
x, y: posición, dentro de Data, de la esquina superior izquierda de la submatriz a considerar.
size: ancho de la submatriz a considerar. Suponemos que es cuadrada.

int Data[][]; /* Matriz general, principal, o como se quiera decir. */

int equisuma( int x, int y, int size ) {
  int result = 0;
  int sub = 0;
  int subSize = 0;

  if( size == 2 ) {
    /* Devolvemos la suma de los 4 elementos. */
    result = Data[x][y] +
             Data[x+1][y] +
             Data[x][y+1] +
             Data[x+1][y+1];
  } else {
    /* Tamaño de las submatrices. */
    subSize = size / 2;

    result = equisuma( x, y, subSize );

    if( result != -1 ) {
      sub = equisuma( x + subSize, y, subSize );
      if( ( sub == -1 ) || ( sub != result ) )
        result = -1;
    }

    if( result != -1 ) {
      sub = equisuma( x, y + subSize, subSize );
      if( ( sub == -1 ) || ( sub != result ) )
        result = -1;
    }

    if( result != -1 ) {
      sub = equisuma( x + subSize, y + subSize, subSize );
      if( ( sub == -1 ) || ( sub != result ) )
        result = -1;
    }
  }

  return result;
}

void main( ) {
  equisuma( 0, 0, AnchoDeLaMatriz );
}

Como verás, utiliza el clásico esquema de 'divide y vencerás', y creo que se ajusta al enunciado. Tendrás que ajustarlo a los datos exactos de tu problema.

EDITO

#include <stdio.h>

typedef int MatrizEntero[10][10];

int equisuma( int, int, int );

static MatrizEntero m = { { 1, 1, 1, 1, 1, 1, 1, 1 },
                          { 1, 1, 1, 1, 1, 1, 1, 1 },
                          { 1, 1, 1, 1, 1, 1, 1, 1 },
                          { 1, 1, 1, 1, 1, 1, 1, 1 },
                          { 1, 1, 1, 1, 1, 1, 1, 1 },
                          { 1, 1, 1, 1, 1, 1, 1, 1 },
                          { 1, 1, 1, 1, 1, 1, 1, 1 },
                          { 1, 1, 1, 1, 1, 1, 1, 1 } };

void main( ) {
  int ancho;
  int resultado;

  printf( "Deme el ancho de la matriz " );
  scanf( "%d", &ancho );

  resultado = equisuma( 0, 0, ancho );

  if( resultado == -1 ) {
    printf( "La matriz no es equisuma !!\n" );
  } else {
    printf( "El resultado es: %d\n", resultado );
  }
}

int equisuma( int x, int y, int ancho ) {
   int acumulado = 0;
   int subSuma = 0; //submatriz
   int subSize = 0;//tamaño de submatriz

   if( ancho == 2 ) {
    // La matriz tiene un ancho de 2.
    // Comprobamos si los 4 elementos son iguales.
    // Comparamos la esquina superior izquierda con los demás, para
    // aprovechar posibles cachés u optimizaciones del compilador.
    if( ( m[x][y] == m[x+1][y] ) &&
        ( m[x][y] == m[x][y+1] ) &&
        ( m[x][y] == m[x+1][y+1] ) ) {
      acumulado = m[x][y] +
                  m[x+1][y] +
                  m[x][y+1] +
                  m[x+1][y+1];
    } else {
      acumulado = -1;
    }
  } else {
    // Dividimos la matriz en 4 submatrices, y las vamos comprobando
    // secuencialmente.

    // Tamaño de las submatrices
    subSize = ancho / 2;

    // Esquina superior izquierda.
    // Al ser la primera llamada, no hay que comprobar nada.
    acumulado = equisuma( x, y, subSize );

    // Si era equisuma, comprobamos la esquina superior derecha.
    if( acumulado != -1 ) {
      subSuma = equisuma( x + subSize, y, subSize );
      acumulado = subSuma == -1 ? -1 : acumulado + subSuma;
    }

    // Esquina inferior izquierda.
    if( acumulado != -1 ) {
      subSuma = equisuma( x, y + subSize, subSize );
      acumulado = subSuma == -1 ? -1 : acumulado + subSuma;
    }

    // Esquina inferior derecha.
    if( acumulado != -1 ) {
      subSuma = equisuma( x + subSize, y + subSize, subSize );
      acumulado = subSuma == -1 ? -1 : acumulado + subSuma;
    }
  }
  return acumulado;
}

El código modificado divide recursivamente la matriz en submatrices de la mitad de tamaño, hasta que son de 2x2. Si los 4 valores de esa matriz de 2x2 son iguales, los suma y devuelve el resultado. Si los 4 valores no son iguales, devuelve -1. Ese -1 es devuelto a todas las llamadas recursivas previas.

El resultado final es que solo suma los valores si todos son iguales. Si algún valor es distinto, muestra el mensaje 'no es equisuma'.

El código está profusamente comentado, siendo fácil de modificar. Los 3 if finales dentro de equisuma() controlan las condiciones de las sumas, junto a los ? :

Una última cosa. Colocar m = { . . . } dentro de la función equisuma() es una aberración. Estás llenando la pila con información duplicada completamente inútil. Declararla al principio del archivo, y acceder a ella es mucho mejor ( Esto es otra aberración en si mismo. Lo ideal sería pasar un puntero a la matriz con los datos en cada llamada a equisuma(), pero en este caso concreto no aporta nada; es más, creo que dificulta la lectura e interpretación del código).

11
  • 1
    No pongas dos respuestas distintas. Añade el nuevo ejemplo a tu respuesta original. Tienes un botón de "editar" justo debajo de la misma. Commented el 6 nov. 2016 a las 16:02
  • Ok. Novato en el sitio. En mi descarga, me pareció lo suficientemente diferente como para merecer una respuesta aparte. No volverá a ocurrir.
    – Trauma
    Commented el 6 nov. 2016 a las 18:33
  • Muchísimas gracias por la ayuda.
    – user22070
    Commented el 6 nov. 2016 a las 21:00
  • Muchas gracias por su respuesta. ¿Le importaría decirme cuál es la función del operador ?: ? No tengo mucha experiencia usando C, así que desconozco lo que hace.
    – user22070
    Commented el 13 nov. 2016 a las 12:11
  • Te lo digo si puntuas la respuesta (le das a la flechita para arriba) y la acpetas (el simbolo del check).
    – Trauma
    Commented el 13 nov. 2016 a las 15:13
0

No estoy seguro de lo que quieres hacer, pero te sugiero algunos cambios en tu planteamiento:

Una matriz 2x2 puede tratarse como un array de 4 elementos consecutivos.

typedef int Atom[4];

Una matriz mayor de 2x2 puede tratarse como un array de Atom.

La suma de un Atom es trivial ( [0] + [1] + [2] + [3] )

La suma de una matriz es la suma iterativa de varios Atom.

typedef int Atom[4];
typedef Atom *Array;

int sumaAtom( Atom v ) { return v[0] + v[1] + v[2] + v[3]; }

int sumaArray( Array, sizeX, sizeY ) {
  int x,
      y,
      acu = 0;

  for( x = 0; x < sizeX; ++x ) {
    for( y = 0; y < sizeY; ++y ) {
      acu += sumaAtom( Array[x][y] );
    }
  }

  return acu;
}

Te repito que no estoy seguro de lo que quieres hacer, y si es una práctica sobre recursividad este planteamiento alternativo no es válido, pero sin duda es mucho más práctico y menos proclive a errores.

1
  • Por desgracia, se exige el uso de la recursividad en este problema. Adjunto el enunciado del ejercicio, gracias por adelantado: Dada una matriz de enteros mayores o iguales a cero de dimensión NxN con N potencia de 2, se dice que esa matriz es “equisuma” si los elementos de las 4 submatrices que la componen suman lo mismo y a su vez cada submatriz es también equisuma. Además, una matriz de 2x2 siempre se considera equisuma.
    – user22070
    Commented el 6 nov. 2016 a las 12:26

Tu Respuesta

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