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:
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:
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 ._.
Código (C) [Seleccionar]
#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 ._.
)
