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

 

 


Tema destacado: Trabajando con las ramas de git (tercera parte)


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación C/C++ (Moderadores: Eternal Idol, Littlehorse, K-YreX)
| | |-+  Determinante matriz de orden 'N'
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: Determinante matriz de orden 'N'  (Leído 12,293 veces)
juancaa

Desconectado Desconectado

Mensajes: 140


[ Img^(Img) = Real ]


Ver Perfil
Determinante matriz de orden 'N'
« en: 7 Febrero 2012, 11:45 am »

Bueno, no hace mucho hice un algoritmo para calcular el determinante de una matriz de orden 'N' en C, se centra basicamente en la deifinicion del calculo del determinante de una matriz de orden 'N'.

Para aquellos que os interese aqui os dejo mi codigo, aunque creo que no contiene errores no estoy seguro, podeis probarlo y decirme que tal, a mi no me ha dado problemas:

Código:
#include <stdio.h>
#define N 100
int sgn (int x);
int read_dim (int *dim);
int matrix_adj (int matrix[N][N], int matrix_aux[N][N], int dim, int m, int n);
int det_matrix_N (int matrix[N][N], int dim);
int det_matrix_adj (int matrix[N][N], int dim, int m, int n);

main() {
int i, j, dim, det, matrix[N][N];
while (!read_dim(&dim))
printf("Dimension no valida (<100).");
printf("\nIntroduzca elementos matriz...\n");
for (i=1; i<=dim; i++) {
printf("Elementos fila %d: ", i);
for (j=0; j<dim; j++)
scanf("%d", &matrix[i-1][j]);
}
if (dim!=1)
det=det_matrix_N(matrix,dim);
else
det=matrix[0][0];
printf("\nDeterminante = %d.\n\n", det);
}

int sgn (int x) {
if (x%2==0) return(1);
return(-1);
}
int read_dim (int *dim) {
int nl;
char aux;
printf("\nIntroduzca dimension matriz cuadrada (<100): ");
nl=scanf("%d", &(*dim));
if (nl!=1) {
scanf("%c", &aux);
while (aux!='\n')
scanf("%c", &aux);
}
if ( (*dim>=100) || (*dim<=0) )
return(0);
return(1);
}
int matrix_adj (int matrix[N][N], int matrix_aux[N][N], int dim, int m, int n) {
int i, j, p, q;
for (j=0, q=0; j<dim; j++)
if (j!=n) {
for (i=0, p=0; i<dim; i++)
if (i!=m) {
matrix_aux[p][q]=matrix[i][j];
p++;
}
q++;
}
return(dim-1);
}
int det_matrix_N (int matrix[N][N], int dim) {
int i, j, dim_aux, det;
for (i=0, j=0, det=0, dim_aux=dim; i<dim; i++)
det+=sgn(i+j)*matrix[i][j]*det_matrix_adj(matrix,dim_aux,i,j);
return(det);
}
int det_matrix_adj (int matrix[N][N], int dim, int m, int n) {
int matrix_aux[N][N];
if ( (matrix_adj(matrix,matrix_aux,dim,m,n)) == 1 )
return(matrix_aux[0][0]);
return(det_matrix_N(matrix_aux,dim-1));
}

Un saludo y espero que os sirva!!


En línea

Que tengas un buen dia!
ghastlyX
Ex-Staff
*
Desconectado Desconectado

Mensajes: 1.900



Ver Perfil
Re: Determinante matriz de orden 'N'
« Respuesta #1 en: 7 Febrero 2012, 12:29 pm »

Mirándolo por encima la idea es correcta, como no haya algún bug tonto parece que tu código es correcto (no lo he ejecutado). Te comento un par de cosas a tener en cuenta:

Para matrices relativamente pequeñas, tu código puede tener overflow puesto que el determinante implica muchos productos. Para evitar esto completamente tendrías que utilizar algún tipo de BigInts.

Más importante es la complejidad de tu algoritmo. El algoritmo de calcular el determinante por adjuntos es útil para hacerlo a mano con matrices pequeñas, pero es muy ineficiente probar todos los adjuntos, ya que deja una complejidad de O(n!), de modo que a partir de matrices de orden 13 o 14, olvídate de que acabe en un tiempo razonable tu programa. Puedes acelerar tu programa siguiendo el mismo algoritmo utilizando programación dinámica donde el estado es por qué fila de la matriz estás y una máscara de bits que indican qué filas puedes utilizar. Esto da un total de n2n estados que necesitan tratarse haciendo un bucle en cada uno, luego la complejidad total subiría a O(n22n), menor que la anterior, aunque igualmente grande.

La manera buena para calcular el determinante es cúbica y se puede hacer de varias maneras. Por ejemplo por eliminación gaussiana o por descomposición LU de la matriz.


En línea

Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
[C] Calcular determinante de una matriz de orden 'n'
Programación C/C++
Kasswed 9 39,753 Último mensaje 24 Enero 2013, 15:37 pm
por flony
[C] [Source] Determinante Matriz orden "N"
Programación C/C++
juancaa 0 3,183 Último mensaje 13 Junio 2012, 02:26 am
por juancaa
Calcular determinante de una matriz NxN
Programación C/C++
amchacon 1 15,437 Último mensaje 13 Febrero 2013, 20:35 pm
por leosansan
[C] Determinante de orden N
Programación C/C++
BatchianoISpyxolo 4 5,263 Último mensaje 31 Marzo 2013, 15:18 pm
por leosansan
programa en turbo c++ que me calcule el determinante de una matriz nxn
Programación General
bmjhon 1 2,429 Último mensaje 8 Noviembre 2016, 05:35 am
por engel lex
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines