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:
1 2 3 1 2 3
0 4 5 0 4 5
0 0 2 0 0 0
Y no lo son
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)
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
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;
}
¿Igual algo así?
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:
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
}
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.
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 :rolleyes:
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
Cita de: fary en 1 Mayo 2020, 21:02 PM
¿Igual algo así?
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
}
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?Cita de: YreX-DwX en 1 Mayo 2020, 21:02 PM
...
Por lo tanto la solución más sencilla parece un par de bucles que recorran esta parte de la matriz.
.....
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 :rolleyes:
...
Desde luego... Con los Objetos de Java (o de C++) no se puede hacer fácilmete algebra...
Nota: Se trata como un array unidimensional...
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).
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.
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 :D
P.D : La función ha de llamarse así upperTriangleDesc((const int **)A,N,1)
Cita de: dijsktra en 1 Mayo 2020, 21:38 PM
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:
A[i][j] == 0dejando el resto del código lo más parecido posible. La solución en tal caso sería algo así:
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:
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. :silbar: :silbar:
Estamos ansiosos de ver tu código dijsktra :rolleyes: ¿Para qué retrasarlo más? :laugh:
Mi código sin contador.
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
}
Lo hice en javascript. Seguro que se puede hacer mucho más peque.
upperTriangleDesc=A=>{
for(i=1;i<A.length;++i)
for(j=0;j<i;++j)
if(A[i][j])return 0
;return 1
}
Cita de: YreX-DwX en 2 Mayo 2020, 00:58 AM
Cuando tienes proyectos sin terminar pero @dijsktra te pica a darle más vueltas a un algoritmo aparentemente sencillo. :laugh: :laugh:
Grandeeee....
Cita de: YreX-DwX en 2 Mayo 2020, 00:58 AM
...
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]);
}
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:
Cita de: YreX-DwX en 2 Mayo 2020, 00:58 AM
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...
Cita de: YreX-DwX en 2 Mayo 2020, 00:58 AM
...
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. :silbar: :silbar:
;-) ;-) ;-) Bravo... Correcta... pero aun redundante... :rolleyes: ya que en
j=(j<i)||A[i][j-1]
es equivalente a
j=(j<i)
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
Cita de: fary en 2 Mayo 2020, 07:46 AM
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...
int upperTriangleDesc(const int **A,
const int N)
{
int i,j;
for (i=1,j=0;i<N && j==i-1; i++)
for(j=0; (j<i) && !A[i][j];j++);
return j==i-1 ;
}
// Outer loop
// I1: Q[N/i] and 1<=i<=M, 0<=j<i and ((j<i-1) -> A[i-1][j]!=0)
// Q1: i = min n : 1 <= n <=N and (n<N->(j<n-1 && ->A[n-1][j]!=0))): n nad
// j = min m : 0 <= m < i and (m<i-1 -> A[i-1][m]!=0))): m
// Quote1(N-i)>=0
// Inner loop
// I2: Q2[N/j] and 0 <= j <= i and i < N
// Q2: i<N and j = min m : 0 <= m <=i and (m<i -> A[i][m]!=0): m
// Quote2(N-j)>=0
, 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...
int upperTriangleDesc(const int **A,
const int N)
{
int i,j;
for (i=1,j=0;i<N && !j; i+=!j)
for(j=i; j && !A[i][j-1];j--);
return i==N;
}
// Outer loop
// I1: Q[N/i] and 1<=i<=N, 0<=j<=i and ((j>0) -> (i<N and A[i][j-1]!=0))
// Q1: i = min n : 1 <= n <=N and (n<N->(j>0 && ->A[n][j-1]!=0))): n nad
// j = max m : 0 <= m <= i and (m>0 -> i<N && A[i][m-1]!=0))): m
// Quote1(N-i-j)>=0
// Inner loop
// I2: Q2[N/j] and i<N and 0 <= j <= i
// Q2: i<N and j = max m : 0 <= m <=i and (m>0 -> A[i][m-1]!=0): m
// Quote2(N-j)>=0
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...!
Cita de: dijsktra en 2 Mayo 2020, 21:56 PM
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:
return (N == 1 || (i == N && !A[N-1][N-2])); Aunque claramente no es la mejor solución... :laugh:
Cita de: dijsktra en 2 Mayo 2020, 21:56 PM
;-) ;-) ;-) Bravo... Correcta... pero aun redundante... :rolleyes: ya que en
j=(j<i)||A[i][j-1]
es equivalente a
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
dijsktra deberías de poner mas retos como este :P