[C] Matrici quadrate (calcolo del det. con Laplace)

[Dark_Tranquillity]

Ciao Cercavo un' algoritmo in C che mi permetta di calcolare il determinante di una matrice con Laplace.

Grazie Mille a chi mi sarà di aiuto...

[fabio_tarantino]

Perchè con Laplace?
Fai prima a trasformare la matrice data in una matrice triangolare superiore e poi calcoli il delta semplicemente moltiplicando gli elementi sulla diagonale principale.

[a2000]

Function f_detm0(a)
Real(8) a( : , : )
Integer ik(1:KK), jk(1:KK)

Do i = 1, KK; ik(i) = i; jk(i) = i; End Do
f_detm0 = f_detm(a, ik, jk, KK)

End Function



Recursive Function f_detm(a, ik, jk, k) Result (detm)
Real(8) a( : , : )
Integer ik(1: ), jk(1: )
Integer ik1(1:k - 1), jk1(1:k - 1)

If (k == 2) Then
detm = a(ik(1), jk(1)) * a(ik(2), jk(2)) - a(ik(1), jk(2)) * a(ik(2), jk(1))
Else
i = 1; iki = ik(i)
Call minore(ik, ik1, i, k)
isgn = 1; detm = 0.0
Do j = 1, k
Call minore(jk, jk1, j, k)
detm = detm + isgn * a(iki, jk(j)) * f_detm(a, ik1, jk1, k - 1)
isgn = -isgn
End Do
End If

End Function



Subroutine minore(ik, ik1, i0, k)
Integer ik(1: ), ik1(1: )

Do i = 1, i0 - 1
ik1(i) = ik(i)
End Do
Do i = i0 + 1, k
ik1(i - 1) = ik(i)
End Do

End Subroutine

[cionci]

Prova con questo:

#include <stdio.h>
#define SIZE 4

void trova_minore(int m[SIZE][SIZE], int size, int r, int c, int minore[SIZE][SIZE])
{
int i1, i2, j1, j2;
for(i1=i2=0; i1<size-1; ++i1,++i2)
{
if(i1 == r) ++i2;
for(j1=j2=0; j1<size-1; ++j1,++j2)
{
if(j1 == c) ++j2;
minore[i1][j1] = m[i2][j2];
}
}
}

int det(int m[SIZE][SIZE], int size, int rp)
{
int minore[SIZE][SIZE], i, j;
int result = 0, detm;
printf("Calcolo determinate di :\n");
for(i=0; i<size; ++i)
{
for(j=0; j<size; ++j)
printf("%5d", m[i][j]);
printf("\n");
}
if(size == 1) return m[0][0];
for(i=0; i<size; ++i)
{
trova_minore(m, size, rp, i, minore);
detm = det(minore, size-1, 0);
result += (m[rp][i]) ? /*se l'elemento è diverso da zero*/
((((rp + i) % 2) ? -1 : 1) * /*-1 se rp+i è dispari altrimenti +1*/
m[rp][i] * detm) /*elmento * det(Aij)*/
: 0; /*ritorna zero se l'elemento è nullo*/
}
return result;
}

int main()
{
int m[SIZE][SIZE];
int i, j;
for(i=0; i<SIZE; ++i)
for(j=0; j<SIZE; ++j)
{
printf("Inserisci il valore dell'elemento (%d,%d): ", i+1, j+1);
scanf("%d", &m[i][j]);
}

printf("Determinante = %d", det(m,SIZE,0));
return 0;
}

[Dark_Tranquillity]

perfetto cionci funziona...grazie

Un'altra domanda è.
Nel testo è specificato che non è possibie utilizzare array per allocare i minori della matrice, che metodo posso usare?

[cionci]

Azzz...come non è possibile ?
Non era meglio se lo dicevi prima ? ;)

Sinceramente ora non mi viene niente in mente...probabilmente si può fare qualcosa con la ricorsione...

[Dark_Tranquillity]

io ho trovato questa funzione in java:

