Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

determinanta problem

[es] :: Art of Programming :: determinanta problem

[ Pregleda: 5437 | Odgovora: 7 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

relaxman

Član broj: 57756
Poruke: 5
*.dial.InfoSky.Net.



Profil

icon determinanta problem09.05.2005. u 01:02 - pre 229 meseci
Imam jedan mali problem sa matricama tj determinantama.
Treba da izracunam determinantu matrice reda nxn,ali ako je "mozda" nekom lakse da radi sa brojevima, matrica moze da bude 3x3.
Isao sam sa 2 for petlje ali algoritam na zalost,mi se ne slaze uvek za "samo" jedan clan u svakom redu.Da ne pominjem da sam ipak
resio problem jer je matrica 3x3, tako sto sam napisao jedan salama izraz sa dve for petlje,ali kako je to "ne programersko" resenje,bio bih zahvalan ako neko moze da mi pomogne.

 
Odgovor na temu

--SOULMaTe--
Nemanja Skoric
Novi Sad

Član broj: 1464
Poruke: 173
*.nat-pool.nsad.sbb.co.yu.



Profil

icon Re: determinanta problem09.05.2005. u 13:50 - pre 229 meseci
Ne mozes da uradis sa 2 for petlje.
Ona prostacka i spora varijanta je da generises sve permutacije u proizvodu i prema parnosti permutacije da odredis znak za svaki cinilac.

A ima i mnogo pametnijih resenja. Cini mi se da postoji jedno divide & conquer resenje.
Podelis determinantu na cetvrtine. A - gornja levo cetvrtina B - gornja desno cetvrtina
C - donja levo cetvrtina D - donja desno cetvrtina

Znaci to ovako nesto izgleda :
A B
C D

I onda izracunas rekurzivno svaku od tih i resenje bude A*D - B*C

E sad nisam siguran u tacnost algoritam al neka me neko ispravi....
Don’t do drugs, sleep deprivation is better.
 
Odgovor na temu

relaxman

Član broj: 57756
Poruke: 5
*.dial.InfoSky.Net.



Profil

icon Re: determinanta problem09.05.2005. u 15:08 - pre 229 meseci
Posto je konkretno determinanta 3x3 kako da je podelim na cetrvrtine?
Zanima me
i za nxn jer mi se vec ranije javljao ovaj problem,ali ipak je sada bitnije 3x3.Treba mi neko elegantnije resenje.Bilo kakva pomoc je dobrodosla.
 
Odgovor na temu

--SOULMaTe--
Nemanja Skoric
Novi Sad

Član broj: 1464
Poruke: 173
*.nat-pool.nsad.sbb.co.yu.



Profil

icon Re: determinanta problem09.05.2005. u 15:55 - pre 229 meseci
Ok, moj "algoritam" nije tacan u potpunosti, pogledacu tacno kako se to radi sto sam opisao.
A za determinantu 3x3 uradis na onaj prvi nacin koji sam opisao. Generisanjem permutacija.
Don’t do drugs, sleep deprivation is better.
 
Odgovor na temu

--SOULMaTe--
Nemanja Skoric
Novi Sad

Član broj: 1464
Poruke: 173
*.nat-pool.nsad.sbb.co.yu.



Profil

icon Re: determinanta problem09.05.2005. u 21:46 - pre 229 meseci
Ako ti je mrsko da trazis neki efiakasan algoritam a oces da uradis za nxn matricu, onda umesto generisanja permutacija lakse mozes da razvijes determinantu po jednoj koloni ili vrsti i rekurzivno je pozoves za svaku od tih novonastalih matrica sve dok ne dodjes do matrice reda 2 kada to samo izracunas jednostavno i vratis rezultat.
Don’t do drugs, sleep deprivation is better.
 
Odgovor na temu

relaxman

Član broj: 57756
Poruke: 5
*.dial.InfoSky.Net.



Profil

icon Re: determinanta problem10.05.2005. u 14:35 - pre 229 meseci
Hvala na pomoci!
SOULMaTe
 
Odgovor na temu

djoka_l
Beograd

Član broj: 56075
Poruke: 3445

Jabber: djoka_l


+1462 Profil

icon Re: determinanta problem26.05.2005. u 13:24 - pre 229 meseci
Evo jednog linka: http://lavica.fesb.hr/mat1/vjezbe/node26.html

Dakle, rekurzivni način računanja determinante razvojem po koloni ili vrsti , pa onda računanje n determinanti je najgori mogući način da se to uradi. Najčešći metdo je Laplasov razvoj (vidi link) gde se matrica svodi na trougaonu, pa je onda det(A) jednak proizvodu elemenata na glavnoj dijagonali.

Ovaj metod se najčešće modifikuje tako što se radi pivotizacija, tj. uvek se uzima onaj red u kojem je element u tekućoj koloni maksimalan. Na primer u prvom koraku se uzima a1k takav da je on maksimalan u prvoj koloni i taj se red zameni sa prvim redom, pa onda se taj red pomnožen sa 1/a1k oduzme od ostalih, pa tako do n. Obrati pažnju da pivotizacija nije neophodna, ali je poželjna, a da svaka zamena dva reda menja znak determinante.

Jedna ispravka: ovo nije Laplasov razvoj nego Gaus-Žordanov, ano se ne varam. Bilo je jako davno :)
 
Odgovor na temu

toroman
Srećko Toroman
www.wowd.com
Beograd / Banja Luka

Član broj: 52673
Poruke: 159
*.dialup.blic.net.

Sajt: toroman.wordpress.com


Profil

icon Re: determinanta problem26.05.2005. u 15:15 - pre 229 meseci
Za determinante 3x3 možeš da koristiš Sarusovo pravilo.

Ali to ne važi za ostale, naravno ... rekurzija je tu najlakže riješenje ...
Programeri su odgovorili na Hamletovo pitanje "Biti il ne biti?" :
0x2B | ~0x2B = 0xFF
(kao ono - ff - teško pitanje!)
 
Odgovor na temu

[es] :: Art of Programming :: determinanta problem

[ Pregleda: 5437 | Odgovora: 7 ] > FB > Twit

Postavi temu Odgovori

Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.