[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

[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

[a2000]

sì.

[cionci]

a2000: hai alocato altri vettori, non vale

[a2000]

puntatori. vale.

[a2000]

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