[c++]Matrici

[Matrix_denny]

calcolare il determinante di matrici n*n!!

[Anªkin]

prova con questo:

#define DIM 3
void main()
{
	int m[DIM][DIM];  // definisci tu i valori della matrice

	int diaForward=1, diaBack=1;
	int det=0;

      // popola la matrice

		for (int i=0; i<DIM; i++)
                    {
		for (int j=0; j<DIM; j++)
			{
			diaBack *= m[j][j+i<DIM ? j+i : j+i-DIM];
			diaForward *= m[j][DIM-j-1-i>=0 ? DIM-j-1-i : 2*DIM-j-i-1];
		}
		det+=diaBack-diaForward;
		diaForward = diaBack = 1;
}
printf("\n%d\n", det);
}

[Matrix_denny]

potresti scrivere anche un commento su quello che mi hai mandato?

[Anªkin]

Meglio di no.
Per sicurezza sono andato a controllare, ma il metodo che ho utilizzato credo valga solamente per matrici 3x3. Quindi non fa al caso tuo.

cmq mò controllo meglio!

[Xadoom]

Per matrici nxn credo tu debba andarti a calcolare i complementi algebrici....reminescenze di algebra lineare....ma forse credo proprio ci siano algoritmi già implementati...provato una ricerca sul forum?

[Matrix_denny]

consultando il libro di geometria ho trovato la formula di determinante di matrici n*n :
La sommatoria per j che parte da 1 a n di (a(1j)*A(1j)) per n>=2.
Chi ha confidenza con matrici di 3*3 capira' sicuramente questa formula altrimenti basta scrivere su un motore di ricerca determinante matrici n*n!!!

[Anªkin]

Allora innanzitutto premetto che il codice "dovrebbe" funzionare, ma ovvio che i test li ho fatti solo su 2 matrici una 4x4 e una 5x5 generata da quella 4x4. Quindi non prometto nulla. Se hai esercizi con risultato di matrici con n>3 puoi verificare

Seconda cosa il codice accetta matrici con n>=1.

@xadoom: non volevo cercare uno script già fatto, se no dove sta il gusto


ecco il codice. Ok potevo linkare un file, lo so

#include <stdio.h>
#include <malloc.h>
#include <math.h>

int laplace(int, int **);
int Sarrus(int **, int);


void main()
	{
	int size=0; // dimensione matrice di ingresso
	int **ma;  // matrice di ingresso
	int i, j;

	// chiedo la matrice
	printf("Digita la dimensione della matrice:\n");
	scanf("%d", &size);
	// controllo il valore
	if (size<=0) return; 

		// alloco la memoria della matrice
		ma = (int **)malloc(size*sizeof(int));

	// chiedo i valori della matrice di ingresso
	printf("Digita gli elementi della matrice, riga per riga:\n");

	for (i=0; i<size; i++)
		{
		*(ma+i) = (int *)malloc(size*sizeof(int));
		for (j=0; j<size; j++)
			{
			scanf("%d", &ma[i][j]);
		}	
	}

	// stampo la matrice di ingresso
	for (i=0; i<size; i++)
		{
		for (j=0; j<size; j++)
		printf("%4d ", ma[i][j]);
		printf("\n");
	}

		// a seconda della dimensione prevedo i casi limite con size =1,2,3 ed n
		if (size==1) printf("Determinante: %d", ma[0][0]);
		else if (size==2 || size==3) printf("Determinante: %d", Sarrus(ma, size));
		else printf("Determinante: %d\n",laplace(size, ma));


}
// implementa lo sviluppo di laplace del determinante rispetto alla prima riga
// dato che è indifferente quale riga/colonna prendere la funzione prende la prima riga,
// che è più comodo
int laplace(int ord, int **v)//ord == dimensione di v
	{
			int i, j, z, k=0;
			int det=0;
			int **p; // dichiaro un puntatore ad un array bidimensionale

			int dim_p;

			// dimensione delle sottomatrici
			dim_p = ord-1;
 

	p = (int **)malloc(dim_p*sizeof(int)); // alloco la memoria 
	for (i=0; i<dim_p; i++)
	*(p+i) = (int *)malloc(dim_p*sizeof(int));



for (z=0; z<=dim_p; z++)
	{
	/**********************/
	//creo le sottomatrici
	for (i=1; i<=dim_p; i++)
	{
		for (j=0; j<=dim_p; j++)
		{
		if (j==z) k=1;
		else p[i-1][j-k] = v[i][j];
		}
	k=0;
	}
	/********************************/
	
	// richiamo ricorsivamente la funzione laplace() e per ultima Sarrus()
	if (dim_p>3)
		det+=(int)pow(-1, z+2)*v[0][z]*laplace(dim_p, p);
	else det+=(int)pow(-1, z+2)*v[0][z]*Sarrus(p,3); 
}
	return det;
}

