elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.


 


Tema destacado: Introducción a la Factorización De Semiprimos (RSA)


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación C/C++ (Moderadores: Eternal Idol, Littlehorse, K-YreX)
| | |-+  [ALGEBRA DE MATRICES] Matriz triangular superior desdendiente en C.
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] 2 Ir Abajo Respuesta Imprimir
Autor Tema: [ALGEBRA DE MATRICES] Matriz triangular superior desdendiente en C.  (Leído 1,293 veces)
dijsktra

Desconectado Desconectado

Mensajes: 100


Mr Edsger Dijsktra (Tribute to)


Ver Perfil
[ALGEBRA DE MATRICES] Matriz triangular superior desdendiente en C.
« en: 1 Mayo 2020, 20:08 »

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:
1 2 3    1 2 3    
0 4 5    0 4 5
0 0 2    0 0 0

Y no lo son

Código:
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:
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
  1. int upperTriangleDesc(const int **A,
  2.      const int N)
  3. {
  4. // Start coding here
  5.    return 0 ;
  6. }
  7.  
  8. int main(int argc, char *args[])
  9. {
  10.  int **A;
  11.  int N;
  12.  for( ; scanf("%d",&N)==1; )
  13.    {
  14.      if  ((A=(int**)malloc(N*sizeof(int *)))==NULL)
  15. {
  16.  perror("calloc");
  17.  exit(1);
  18. }
  19.      for(int n=0;n<N;n++)
  20. {
  21.  if  ((A[n]=(int*)malloc(N*sizeof(int)))==NULL)
  22.    {
  23.      perror("calloc");
  24.      exit(1);
  25.    }
  26.  for(int m=0;m<N;m++)
  27.    if (scanf("%d",&A[n][m])!=1)
  28.      {
  29. perror("scanf");
  30. exit(1);
  31.      }
  32. }
  33.      printf("upperTriangleDesc: %d\n",upperTriangleDesc((const int **)A,N));
  34.      for(int n=0;n<N;n++)
  35. free(A[n]);
  36.      free(A);
  37.    }
  38.  return 0;
  39. }



« Última modificación: 1 Mayo 2020, 21:27 por dijsktra » En línea

Si la depuración es el proceso de eliminar fallos en el software, entonces programar debe ser el proceso de ponerlos dentro. (Edsger Dijsktra)
fary
Colaborador
***
Desconectado Desconectado

Mensajes: 957



Ver Perfil WWW
Re: [ALGEBRA DE MATRICES] Matriz triangular superior desdendiente en C.
« Respuesta #1 en: 1 Mayo 2020, 21:02 »

¿Igual algo así?

Código
  1. int upperTriangleDesc(const int **A, const int N)
  2. {
  3.    int contador = 0;
  4.    int i, a;
  5.  
  6.    for ( i = 1; i < N; i++)
  7.    {
  8.        for (a = 0; a <= contador; a++)
  9.        {
  10.            if (A[i][a] != 0) return 0; // Es incorrecta
  11.        }
  12.        contador++;
  13.    }
  14.  
  15.    return 1 ; // Es correcta
  16. }

Edito quitando la variable contador:

Código
  1. int upperTriangleDesc(const int **A, const int N)
  2. {
  3.    int i, a;
  4.  
  5.    for (i = 1; i < N; i++)
  6.    {
  7.        for (a = 0; a <= (i-1); a++)
  8.        {
  9.            if (A[i][a] != 0) return 0; // Es incorrecta
  10.        }
  11.    }
  12.  
  13.    return 1 ; // Es correcta
  14. }


« Última modificación: 2 Mayo 2020, 07:43 por fary » En línea

Un byte a la izquierda.
K-YreX
Moderador
***
Desconectado Desconectado

Mensajes: 799



