Prethodna tema :: Sljedeća tema |
Autor/ica |
Poruka |
Crni Forumaš(ica)


Pridružen/a: 15. 12. 2003. (01:20:43) Postovi: (23C)16
Spol: 
Lokacija: Zagreb
|
Postano: 19:47 čet, 13. 5. 2004 Naslov: Determinanta |
|
|
Napravil' sam program kaj računa determinantu učitane matrice [b]n×n[/b] za učitani broj [b]n[/b]. Stvar radi na principu onog [i]razbijanja[/i] determinante na više manjih determinanta koje reprezentiraju čvorovi u vezanoj listi. Dijelovi strukture su osim matrica (determinanti), broj stupaca (redaka), koeficijent s kojim se množi determinanta i pointer na idući. Učitana matrica dimenzija [b]n×n[/b] se [i]razbija[/i] [b]n-1[/b] puta kako bi se naravno dobili čvorovi čije su dimenzije matrica [b]1×1[/b]. Onda se zbrajaju umnošci brojeva matrice i koeficijenata. Konačni broj čvorova liste nakon [b](n-1)[/b]-vog razbijanja je [b]n![/b]. Problemi nastaju kada je otprilike [b]n>7[/b], jer je tada broj čvorova u listi strašno velik...npr. za [b]n=9[/b] taj broj je [b]362880[/b].
Oslobađanje memorije nisam puno koristil', jer kad sam probal', bilo je još sporije i lošije. Pa ak netko ima ideju kak' da radi bolje, nek se javi, ali sa kodom. Nemojte mi [i]mudrovat' na suho[/i] (to mrzim).
[code:1]#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
typedef struct node
{
int **a;
int n;
int koef;
struct node *nx;
} node;
typedef node* (*fun)(node*);
node* kraj (node *g)
{
node *p,*k;
for (p=g; p!=NULL; p=p->nx)
k=p;
return k;
}
int** rezerviraj (int t)
{
int **a,i,j;
a=(int **) malloc (t*sizeof(int *));
for (i=0; i<t; i++)
a[i]=(int *) malloc (t*sizeof(int));
return a;
}
int** unos1 (int t)
{
int **a,i,j;
a=(int **) malloc (t*sizeof(int *));
for (i=0; i<t; i++)
a[i]=(int *) malloc (t*sizeof(int));
for (i=0; i<t; i++)
{
for (j=0; j<t; j++)
{
printf("a%d%d=",i,j);
scanf("%d",&a[i][j]);
}
}
return a;
}
node* unos (node *g)
{
int t;
node *p;
p=(node *) malloc (sizeof(node));
printf("n=");
scanf("%d",&t);
p->n=t;
p->koef=1;
p->a=unos1(t);
p->nx=NULL;
return p;
}
void ispis (node *g)
{
int i,j;
printf("\n");
for (i=0; i<g->n; i++)
{
for (j=0; j<g->n; j++)
printf("%3d ",g->a[i][j]);
printf("\n");
}
printf("\n");
}
int broj (node *g)
{
node *p;
int t;
t=0;
for (p=g; p!=NULL; p=p->nx)
t++;
return t;
}
int pot (int t)
{
if (t==0)
return 1;
else
return -pot(t-1);
}
int fakt (int t)
{
if (t==0)
return 1;
else
return t*fakt(t-1);
}
node* red1 (node *g, int j)
{
int t,i,r,h;
node *p;
p=(node *) malloc (sizeof(node));
t=(g->n)-1;
p->a=rezerviraj(t);
p->n=t;
p->koef=pot(j)*(g->koef)*(g->a[0][j]);
r=0;
h=0;
while (r<t)
{
if (h!=j)
{
for (i=0; i<t; i++)
p->a[i][r]=g->a[i+1][h];
r++;
}
h++;
}
return p;
}
node* red (node *g)
{
node **p,*d;
int i,t;
t=g->n;
p=(node **) malloc (t*sizeof(node *));
for (i=0; i<t; i++)
p[i]=red1(g,i);
for (i=0; i<t-1; i++)
p[i]->nx=p[i+1];
p[t-1]->nx=NULL;
return p[0];
}
node* reduciraj (node *g, fun f)
{
node **p,*q;
int t,i;
t=broj(g);
p=(node **) malloc (t*sizeof(node *));
i=0;
for (q=g; q!=NULL; q=q->nx)
{
p[i]=red(q);
i++;
}
for (i=0; i<t-1; i++)
f(p[i])->nx=p[i+1];
f(p[t-1])->nx=NULL;
return p[0];
}
main()
{
node *q,*g=NULL,*p;
int s,i,t,*c,*d,j;
g=unos(g);
t=g->n;
ispis(g);
for (i=0; i<t-1; i++)
g=reduciraj(g,kraj);
c=(int *) malloc ((broj(g))*sizeof(int));
d=(int *) malloc ((broj(g))*sizeof(int));
i=0;
for (q=g; q!=NULL; q=q->nx)
{
c[i]=q->a[0][0];
d[i]=q->koef;
i++;
}
s=0;
for (i=0; i<broj(g); i++)
s=s+(c[i]*d[i]);
free(c);
free(d);
printf("\n%d\n",s);
scanf("\n");
}[/code:1]
Imam neki osjećaj da bi ovo moglo krcka interesirat'. :D
Napravil' sam program kaj računa determinantu učitane matrice n×n za učitani broj n. Stvar radi na principu onog razbijanja determinante na više manjih determinanta koje reprezentiraju čvorovi u vezanoj listi. Dijelovi strukture su osim matrica (determinanti), broj stupaca (redaka), koeficijent s kojim se množi determinanta i pointer na idući. Učitana matrica dimenzija n×n se razbija n-1 puta kako bi se naravno dobili čvorovi čije su dimenzije matrica 1×1. Onda se zbrajaju umnošci brojeva matrice i koeficijenata. Konačni broj čvorova liste nakon (n-1)-vog razbijanja je n!. Problemi nastaju kada je otprilike n>7, jer je tada broj čvorova u listi strašno velik...npr. za n=9 taj broj je 362880.
Oslobađanje memorije nisam puno koristil', jer kad sam probal', bilo je još sporije i lošije. Pa ak netko ima ideju kak' da radi bolje, nek se javi, ali sa kodom. Nemojte mi mudrovat' na suho (to mrzim).
Kod: | #include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
typedef struct node
{
int **a;
int n;
int koef;
struct node *nx;
} node;
typedef node* (*fun)(node*);
node* kraj (node *g)
{
node *p,*k;
for (p=g; p!=NULL; p=p->nx)
k=p;
return k;
}
int** rezerviraj (int t)
{
int **a,i,j;
a=(int **) malloc (t*sizeof(int *));
for (i=0; i<t; i++)
a[i]=(int *) malloc (t*sizeof(int));
return a;
}
int** unos1 (int t)
{
int **a,i,j;
a=(int **) malloc (t*sizeof(int *));
for (i=0; i<t; i++)
a[i]=(int *) malloc (t*sizeof(int));
for (i=0; i<t; i++)
{
for (j=0; j<t; j++)
{
printf("a%d%d=",i,j);
scanf("%d",&a[i][j]);
}
}
return a;
}
node* unos (node *g)
{
int t;
node *p;
p=(node *) malloc (sizeof(node));
printf("n=");
scanf("%d",&t);
p->n=t;
p->koef=1;
p->a=unos1(t);
p->nx=NULL;
return p;
}
void ispis (node *g)
{
int i,j;
printf("\n");
for (i=0; i<g->n; i++)
{
for (j=0; j<g->n; j++)
printf("%3d ",g->a[i][j]);
printf("\n");
}
printf("\n");
}
int broj (node *g)
{
node *p;
int t;
t=0;
for (p=g; p!=NULL; p=p->nx)
t++;
return t;
}
int pot (int t)
{
if (t==0)
return 1;
else
return -pot(t-1);
}
int fakt (int t)
{
if (t==0)
return 1;
else
return t*fakt(t-1);
}
node* red1 (node *g, int j)
{
int t,i,r,h;
node *p;
p=(node *) malloc (sizeof(node));
t=(g->n)-1;
p->a=rezerviraj(t);
p->n=t;
p->koef=pot(j)*(g->koef)*(g->a[0][j]);
r=0;
h=0;
while (r<t)
{
if (h!=j)
{
for (i=0; i<t; i++)
p->a[i][r]=g->a[i+1][h];
r++;
}
h++;
}
return p;
}
node* red (node *g)
{
node **p,*d;
int i,t;
t=g->n;
p=(node **) malloc (t*sizeof(node *));
for (i=0; i<t; i++)
p[i]=red1(g,i);
for (i=0; i<t-1; i++)
p[i]->nx=p[i+1];
p[t-1]->nx=NULL;
return p[0];
}
node* reduciraj (node *g, fun f)
{
node **p,*q;
int t,i;
t=broj(g);
p=(node **) malloc (t*sizeof(node *));
i=0;
for (q=g; q!=NULL; q=q->nx)
{
p[i]=red(q);
i++;
}
for (i=0; i<t-1; i++)
f(p[i])->nx=p[i+1];
f(p[t-1])->nx=NULL;
return p[0];
}
main()
{
node *q,*g=NULL,*p;
int s,i,t,*c,*d,j;
g=unos(g);
t=g->n;
ispis(g);
for (i=0; i<t-1; i++)
g=reduciraj(g,kraj);
c=(int *) malloc ((broj(g))*sizeof(int));
d=(int *) malloc ((broj(g))*sizeof(int));
i=0;
for (q=g; q!=NULL; q=q->nx)
{
c[i]=q->a[0][0];
d[i]=q->koef;
i++;
}
s=0;
for (i=0; i<broj(g); i++)
s=s+(c[i]*d[i]);
free(c);
free(d);
printf("\n%d\n",s);
scanf("\n");
} |
Imam neki osjećaj da bi ovo moglo krcka interesirat'.
|
|
[Vrh] |
|
veky Forumaš(ica)

