PDA

Visualizza la versione completa : [c++]Matrici


Matrix_denny
04-05-2004, 08:41
calcolare il determinante di matrici n*n!!

Anªkin
04-05-2004, 11:35
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
04-05-2004, 11:45
potresti scrivere anche un commento su quello che mi hai mandato?

Anªkin
04-05-2004, 11:52
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
04-05-2004, 13:39
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? :ciauz:

Matrix_denny
04-05-2004, 14:54
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
04-05-2004, 15:41
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.
:ciauz:

Matrix_denny
04-05-2004, 15:56
effettivamente il codice funziona ma ho difficolta nel capirlo potresti mandarmi dei commenti soprattutto nella parte dove n>=3
ti ringrazio

Anªkin
04-05-2004, 16:44
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 (http://www.dm.uniba.it/~barile/precorso/algebra_lineare/determinante.doc)) 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
04-05-2004, 18:14
qualcuno e' in grado di fare la conversione di questo programma in c++(sono alle prime armi nella programmazione)

Loading