Cuando tienes proyectos sin terminar pero @dijsktra te pica a darle más vueltas a un algoritmo aparentemente sencillo.
Grandeeee.......
Chavalote! Este no te lo puedo bendecir... Tiene un sutil fallo. Te digo cual?Código
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]); }
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]]!
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......
A ver qué tal esta vez.
Código
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.
Bravo... Correcta... pero aun redundante... ya que en
Código
es equivalente a
j=(j<i)||A[i][j-1]
Código
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.
j=(j<i)
(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