Ver Perfil
Re: [ALGEBRA DE MATRICES] Matriz triangular superior desdendiente en C.
« Respuesta #2 en: 1 Mayo 2020, 21:02 »

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
  1. int upperTriangleDesc(const int **A, const int N){
  2. int triangular_superior = 1;
  3. for(size_t i = 1; i < N && triangular_superior; ++i)
  4. for(size_t j = 0; j < i && triangular_superior; ++j)
  5. triangular_superior = (A[i][j] == 0);
  6. return triangular_superior;
  7. }
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 :rolleyes:
En línea

Código
  1. cout << "Todos tenemos un defecto, un error en nuestro código" << endl;
dijsktra

Desconectado Desconectado

Mensajes: 100


Mr Edsger Dijsktra (Tribute to)


Ver Perfil
Re: [ALGEBRA DE MATRICES] Matriz triangular superior desdendiente en C.
« Respuesta #3 en: 1 Mayo 2020, 21:31 »

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
  1. int upperTriangleDesc(const int **A, const int N)
  2. {
  3.    int contador = 0;
  4.    int i, a;
  5.  
  6.    for ( i = 1; i < N; i++)
  7.    {
  8.        for (a = 0; a <= contador; a++)
  9.        {
  10.            if (A[i][a] != 0) return 0; // Es incorrecta
  11.        }
  12.        contador++;
  13.    }
  14.  
  15.    return 1 ; // Es correcta
  16. }
En línea

Si la depuración es el proceso de eliminar fallos en el software, entonces programar debe ser el proceso de ponerlos dentro. (Edsger Dijsktra)
dijsktra

Desconectado Desconectado

Mensajes: 100


Mr Edsger Dijsktra (Tribute to)


Ver Perfil
Re: [ALGEBRA DE MATRICES] Matriz triangular superior desdendiente en C.
« Respuesta #4 en: 1 Mayo 2020, 21:38 »

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
  1. int upperTriangleDesc(const int **A, const int N){
  2. int triangular_superior = 1;
  3. for(size_t i = 1; i < N && triangular_superior; ++i)
  4. for(size_t j = 0; j < i && triangular_superior; ++j)
  5. triangular_superior = (A[i][j] == 0);
  6. return triangular_superior;
  7. }
....
Como echo de menos estas cosas de C/C++ desde que trabajo con Java :rolleyes:
...
Desde luego... Con los Objetos de Java (o de C++) no se puede hacer fácilmete algebra...

« Última modificación: 1 Mayo 2020, 21:40 por dijsktra » En línea

Si la depuración es el proceso de eliminar fallos en el software, entonces programar debe ser el proceso de ponerlos dentro. (Edsger Dijsktra)
NEBIRE


Desconectado Desconectado

Mensajes: 2.337


Ver Perfil
Re: [ALGEBRA DE MATRICES] Matriz triangular superior desdendiente en C.
« Respuesta #5 en: 1 Mayo 2020, 22:00 »

Nota: Se trata como un array unidimensional...
Código:
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).
« Última modificación: 1 Mayo 2020, 22:06 por NEBIRE » En línea

kub0x
Enlightenment Seeker
Colaborador
***
Desconectado Desconectado

Mensajes: 1.371


S3C M4NI4C


Ver Perfil
Re: [ALGEBRA DE MATRICES] Matriz triangular superior desdendiente en C.
« Respuesta #6 en: 1 Mayo 2020, 22:28 »

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
  1. int upperTriangleDesc(const int **A, const int N, int pivot) {
  2.     if (pivot == N) return 1;
  3.     for (int i=0; i<N && pivot < N; i++)
  4.      if (A[pivot++][i] != 0) return 0;
  5. return upperTriangleDesc(A,N,N-i+1);
  6. }

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

P.D : La función ha de llamarse así
Código
  1. upperTriangleDesc((const int **)A,N,1)
« Última modificación: 1 Mayo 2020, 22:37 por kub0x » En línea

Viejos siempre viejos,
Ellos tienen el poder,
Y la juventud,
¡En el ataúd! Criaturas Al poder.

K-YreX
Moderador
***
Desconectado Desconectado

Mensajes: 799



Ver Perfil
Re: [ALGEBRA DE MATRICES] Matriz triangular superior desdendiente en C.
« Respuesta #7 en: 2 Mayo 2020, 00:58 »

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.  :laugh: :laugh:

Pues veamos. La primera opción que aparece es sustituir la variable por el valor de su expresión directamente que es:
Código:
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
  1. int upperTriangleDesc(const int **A, const int N){
  2.    size_t i = 1; j = 0; // Declaramos e inicializamos j para poder usarlo en la condicion del bucle externo
  3.    while(i < N && !A[i][j]){
  4.        // El bucle interno no tiene ninguna complicacion
  5.        while(j < i && !A[i][j]){
  6.            ++j;
  7.        }
  8.        // Ahora al salir tenemos dos situaciones:
  9.        // - (j = i) y en tal caso la matriz todavia es triangular superior -> Incrementamos i y restablecemos j a 0 para recorrer otra fila
  10.        // - (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
  11.        if(j == i){
  12.            ++i;
  13.            j = 0;
  14.        }
  15.    }
  16.    // Los bucles acaban cuando:
  17.    // Un elemento no es nulo (A[i][j] != 0) -> !triangular
  18.    // Llegamos al final (i == N) -> SI A[N-1][N-2] == 0 ENTONCES triangular SINO !triangular
  19.    return (i == N && !A[N-1][N-2]);
  20. }

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
  1. int upperTriangleDesc(const int **A, const int N){
  2.    size_t i = 1, j = 0;
  3.    while(i < N && !j){
  4.        while(j < i && !A[i][j]){
  5.            ++j;
  6.        }
  7.        // Al salir: SI j < i ENTONCES A[i][j] != 0 SINO SI A[i][j-1] == 0 ENTONCES triangular (de momento) SINO !triangular
  8.        j = (j < i) || A[i][j-1];
  9.        ++i;
  10.    }
  11.    // Triangular <-> j = 0
  12.    return !j;
  13. }

A ver qué tal esta vez.  :silbar: :silbar:
En línea

Código
  1. cout << "Todos tenemos un defecto, un error en nuestro código" << endl;
fary
Colaborador
***
Desconectado Desconectado

Mensajes: 957



Ver Perfil WWW
Re: [ALGEBRA DE MATRICES] Matriz triangular superior desdendiente en C.
« Respuesta #8 en: 2 Mayo 2020, 07:46 »

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

Mi código sin contador.

Código
  1.    int upperTriangleDesc(const int **A, const int N)
  2.    {
  3.        int i, a;
  4.  
  5.        for (i = 1; i < N; i++)
  6.        {
  7.            for (a = 0; a <= (i-1); a++)
  8.            {
  9.                if (A[i][a] != 0) return 0; // Es incorrecta
  10.            }
  11.        }
  12.  
  13.        return 1 ; // Es correcta
  14.    }
« Última modificación: 2 Mayo 2020, 07:48 por fary » En línea

Un byte a la izquierda.
@XSStringManolo
<svg/onload=alert()>
Colaborador
***
Desconectado Desconectado

Mensajes: 2.163


Turn off the red ligth


Ver Perfil WWW
Re: [ALGEBRA DE MATRICES] Matriz triangular superior desdendiente en C.
« Respuesta #9 en: 2 Mayo 2020, 11:45 »

Lo hice en javascript. Seguro que se puede hacer mucho más peque.
Código
  1. upperTriangleDesc=A=>{
  2.  for(i=1;i<A.length;++i)
  3.    for(j=0;j<i;++j)
  4.      if(A[i][j])return 0
  5.  ;return 1
  6. }
En línea

Páginas: [1] 2 Ir Arriba Respuesta Imprimir 

Ir a:  

Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines