A partir del título de este post ( http://foro.elhacker.net/programacion_cc/determinante_matriz_de_orden_n-t352910.0.html ) me entró la curiosidad de resolverlo de manera dinámica. Y la manera que se me ocurría para un algoritmo sencillo pues es la regla de Laplace o el desarrollo por menores complementarios de manera recursiva:
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define N 4
/* DETERMINANTE DE UNA MATRIZ de orden N - por MAFH */
typedef int ** matriz;
void visualizar_matriz (matriz matrix, int m, int n) {
int i,j;
for (i=0; i<m; i++) {
for(j=0; j<n; j++) {
printf("%d ", matrix[i][j]);
}
printf("\n");
}
}
matriz generar_matriz (int m, int n) {
int i;
matriz temp;
if ((temp = (matriz) malloc(m*sizeof(int*))) == NULL)
return NULL;
for (i=0; i<m; i++)
if ((temp[i] = (int *)malloc(n*sizeof(int))) == NULL)
return NULL;
return temp;
}
matriz copiar_matriz (matriz matrix, int m, int n) {
int i,j;
matriz temp = (matriz) generar_matriz(m,n);
if (temp != NULL) {
for (i=0; i<m; i++)
for (j=0; j<n; j++)
temp[i][j] = matrix[i][j];
}
return temp;
}
void liberar_matriz (matriz matrix, int m) {
int i;
for (i=0; i<m; i++)
free(matrix[i]);
free(matrix);
}
void rellenar_matriz (matriz matrix, int m, int n) {
int i,j;
for (i=0; i<m; i++)
for(j=0; j<n; j++) {
printf("Valor de matrix[%d,%d] = ", i, j);
scanf("%d", &(matrix[i][j]));
}
}
matriz adjunto_matriz (matriz matrix, int fila, int columna, int n) {
matriz adjunto = (matriz) generar_matriz(n-1,n-1);
if (adjunto != NULL) {
int i, j, k=0, l=0;
for (i=0; i<n; i++)
for (j=0; j<n; j++) {
if ((i != fila) && (j != columna)) {
adjunto[k][l] = matrix[i][j];
if (++l == n-1) {
l=0;
k++;
}
}
}
}
return adjunto;
}
int determinante (matriz matrix, int n) {
if (n == 1) {
return matrix[0][0];
} else {
int j;
int res = 0;
for (j=0; j<n; j++){
matriz adjunto = (matriz) adjunto_matriz(matrix, 0, j, n);
if (adjunto == NULL) exit(1);
res += pow(-1, (j%2))*matrix[0][j]*determinante(adjunto, n-1);
liberar_matriz(adjunto,n-1);
}
return res;
}
}
int main (int argc, char ** argv) {
matriz m = (matriz) generar_matriz(N,N);
rellenar_matriz(m,N,N);
visualizar_matriz(m,N,N);
printf("|M| = %d\n", determinante(m,N));
liberar_matriz(m,N);
return 0;
}
Aunque tenemos la constante N para el orden de la matriz, podemos utilizar una variable para que el usuario introduzca el orden, evidentemente.
Una ejecución del código con Valgrind:
Citarpyxolo@ubuntu:~/Escritorio$ gcc -o det determinanteN.c -lm
pyxolo@ubuntu:~/Escritorio$ valgrind ./det -all
==4938== Memcheck, a memory error detector
==4938== Copyright (C) 2002-2011, and GNU GPL'd, by Julian Seward et al.
==4938== Using Valgrind-3.7.0 and LibVEX; rerun with -h for copyright info
==4938== Command: ./det -all
==4938==
Valor de matrix[0,0] = 2
Valor de matrix[0,1] = 3
Valor de matrix[0,2] = -4
Valor de matrix[0,3] = 2
Valor de matrix[1,0] = 9
Valor de matrix[1,1] = 11
Valor de matrix[1,2] = 0
Valor de matrix[1,3] = 3
Valor de matrix[2,0] = 2
Valor de matrix[2,1] = -4
Valor de matrix[2,2] = -5
Valor de matrix[2,3] = -6
Valor de matrix[3,0] = 21
Valor de matrix[3,1] = 100
Valor de matrix[3,2] = 2
Valor de matrix[3,3] = 3
2 3 -4 2
9 11 0 3
2 -4 -5 -6
21 100 2 3
|M| = -23240
==4938==
==4938== HEAP SUMMARY:
==4938== in use at exit: 0 bytes in 0 blocks
==4938== total heap usage: 105 allocs, 105 frees, 752 bytes allocated
==4938==
==4938== All heap blocks were freed -- no leaks are possible
==4938==
==4938== For counts of detected and suppressed errors, rerun with: -v
==4938== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
Conclusión del desarrollo por menores:
Orden 1:
1 de orden 1
no llamadas recursivas
Orden 2:
2 de orden 1
2 = 2 llamadas recursivas
Orden 3:
3 de orden 2
2 de orden 1
3*2 = 6 llamadas recursivas
Orden 4:
4 de orden 3
3 de orden 2
2 de orden 1
4*3*2 = 24 llamadas recursivas
Orden 5:
5 de orden 4
4 de orden 3
3 de orden 2
2 de orden 1
5*4*3*2 = 120 llamadas recursivas
Orden n:
n de orden n-1
n-1 de orden n-2
.... de orden ...
3 de orden 2
2 de orden 1
n*(n-1)*(n-2)*(n-3)*...*(n-n+1) = (productorio desde i=n hasta 2 de i) = n! llamadas recursivas
Como conclusión a los resultados expuestos obtenemos que el número de llamadas recursivas que se realizan viene dado por:
Nº llamadas recursivas = Permutaciones(Orden) = Orden!Como bien había dicho
ghastlyX en respuesta al tema arriba enlazado.
Edit:
He tratado de lanzar el código con un determinante de orden 13 y evidentemente "no terminaba"...
Nº llamadas recursivas = P(13) = 13! = 6227020800
T(n) es exponencial y encima con los alojos y desalojos de memoria... Para morirse xD
Por otra parte, convendría generar los adjuntos con la misma matriz que se usa o de alguna manera sin generar otra matriz de tamaño n-1 para cada adjunto ._.
Buena idea, yo hize también un algoritmo recursivo pero en C++... Andara por algun lugar de este foro.
El determinante es una operacion complej, hacer un determinante de 20x20 puede trardar semanas (y me quedo corto).
Cita de: amchacon en 29 Marzo 2013, 21:41 PM
El determinante es una operacion complej, hacer un determinante de 20x20 puede trardar semanas (y me quedo corto).
Es que el sistema que utilizan es de "fuerza bruta".
Para hacerlo razonable habría que usar Gauss con/sin pivotes.
Saluditos!, ....(http://st.forocoches.com/foro/images/smilies/aaaaa.gif)
Cita de: leosansan en 30 Marzo 2013, 05:11 AM
Es que el sistema que utilizan es de "fuerza bruta".
Para hacerlo razonable habría que usar Gauss con/sin pivotes.
Saluditos!, ....(http://st.forocoches.com/foro/images/smilies/aaaaa.gif)
No, ya, ya. diagonalizar la matriz para obtener la solución con el producto de los elementos de la diagonal principal xD Pero para diagonalizar la matriz... xD No sabría como hacerlo de forma eficiente. Aunque bueno, debería tratar de pensarlo para afirmar eso xD
Cita de: BatchianoISpyxolo en 30 Marzo 2013, 07:05 AM
.......................................
Pero para diagonalizar la matriz... xD No sabría como hacerlo de forma eficiente.
........................................
No es tan complicado, al menos sin pivote. Un ejemplo:
/* Función para triangularizar una matriz */
/************************************************/
int triang(int N, double **a, double *b)
{
int i, j, k, error;
double fac;
for (k=0; k<N-1; k++)
for (i=k+1; i<N; i++)
{
if (fabs(a[k][k])<EPS) return -1;
fac=-a[i][k]/a[k][k];
for (j=k; j<N; j++)
{
a[i][j]+=a[k][j]*fac;
}
b[i]=b[i]+b[k]*fac;
}return 1;
}
/* Función para resolver un sistema triangular superior */
/************************************************/
Saluditos!. ...(http://st.forocoches.com/foro/images/smilies/simba2.gif)