// Implementa la regola di Sarrus
int Sarrus(int **s, int ter)
	{
	int diaForward=1, diaBack=1;
	int det=0;	

	for (int i=0; i<(ter==2 ? 1 : ter); i++){
		for (int j=0; j<ter; j++)
			{
			printf("%d %d\n", j, j+i<ter ? j+i : j+i-ter);
			diaBack *= s[j][j+i<ter ? j+i : j+i-ter];
			diaForward *= s[j][ter-j-1-i>=0 ? ter-j-1-i : 2*ter-j-i-1];
		}
		det+=diaBack-diaForward;
		diaForward = diaBack = 1;
}
return det;
}

P.S.:
Ovvio che probabilmente non funzionerà perché avrò beccato una matrice ***tarda che è un caso particolare e non m'ha fatto rilevare gli errori.

[Matrix_denny]

effettivamente il codice funziona ma ho difficolta nel capirlo potresti mandarmi dei commenti soprattutto nella parte dove n>=3
ti ringrazio

[Anªkin]

Meno male che funziona

Beh per n==1, se non erro il determinante coincide con l'unico elemento della matrice (non ho controllato però).

if (size==1) printf("Determinante: %d", ma[0][0]);

mentre per 2<=n<=3 parte la funzione Sarrus (dall'omonimo Matematico)
e implementa nel caso di n=2 la differenza dei prodotti tra gli elementi delle 2 diagonali Aij = {a11, a12, a21, a22}
quindi det = (a11*a22)-(a12*a21).

for (int i=0; i<(ter==2 ? 1 : ter); i++){
//(ter==2 ? 1 : ter) controlla se la dimensione della matrice
//è uguale a 2. In quel caso basta ciclare una sola volta 
//(cioé non ciclare affatto)  
		for (int j=0; j<ter; j++)
			{
                         // questo printf me lo sono dimenticato, toglilo
			//printf("%d %d\n", j, j+i<ter ? j+i : j+i-ter);
			diaBack *= s[j][j+i<ter ? j+i : j+i-ter];
			diaForward *= s[j][ter-j-1-i>=0 ? ter-j-1-i : 2*ter-j-i-1];
		}
		det+=diaBack-diaForward;
		diaForward = diaBack = 1;
}

per n==3
diaBack calcola la somma dei prodotti delle diagonali con la cima indietro (tipo backslash) mentre diaForward calcola la somma dei prodotti delle diagonali in avanti (tipo forwardslash).
la differenza di diaBack e diaForward da il determinante per matrici 3x3

n>3

In questo caso si utilizza il metodo di laplace. Do per scontato che tu lo sappia (metto un link sotto cmq).


la funzione prende 2 parametri, ord è la dimensione della matrice v, e v è la matrice che passiamo a laplace(). Siccome il metodo di laplace prevede di escludere dalla matrice originale una riga (la prima nel nostro caso) la funzione costruisce ogni volta una sotto matrice di un ordine inferiore rispetto alla precedente, fino ad arrivare a una matrice 3x3. Quindi avendo una matrice 4x4 la funzione esclude la prima riga e costruisce 4 sotto matrici una per ogni elemento della prima riga. Le sotomatrici sono costruite escludendo la colonna a cui appartiene l'elemento della prima riga (dal link si capisce meglio: Link - determinante) Quindi si va a calcolare il determinante delle sottomatrici se queste hanno dimensione 3, mentre si ripete il procedimento precedente se hanno dimensione maggiore di 3. Una volta arrivati a dimensione 3 Sarrus() calcola il determinante per ogni sottomatrice e lo restituisce a laplace (metodo ricorsivo). il determinante viene moltiplicato con il valore dell'elemento che appartiene alla prima riga (quella esclusa) e ogni prodotto viene sommato. La somma da il determinante della matrice.


quindi il primo ciclo (quello con "z") scandisce le colonne da escludere mentre gli altri 2 cicli nidificati (con "i" e "j") leggono la matrice passata alla funzione e prendono i valori da immettere nella nuova sottomatrice z-esima

int laplace(int ord, int **v)//ord == dimensione di v
	{
			int i, j, z, k=0;
			int det=0;
			int **p; // dichiaro un puntatore ad un array bidimensionale

			int dim_p;

			// dimensione delle sottomatrici
			dim_p = ord-1;
 

	p = (int **)malloc(dim_p*sizeof(int)); // alloco la memoria 
	for (i=0; i<dim_p; i++)
	*(p+i) = (int *)malloc(dim_p*sizeof(int));



for (z=0; z<=dim_p; z++)
	{
	/**********************/
	//creo le sottomatrici
	for (i=1; i<=dim_p; i++)
	{
		for (j=0; j<=dim_p; j++)
		{
		if (j==z) k=1;
		else p[i-1][j-k] = v[i][j];
		}
	k=0;
	}
	/********************************/
	
	// richiamo ricorsivamente la funzione laplace() e per ultima Sarrus()
	if (dim_p>3)
		det+=(int)pow(-1, z+2)*v[0][z]*laplace(dim_p, p);
	else det+=(int)pow(-1, z+2)*v[0][z]*Sarrus(p,3); 
}
	return det;
}

Dimmi se c'è altro che non ti è chiaro, il che può essere dato che non mi sono spiegato proprio bene

[Matrix_denny]

qualcuno e' in grado di fare la conversione di questo programma in c++(sono alle prime armi nella programmazione)