private long det (int [][] matrice, int ordine) {
long risultato = 0;
int [][] nuova;
int pos;

if (ordine == 2)
risultato = matrice[0][0] * matrice[1][1] - matrice[0][1] * matrice[1][0];
else {
nuova = new int[ordine-1][ordine-1];
for (int k=0; k<ordine;k++) {
for (int i=1; i<ordine; i++) {
pos = 0;
for (int j=0; j<ordine; j++)
if (j != k) {
nuova[i-1][pos] = matrice[j];
pos++;
}
}

if ((k % 2) == 0)
risultato = risultato + matrice[0][k] * det(nuova, (ordine-1));
else
risultato = risultato - matrice[0][k] * det(nuova, (ordine-1));
}
}

return risultato;
}



ma come si traduce:
nuova = new int[ordine-1][ordine-1];

[cionci]

Anche quello usa le matrici per contenere i minori...

[cionci]

Ecco qua:

#include <stdio.h>
#define SIZE 5

void scambia_righe(int m[SIZE][SIZE], int size, int r1, int r2, int start)
{
int i, tmp;
for(i=start; i<size; ++i)
{
tmp = m[r1][i];
m[r1][i] = m[r2][i];
m[r2][i] = tmp;
}
}

int det(int m[SIZE][SIZE], int size, int start)
{
int r;
int sgn = 1;
int risultato = 0;

if(start == (size - 1))
return m[size-1][size-1];

for(r=start; r<size; ++r)
{
if(r != start)
{
sgn = -1; /*scambiando due righe il determinante del minore cambia di segno*/
scambia_righe(m, size, start, r, start);
}

risultato += sgn * m[start][start] * det(m, size, start+1);

if(r != start)
scambia_righe(m, size, start, r, start);
}
return risultato;
}

int main()
{
int m[SIZE][SIZE];
int i, j;
for(i=0; i<SIZE; ++i)
for(j=0; j<SIZE; ++j)
{
printf("Inserisci il valore dell'elemento (%d,%d): ", i+1, j+1);
scanf("%d", &m[i][j]);
}

printf("Determinante = %d", det(m,SIZE,0));
return 0;
}

[a2000]

Recursive Function f_detm(a, jk, k) Result(detm)
Real(8) a(1: KK, 1: KK)
Integer jk(1 : k)
Integer jk1(1 : k)

If (k == 2) Then
detm = a(KK - 1, jk(1)) * a(KK, jk(2)) - a(KK - 1, jk(2)) * a(KK, jk(1))

Else
jk1(1:k-1) = jk(2:k)
detm = 0d0 ; isgn = -1
k1=k-1; i = KK - k1
Do j = 1, k
isgn = -isgn
detm = detm + isgn * a(i, jk(j)) * f_detm(a, jk1, k-1)
jk1(j) = jk(j)
End Do

End If

End Function



12 x 12 in 0.10 secondi :D

[fabio_tarantino]

hai usato Laplace per il calcolo del determinante?


Originariamente inviato da a2000

Recursive Function f_detm(a, jk, k) Result(detm)
Real(8) a(1: KK, 1: KK)
Integer jk(1 : k)
Integer jk1(1 : k)

If (k == 2) Then
detm = a(KK - 1, jk(1)) * a(KK, jk(2)) - a(KK - 1, jk(2)) * a(KK, jk(1))

Else
jk1(1:k-1) = jk(2:k)
detm = 0d0 ; isgn = -1
k1=k-1; i = KK - k1
Do j = 1, k
isgn = -isgn
detm = detm + isgn * a(i, jk(j)) * f_detm(a, jk1, k-1)
jk1(j) = jk(j)
End Do

End If

End Function



12 x 12 in 0.10 secondi :D

[a2000]

sì.

[cionci]

a2000: hai alocato altri vettori, non vale ;)

[a2000]

puntatori. vale. :p

[a2000]

Originariamente inviato da Dark_Tranquillity
Nel testo è specificato che non è possibie utilizzare array per allocare i minori della matrice
;)