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


 


Tema destacado: Security Series.XSS. [Cross Site Scripting]


+  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,294 veces)
dijsktra

Desconectado Desconectado

Mensajes: 100


Mr Edsger Dijsktra (Tribute to)


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

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

...
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. }
Chavalote! Este no te lo puedo bendecir... Tiene un sutil fallo. Te digo cual?
Prueba a evaluar la matriz de 1 fila y 1 columna...
El resultado es indeterminado... porque entonces accedes a una posicion tal como A[0][-1]  . Si acierta, dependera del compilador, o de la conjunci'on de los astros...
Que pasa? que las matrices de 1 fila y 1 columna no son matrices???  Prueba [[1]]!  :laugh: :laugh: :laugh:


Podemos ver que esto se complica mucho y solo para quitar una variable local. Así que tenía que haber otra solución.
Ese es el punto... Que tenemos que hacerlo sencillo. Pero claro, con lo bien que lo hiciste al principio, cacda vez queda menos margen...

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

 ;-) ;-) ;-)  Bravo... Correcta... pero aun redundante... :rolleyes: ya que en
Código
  1. j=(j<i)||A[i][j-1]
  2.  
es equivalente a
Código
  1. j=(j<i)
  2.  
En ese punto. N>i>0 siempre. ya que 1<=i<=N (desde el principio 1==1, y siempre aumenta... y por meterse en el primer bucle i<N.
(Si has llegado a j==i, es porque todos los anteriores son 0, en particular, A[j-1]. luego es "por el momento triangular", lo que tu registras poniendo j=0.Si no llegas, a j==i es porque A[j] es distinto de 0, y tu la marcas a 1, "diciendo que no es triangular". Por evaluacion en cortocircuito, no se evalua A[j-1]...

Y como tu dices, se ha hecho mas "compleja de leer" ya que...j
  • Unas veces marca el indice de la columna 0<=j<N A[j] (while)
  • Otras veces marca un predicado booleano {0,1} para saber si es triangular "pr el momento" j=(j<i)||A[j-1]

Pongo ya mi solucion en el mensaje abajo, para no repetir, en respuesta a fary



« Última modificación: 2 Mayo 2020, 23:00 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)
dijsktra

Desconectado Desconectado

Mensajes: 100


Mr Edsger Dijsktra (Tribute to)


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

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

Allá va... Se aceptan criticas...

Con el buen trabajo que hicisteis al principio, había poco margen... De hecho, la tuya es muy dificil de superar, pero no es estructurada... tiene "saltos"... Y el heroe del cual tomo el pseudonimo, dijsktra, maldecia la programación "con saltos"... Esto podia hacer el software muy complejo de mantener, por lo menos en algoritmia, no en programacion de sistemas.

Lo que no todo el mundo sabe es que, sin cuidado, - sin la técnica de derivación- y sin un buen lenguaje -C no es el mejor para la algoritmia, porque le faltan asignaciones multiples y comandos guardados...- la programacion estructurada puede ser tan dificil de mantener ( o mas) que la no estructurada. Aunque en general, siguiendo las directrices de dijsktra (el original, no yo)  es m'as fácil.


La formalizacion que permite demostrarlo rigorusamente esta descrita en comnetarios, pero eso es para cursos avanzados.. Lo dejo para la posteridad que lo quiera conusltar en Internet...

Propongo dos versiones.. Va la primera...

Código
  1. int upperTriangleDesc(const int **A,
  2.      const int N)
  3. {
  4.  int i,j;
  5.  for (i=1,j=0;i<N && j==i-1; i++)
  6.    for(j=0; (j<i) && !A[i][j];j++);
  7.  return j==i-1 ;
  8. }
  9.  
  10. // Outer loop
  11. // I1: Q[N/i] and 1<=i<=M, 0<=j<i and ((j<i-1) -> A[i-1][j]!=0)
  12. // Q1: i = min n : 1 <= n <=N and (n<N->(j<n-1 && ->A[n-1][j]!=0))): n nad
  13. //     j = min m : 0 <= m < i and (m<i-1 -> A[i-1][m]!=0))): m
  14. // Quote1(N-i)>=0
  15. // Inner loop
  16. // I2: Q2[N/j] and 0 <= j <= i and i < N
  17. // Q2: i<N and j = min m : 0 <= m <=i and (m<i -> A[i][m]!=0): m
  18. // Quote2(N-j)>=0
  19.  
  20.  
Grosso modo, la idea es la siguiente...
Al principio, al final y entre vueltas del bucle externo, si j<i-1 entonces sabemos que hemos encontradoun elemento A[i-1][j] distingo de 0, en la zona prohibida... Es un invariante... Y acabamos si hemos llegado a i==N en el caso peor... luego en las anteriores a N, no lo encontrarmos... Aun en i==N podria ser, por loq eu evaluamos j==i-1 en el return... Es como una piedra en el calzado esa utlima linea...es lo que le perdio a
YreX-DwX .  Aun asi, se puede apreciar como los indices i,j se modifican naturalmente, con i++,j++

La segunda, mi favorita...
Código
  1. int upperTriangleDesc(const int **A,
  2.      const int N)
  3. {
  4.  int i,j;
  5.  for (i=1,j=0;i<N && !j; i+=!j)
  6.    for(j=i; j && !A[i][j-1];j--);
  7.  return i==N;
  8. }
  9.  
  10. // Outer loop
  11. // I1: Q[N/i] and 1<=i<=N, 0<=j<=i and ((j>0) -> (i<N and A[i][j-1]!=0))
  12. // Q1: i = min n : 1 <= n <=N and (n<N->(j>0 && ->A[n][j-1]!=0))): n nad
  13. //     j = max m : 0 <= m <= i and (m>0 -> i<N && A[i][m-1]!=0))): m
  14. // Quote1(N-i-j)>=0
  15. // Inner loop
  16. // I2: Q2[N/j] and i<N and 0 <= j <= i
  17. // Q2: i<N and j = max m : 0 <= m <=i and (m>0 -> A[i][m-1]!=0): m
  18. // Quote2(N-j)>=0
  19.  
En esta version, tenemos la fortuna de parar en la primera linea en la que hayamos encontrado el elemento no valido, que resultara estar en A(i)[j-1] si j>0 (Es un invariante)...
O en N, si no lo encontramos...Pero el cambio no es gratuiro.. el avance de i es condicional, i.e. i+=!j

Saludos...Cuidaos del COVID...!





« Última modificación: 4 Mayo 2020, 18:42 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)
K-YreX
Moderador
***
Desconectado Desconectado