Pridružen/a: 09. 12. 2002. (19:59:43) Postovi: (5B0)16
Lokacija: negdje daleko...
|
Postano: 21:36 čet, 13. 5. 2004 Naslov: Re: Determinanta |
|
|
[quote="Crni"]Napravil' sam program kaj računa determinantu učitane matrice [b]n×n[/b] za učitani broj [b]n[/b]. Stvar radi na principu onog [i]razbijanja[/i] determinante na više manjih determinanta...
...Problemi nastaju kada je otprilike [b]n>7[/b],...
...Pa ak netko ima ideju kak' da radi bolje, nek se javi, ali sa kodom.[/quote]
Dakle... evo jedna zgodna implementacijica nastala u zadnjih ~sat vremena (nisam je imao vremena puno "ušminkati", može se još smanjiti npr. obrtanjem petlji da idu prema dolje...) - radi na istom principu kao i tvoja (Laplaceovo [i]razbijanje[/i], što bi ti rekao: ), samo se ne petlja s listama već cijelu stvar drži u polju. Također, [b]nema kopiranja[/b] - polje je cijelo vrijeme statično u memoriji, a (rekurzivna) funkcija prima kao argumente samo bit-polja redaka i stupaca koje treba uračunati. Radi bez problema (na cromathu) za matrice do 9x9 , pa sam odlučio to staviti i kao simboličnu granicu, uštedjevši još 3 karaktera. ;-)
Ispustivši deklaracije moglo bi se još uštedjeti... ali ovako nema [b]nikakvih warninga[/b] pod cromathovim cc-om.
Čisto kao zgodna protuteža ovoj grdosiji od ~5 ekranâ... :-)
[size=10]int a[9][9],n,i;
d(r,c){int p=1,q=1,g=1,s=0,i=0,j=0;if(!r)return 1;for(;!(r&p);++i)p*=2;
r&=~p;for(;j<9;++j,q*=2)if(c&q)s+=g*a[i][j]*d(r,c&~q),g=-g;return s;}
main(){scanf("%d",&n);for(i=0;i<n*n;++i)scanf("%d",&a[i/n][i%n]);
n=(1<<n)-1;printf(" %d\n",d(n,n));}[/size]
Crni (napisa): | Napravil' sam program kaj računa determinantu učitane matrice n×n za učitani broj n. Stvar radi na principu onog razbijanja determinante na više manjih determinanta...
...Problemi nastaju kada je otprilike n>7,...
...Pa ak netko ima ideju kak' da radi bolje, nek se javi, ali sa kodom. |
Dakle... evo jedna zgodna implementacijica nastala u zadnjih ~sat vremena (nisam je imao vremena puno "ušminkati", može se još smanjiti npr. obrtanjem petlji da idu prema dolje...) - radi na istom principu kao i tvoja (Laplaceovo razbijanje, što bi ti rekao: ), samo se ne petlja s listama već cijelu stvar drži u polju. Također, nema kopiranja - polje je cijelo vrijeme statično u memoriji, a (rekurzivna) funkcija prima kao argumente samo bit-polja redaka i stupaca koje treba uračunati. Radi bez problema (na cromathu) za matrice do 9x9 , pa sam odlučio to staviti i kao simboličnu granicu, uštedjevši još 3 karaktera.
Ispustivši deklaracije moglo bi se još uštedjeti... ali ovako nema nikakvih warninga pod cromathovim cc-om.
Čisto kao zgodna protuteža ovoj grdosiji od ~5 ekranâ...
int a[9][9],n,i;
d(r,c){int p=1,q=1,g=1,s=0,i=0,j=0;if(!r)return 1;for(;!(r&p);++i)p*=2;
r&=~p;for(;j<9;++j,q*=2)if(c&q)s+=g*a[i][j]*d(r,c&~q),g=-g;return s;}
main(){scanf("%d",&n);for(i=0;i<n*n;++i)scanf("%d",&a[i/n][i%n]);
n=(1<<n)-1;printf(" %d\n",d(n,n));}
|
|
[Vrh] |
|
GauSs_ Moderator


Pridružen/a: 28. 01. 2004. (21:01:17) Postovi: (53C)16
Spol: 
Lokacija: 231
|
Postano: 8:20 pet, 14. 5. 2004 Naslov: |
|
|
kao sto sam i prije napisao u dijelu "Uvod u racunarstvo->Rekurzija determinante" :
[code:1]
double* determinanta( double **a, int red_matrice){
int i, j, k, predznak;
double *suma, **pomocna;
suma=(double *) malloc(sizeof( double));
if(red_matrice==1) return *a;
*suma=0;
predznak=1;
pomocna=(double **) malloc(red_matrice*(sizeof(void *)));
if(pomocna==NULL){
puts(":>>> Pogreska pri alociranju memorije");
return NULL;
}
for(i=0;i<red_matrice;i++){
pomocna[i]=(double *) malloc(red_matrice*(sizeof(double )));
if(pomocna[i]==NULL){
puts(":>>> Pogreska pri alociranju memorije");
return NULL;
}
}
for(i=0;i<red_matrice;i++){
for(k=0;k<red_matrice-1;k++){
for(j=0;j<i;j++) pomocna[j][k]=a[j][k+1];
for(j=i;j<red_matrice-1;j++) pomocna[j][k]=a[j+1][k+1];
}
(*suma)+=predznak*a[i][0]*(*(determinanta(pomocna, red_matrice-1)));
predznak*=-1;
}
for(i=0;i<red_matrice;i++) free(pomocna[i]);
free(pomocna);
return suma;
}
[/code:1]
i nije mudrovanje na suho :lol: 8)
kao sto sam i prije napisao u dijelu "Uvod u racunarstvo→Rekurzija determinante" :
Kod: |
double* determinanta( double **a, int red_matrice){
int i, j, k, predznak;
double *suma, **pomocna;
suma=(double *) malloc(sizeof( double));
if(red_matrice==1) return *a;
*suma=0;
predznak=1;
pomocna=(double **) malloc(red_matrice*(sizeof(void *)));
if(pomocna==NULL){
puts(":>>> Pogreska pri alociranju memorije");
return NULL;
}
for(i=0;i<red_matrice;i++){
pomocna[i]=(double *) malloc(red_matrice*(sizeof(double )));
if(pomocna[i]==NULL){
puts(":>>> Pogreska pri alociranju memorije");
return NULL;
}
}
for(i=0;i<red_matrice;i++){
for(k=0;k<red_matrice-1;k++){
for(j=0;j<i;j++) pomocna[j][k]=a[j][k+1];
for(j=i;j<red_matrice-1;j++) pomocna[j][k]=a[j+1][k+1];
}
(*suma)+=predznak*a[i][0]*(*(determinanta(pomocna, red_matrice-1)));
predznak*=-1;
}
for(i=0;i<red_matrice;i++) free(pomocna[i]);
free(pomocna);
return suma;
}
|
i nije mudrovanje na suho
|
|
[Vrh] |
|
defar Forumaš(ica)


Pridružen/a: 19. 01. 2004. (01:37:19) Postovi: (152)16
|
Postano: 20:18 uto, 18. 5. 2004 Naslov: |
|
|
hm...LU faktorizacija? za matricu n*n cije su det vodecih podmatrica do reda n-1 razlicite od nule postoji jedinstveni rastav na gornje U i donjetrokutastu matricu L, td A=LU....rece prof. drmac u petak
a det dijagonalne mat se lako izracuna. moram ic...citamo se.
hm...LU faktorizacija? za matricu n*n cije su det vodecih podmatrica do reda n-1 razlicite od nule postoji jedinstveni rastav na gornje U i donjetrokutastu matricu L, td A=LU....rece prof. drmac u petak
a det dijagonalne mat se lako izracuna. moram ic...citamo se.
_________________ `To begin with, a dog's not mad. You grant that? 'Well, then,' the Cat went on, `you see, a dog growls when it's angry, and wags its tail when it's pleased. Now I growl when I'm pleased, and wag my tail when I'm angry. Therefore I'm mad.'
|
|
[Vrh] |
|
ahri Forumaš(ica)


Pridružen/a: 19. 11. 2003. (23:16:07) Postovi: (193)16
|
|
[Vrh] |
|
krcko Forumaš nagrađen za životno djelo


