[ALGEBRA DE MATRICES] Matriz triangular superior desdendiente en C.

[dijsktra]

Se pide, dada na matriz de tamaño NxN, N arbitrario, determinar si es una matriz triangular superior decendiente. Esto es, los elementos debajo de la diagonal principal descendiente son todos nulos (no necesariaemente el resto).

Por ejemplo, son triangulares superiores descendientes:

Código [Seleccionar] Expandir


1 2 3    1 2 3    
0 4 5    0 4 5
0 0 2    0 0 0


Y no lo son

Código [Seleccionar] Expandir


1 2 3    1 2 3    
0 4 5    2 4 5
0 2 2    0 0 0

Se facilita el codigo de entrada/salida y unos casos de uso. La primera linea marca la dimension de la matriz cuadrada, N. Las siguientes N lineas dan las filas de la matriz.

ES UN RETO. YO YA TENGO LA SOLUCION. EN UNOS DIAS LA PONGO...
(Se valora la solucion mas imple)

Código [Seleccionar] Expandir


5
1 2 3 0 0
0 4 5 0 0
0 0 0 1 1
0 0 0 3 1
0 0 0 0 1
upperTriangleDesc: 1
3
1 2 3
0 4 5
0 2 0
upperTriangleDesc: 0
3
1 2 3
0 4 5
0 0 0
upperTriangleDesc: 1

Código (c) [Seleccionar] Expandir


int upperTriangleDesc(const int **A,
     const int N)
{
// Start coding here
   return 0 ;
}

int main(int argc, char *args[])
{
 int **A;
 int N;
 for( ; scanf("%d",&N)==1; )
   {
     if  ((A=(int**)malloc(N*sizeof(int *)))==NULL)
{
 perror("calloc");
 exit(1);
}
     for(int n=0;n<N;n++)
{
 if  ((A[n]=(int*)malloc(N*sizeof(int)))==NULL)
   {
     perror("calloc");
     exit(1);
   }
 for(int m=0;m<N;m++)
   if (scanf("%d",&A[n][m])!=1)
     {
perror("scanf");
exit(1);
     }
}
     printf("upperTriangleDesc: %d\n",upperTriangleDesc((const int **)A,N));
     for(int n=0;n<N;n++)
free(A[n]);
     free(A);
   }
 return 0;
}

[fary]

¿Igual algo así?

Código (c) [Seleccionar] Expandir


int upperTriangleDesc(const int **A, const int N)
{
   int contador = 0;
   int i, a;

   for ( i = 1; i < N; i++)
   {
       for (a = 0; a <= contador; a++)
       {
           if (A[i][a] != 0) return 0; // Es incorrecta
       }
       contador++;
   }

   return 1 ; // Es correcta
}

Edito quitando la variable contador:

Código (c) [Seleccionar] Expandir

int upperTriangleDesc(const int **A, const int N)
{
   int i, a;
   
   for (i = 1; i < N; i++)
   {
       for (a = 0; a <= (i-1); a++)
       {
           if (A[i][a] != 0) return 0; // Es incorrecta
       }
   }

   return 1 ; // Es correcta
}

[K-YreX]

Como ya se ha explicado en el enunciado, una matriz es triangular superior descendiente si todos los elementos por debajo de la diagonal principal son nulos, es decir, 0. Por lo tanto el algoritmo debe recorrer única y exclusivamente esta parte de la matriz. El patrón es el siguiente:

• Se empieza en la fila 1
  
• Para cada fila i se recorren las columnas desde 0 hasta i-1.
  
  Por lo tanto la solución más sencilla parece un par de bucles que recorran esta parte de la matriz. Usaremos una variable entera como flag que empezará valiendo 1 (suponemos que la matriz es triangular superior) y cuando encontremos un elemento distinto de 0, dejará de ser triangular superior (cambiaremos el valor a 0) y no será necesario seguir.
  
  Código (c) [Seleccionar] Expandir
  
