Título: [ALGEBRA DE MATRICES] Matriz triangular superior desdendiente en C. Publicado por: dijsktra en 1 Mayo 2020, 20:08 pm 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 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.0 4 5 2 4 5 0 2 2 0 0 0 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
Título: Re: [ALGEBRA DE MATRICES] Matriz triangular superior desdendiente en C. Publicado por: fary en 1 Mayo 2020, 21:02 pm ¿Igual algo así?
Código
Edito quitando la variable contador: Código
Título: Re: [ALGEBRA DE MATRICES] Matriz triangular superior desdendiente en C. Publicado por: K-YreX en 1 Mayo 2020, 21:02 pm 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:
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 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: Título: Re: [ALGEBRA DE MATRICES] Matriz triangular superior desdendiente en C. Publicado por: dijsktra en 1 Mayo 2020, 21:31 pm Hmmmm... Correcta! ;-) ;-) ;-)
Dos objecciones que lo pueden hacer mejor...
¿Igual algo así? Código
Título: Re: [ALGEBRA DE MATRICES] Matriz triangular superior desdendiente en C. Publicado por: dijsktra en 1 Mayo 2020, 21:38 pm Hmmm.... Correcta! ;-) ;-) ;-)
Una objección:
Se puede conseguir una solucion estructurada y con solo 2 variables locales? ... Desde luego... Con los Objetos de Java (o de C++) no se puede hacer fácilmete algebra... Por lo tanto la solución más sencilla parece un par de bucles que recorran esta parte de la matriz. ..... Código .... Como echo de menos estas cosas de C/C++ desde que trabajo con Java :rolleyes: ... Título: Re: [ALGEBRA DE MATRICES] Matriz triangular superior desdendiente en C. Publicado por: Serapis en 1 Mayo 2020, 22:00 pm 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). Título: Re: [ALGEBRA DE MATRICES] Matriz triangular superior desdendiente en C. Publicado por: kub0x en 1 Mayo 2020, 22:28 pm 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
No será la forma más obvia y eso me gusta :D P.D : La función ha de llamarse así Código
Título: Re: [ALGEBRA DE MATRICES] Matriz triangular superior desdendiente en C. Publicado por: K-YreX en 2 Mayo 2020, 00:58 am Hmmm.... Correcta! ;-) ;-) ;-) Cuando tienes proyectos sin terminar pero @dijsktra te pica a darle más vueltas a un algoritmo aparentemente sencillo. :laugh: :laugh: Una objección:
Se puede conseguir una solucion estructurada y con solo 2 variables locales? 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
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:
Código
A ver qué tal esta vez. :silbar: :silbar: Título: Re: [ALGEBRA DE MATRICES] Matriz triangular superior desdendiente en C. Publicado por: fary en 2 Mayo 2020, 07:46 am Estamos ansiosos de ver tu código dijsktra :rolleyes: ¿Para qué retrasarlo más? :laugh:
Mi código sin contador. Código
Título: Re: [ALGEBRA DE MATRICES] Matriz triangular superior desdendiente en C. Publicado por: @XSStringManolo en 2 Mayo 2020, 11:45 am Lo hice en javascript. Seguro que se puede hacer mucho más peque.
Código
Título: Re: [ALGEBRA DE MATRICES] Matriz triangular superior desdendiente en C. Publicado por: dijsktra en 2 Mayo 2020, 21:56 pm Cuando tienes proyectos sin terminar pero @dijsktra te pica a darle más vueltas a un algoritmo aparentemente sencillo. :laugh: :laugh: Grandeeee....... Chavalote! Este no te lo puedo bendecir... Tiene un sutil fallo. Te digo cual?Código
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
A ver qué tal esta vez. :silbar: :silbar: ;-) ;-) ;-) Bravo... Correcta... pero aun redundante... :rolleyes: ya que en Código es equivalente a 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. (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
Pongo ya mi solucion en el mensaje abajo, para no repetir, en respuesta a fary Título: Re: [ALGEBRA DE MATRICES] Matriz triangular superior desdendiente en C. Publicado por: dijsktra en 2 Mayo 2020, 22:44 pm 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 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 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...! Título: Re: [ALGEBRA DE MATRICES] Matriz triangular superior desdendiente en C. Publicado por: K-YreX en 3 Mayo 2020, 00:40 am Chavalote! Este no te lo puedo bendecir... Tiene un sutil fallo. Te digo cual? Es cierto. No me di cuenta de eso en su momento. Habría que tratar las matrices de orden 1 como un caso aparte: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: Código Aunque claramente no es la mejor solución... :laugh: ;-) ;-) ;-) Bravo... Correcta... pero aun redundante... :rolleyes: ya que en 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:Código es equivalente a Código
Bueno, me quedo con que me he quedado cerca... Este era el de calentamiento, no? :xD Título: Re: [ALGEBRA DE MATRICES] Matriz triangular superior desdendiente en C. Publicado por: fary en 3 Mayo 2020, 20:21 pm dijsktra deberías de poner mas retos como este :P
|