Mensajes: 799



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

Chavalote! Este no te lo puedo bendecir... Tiene un sutil fallo. Te digo cual?
Prueba a evaluar la matriz de 1 fila y 1 columna...
El resultado es indeterminado... porque entonces accedes a una posicion tal como A[0][-1]  . Si acierta, dependera del compilador, o de la conjunci'on de los astros...
Que pasa? que las matrices de 1 fila y 1 columna no son matrices???  Prueba [[1]]!  :laugh: :laugh: :laugh:
Es cierto. No me di cuenta de eso en su momento. Habría que tratar las matrices de orden 1 como un caso aparte:
Código
  1. return (N == 1 || (i == N && !A[N-1][N-2]));
Aunque claramente no es la mejor solución... :laugh:

;-) ;-) ;-)  Bravo... Correcta... pero aun redundante... :rolleyes: ya que en
Código
  1. j=(j<i)||A[i][j-1]
es equivalente a
Código
  1. j=(j<i)
El problema fue que me centré en usar A(i, j-1) y entonces comprobé que no era condición suficiente y le añadí el (j < i) pero no vi que ésta sí era suficiente por sí sola...  :rolleyes:
Bueno, me quedo con que me he quedado cerca... Este era el de calentamiento, no? :xD
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 #13 en: 3 Mayo 2020, 20:21 »

dijsktra deberías de poner mas retos como este  :P
En línea

Un byte a la izquierda.
Páginas: 1 [2] Ir Arriba Respuesta Imprimir 

Ir a:  

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