int upperTriangleDesc(const int **A, const int N){
int triangular_superior = 1;
for(size_t i = 1; i < N && triangular_superior; ++i)
for(size_t j = 0; j < i && triangular_superior; ++j)
triangular_superior = (A[i][j] == 0);
return triangular_superior;
}
  Usamos directamente la comparación de que el elemento (i,j) sea igual a 0. Si dicha comparación es cierta (true) se traducirá como un 1 y en caso de que sea falsa (false), se traducirá como 0.
  Como echo de menos estas cosas de C/C++ desde que trabajo con Java
  

[dijsktra]

Hmmmm... Correcta!

Dos objecciones que lo pueden hacer mejor...

•  Date cuenta que contador=i-1. Luego esa variable es redundante, innecesaria! Basta a<i
•  Desde un punto de vista purista (ojo, esto no le quita valor a lo tuyo)... no es progrmacion estructurada... saliendo del bucle interno con return

¿Igual algo así?

Código (c) [Seleccionar] Expandir


int upperTriangleDesc(const int **A, const int N)
{
   int contador = 0;
   int i, a;

   for ( i = 1; i < N; i++)
   {
       for (a = 0; a <= contador; a++)
       {
           if (A[i][a] != 0) return 0; // Es incorrecta
       }
       contador++;
   }

   return 1 ; // Es correcta
}

[dijsktra]

Hmmm.... Correcta!  

Una objección:

•  La tecnica es estructurada, pero emplea 3 variables... trinangular_superior es redundante...

Se puede conseguir una solucion estructurada y con solo 2 variables locales?

...
Por lo tanto la solución más sencilla parece un par de bucles que recorran esta parte de la matriz.
.....

Código (c) [Seleccionar] Expandir


int upperTriangleDesc(const int **A, const int N){
int triangular_superior = 1;
for(size_t i = 1; i < N && triangular_superior; ++i)
for(size_t j = 0; j < i && triangular_superior; ++j)
triangular_superior = (A[i][j] == 0);
return triangular_superior;
}
....
Como echo de menos estas cosas de C/C++ desde que trabajo con Java
...

Desde luego... Con los Objetos de Java (o de C++) no se puede hacer fácilmete algebra...

[Serapis]

Nota: Se trata como un array unidimensional...

Código [Seleccionar] Expandir


buleano = funcion EsMTSD(array Valores, entero Ancho)
   entero i, j, k, f

   k = size(valores)-1
   f = (Ancho + 1)
   Bucle para j desde Ancho hasta k en incrementos de Ancho
       Bucle para i desde j hasta k en incrementos de f
           Si (Valores(i) <> 0) Devolver FALSE        
       Siguiente
   Siguiente
 
   Devolver TRUE
fin funcion

El bucle externo toma el indice del primer elemento de cada fila (empezando por la 2ª)
El bucle interno recorre a saltos de ancho +1, es decir en avanza en diagonal hasta superar su índice la última fila.
Es decir solo se recorren los valores objetos de búsqueda.


Nótese que 'k' y 'f' son redundantes (se añaden por claridad en el código... aunque también lo hace más eficiente si se tratara de arrays enormes).

[kub0x]

Como ya han comentado algunos compañeros la opción de recorrer fila a fila hasta el elemento anterior al diagonal i=j, pues me he decidido a hacerlo en base a las diagonales de todas las filas. Como bien sabeís, toda fila tiene una diagonal siempre empezando desde el primer elemento es decir, esos elementos están en la primera columna, a_0,0, a_2,0, ..., a_(n-1),0. Entonces, trazando estas diagonales compruebo si el elemento es distinto de 0, si asi fuera, sabemos que no es upper triang.

En cambio, si no detectamos un 0, pasamos a la siguiente diagonal, recursivamente. Para los curiosos, N-i nos da el pivot al inicio de la función UpperTriangleDesc, por lo que si le sumamos 1 es decir N-i+1 siempre tendremos pivot+1. Cuando llegue pivot a ser igual a N, devolvemos 1, y es en efecto upper triang. Para rizar el rizo, implemento recursividad y me deshago de un doble "for" o bucle.

Código (c) [Seleccionar] Expandir

int upperTriangleDesc(const int **A, const int N, int pivot) {
    if (pivot == N) return 1;
    for (int i=0; i<N && pivot < N; i++)
     if (A[pivot++][i] != 0) return 0;
return upperTriangleDesc(A,N,N-i+1);
}

No será la forma más obvia y eso me gusta

P.D : La función ha de llamarse así

Código (c) [Seleccionar] Expandir

upperTriangleDesc((const int **)A,N,1)

[K-YreX]

Hmmm.... Correcta!  

Una objección:

•  La tecnica es estructurada, pero emplea 3 variables... trinangular_superior es redundante...

Se puede conseguir una solucion estructurada y con solo 2 variables locales?

Cuando tienes proyectos sin terminar pero @dijsktra te pica a darle más vueltas a un algoritmo aparentemente sencillo. 

Pues veamos. La primera opción que aparece es sustituir la variable por el valor de su expresión directamente que es:

Código [Seleccionar] Expandir

A[i][j] == 0
dejando el resto del código lo más parecido posible. La solución en tal caso sería algo así:

Código (c) [Seleccionar] Expandir


int upperTriangleDesc(const int **A, const int N){
    size_t i = 1; j = 0; // Declaramos e inicializamos j para poder usarlo en la condicion del bucle externo
    while(i < N && !A[i][j]){
        // El bucle interno no tiene ninguna complicacion
        while(j < i && !A[i][j]){
            ++j;
        }
        // Ahora al salir tenemos dos situaciones:
        // - (j = i) y en tal caso la matriz todavia es triangular superior -> Incrementamos i y restablecemos j a 0 para recorrer otra fila
        // - (A[i][j] != 0) y en tal caso la matriz ya no es triangular superior -> No podemos modificar i ni j para que el bucle de fuera tambien termine
        if(j == i){
            ++i;
            j = 0;
        }
    }
    // Los bucles acaban cuando:
    // Un elemento no es nulo (A[i][j] != 0) -> !triangular
    // Llegamos al final (i == N) -> SI A[N-1][N-2] == 0 ENTONCES triangular SINO !triangular
    return (i == N && !A[N-1][N-2]);
}

Podemos ver que esto se complica mucho y solo para quitar una variable local. Así que tenía que haber otra solución. Existe otro patrón. Cada vez que salimos del bucle interno:

• Todos los elementos de la fila son nulos -> j = i -> triangular (de momento)
  
• El último elemento comprobado no era nulo -> j < i
  En vez de restablecer j a 0, podemos darle a j el valor del último elemento evaluado. Y en el bucle externo bastará comprobar si (j == 0). Esto tiene un problema: si todos los elementos evaluados en una fila son nulos -> j = i -> A(i,j) pertenece a la diagonal principal. Solución:
  
  Código (c) [Seleccionar] Expandir
  
int upperTriangleDesc(const int **A, const int N){
    size_t i = 1, j = 0;
    while(i < N && !j){
        while(j < i && !A[i][j]){
            ++j;
        }
        // Al salir: SI j < i ENTONCES A[i][j] != 0 SINO SI A[i][j-1] == 0 ENTONCES triangular (de momento) SINO !triangular
        j = (j < i) || A[i][j-1];
        ++i;
    }
    // Triangular <-> j = 0
    return !j;
}
  
  A ver qué tal esta vez. 

[fary]

Estamos ansiosos de ver tu código dijsktra   ¿Para qué retrasarlo más?  

Mi código sin contador.

Código (c) [Seleccionar] Expandir

   int upperTriangleDesc(const int **A, const int N)
   {
       int i, a;
   
       for (i = 1; i < N; i++)
       {
           for (a = 0; a <= (i-1); a++)
           {
               if (A[i][a] != 0) return 0; // Es incorrecta
           }
       }
   
       return 1 ; // Es correcta
   }

[@XSStringManolo]

Lo hice en javascript. Seguro que se puede hacer mucho más peque.

Código (javascript) [Seleccionar] Expandir

upperTriangleDesc=A=>{
  for(i=1;i<A.length;++i)
    for(j=0;j<i;++j)
      if(A[i][j])return 0
  ;return 1
}