Pridružen/a: 07. 10. 2002. (15:57:59) Postovi: (18B3)16
|
Postano: 6:57 sri, 19. 5. 2004 Naslov: |
|
|
[quote="ahri"]ima tko istipkano determinantu svodjenjem na trokutastu? da ne tipkam, trea frendici...[/quote]
Nemam, ali to je O(n^3), a grdosija Crnog i vekyjeva komprimirana grdosija O(n!). I ne treba LU faktorizacija, dovoljno je obicnim Gaussovim eliminacijama ubit sve iznad (ili ispod) dijagonale.
ahri (napisa): | ima tko istipkano determinantu svodjenjem na trokutastu? da ne tipkam, trea frendici... |
Nemam, ali to je O(n^3), a grdosija Crnog i vekyjeva komprimirana grdosija O(n!). I ne treba LU faktorizacija, dovoljno je obicnim Gaussovim eliminacijama ubit sve iznad (ili ispod) dijagonale.
_________________ Vedran Krcadinac
Ljudi su razliciti, a nula je paran broj.
|
|
[Vrh] |
|
ahri Forumaš(ica)


Pridružen/a: 19. 11. 2003. (23:16:07) Postovi: (193)16
|
|
[Vrh] |
|
veky Forumaš(ica)

Pridružen/a: 09. 12. 2002. (19:59:43) Postovi: (5B0)16
Lokacija: negdje daleko...
|
|
[Vrh] |
|
krcko Forumaš nagrađen za životno djelo


Pridružen/a: 07. 10. 2002. (15:57:59) Postovi: (18B3)16
|
Postano: 12:22 sri, 19. 5. 2004 Naslov: |
|
|
[quote="ahri"]pa zato i trebam, treba joj racunanje nekih bjesnih determinanti. samo mi se neda kodirat...[/quote]
A ne bi joj MATLAB bio dovoljan? Ako bas mora biti open source, potrazi medju BLAS/LAPACK rutinama.
[quote="veky"][quote]I ne treba LU faktorizacija, dovoljno je obicnim Gaussovim eliminacijama ubit sve iznad (ili ispod) dijagonale.[/quote]
Pa to i nije tako bitno različito... :-)[/quote]
Isto je, ali ti je za determinantu dovoljan U (L mozes zaboraviti).
ahri (napisa): | pa zato i trebam, treba joj racunanje nekih bjesnih determinanti. samo mi se neda kodirat... |
A ne bi joj MATLAB bio dovoljan? Ako bas mora biti open source, potrazi medju BLAS/LAPACK rutinama.
veky (napisa): | Citat: | I ne treba LU faktorizacija, dovoljno je obicnim Gaussovim eliminacijama ubit sve iznad (ili ispod) dijagonale. |
Pa to i nije tako bitno različito...  |
Isto je, ali ti je za determinantu dovoljan U (L mozes zaboraviti).
_________________ Vedran Krcadinac
Ljudi su razliciti, a nula je paran broj.
|
|
[Vrh] |
|
ahri Forumaš(ica)


Pridružen/a: 19. 11. 2003. (23:16:07) Postovi: (193)16
|
|
[Vrh] |
|
|