Srodne teme
11.12.2001. Paskal, nije mi jasno...
25.03.2002. Problem sa sumiranjem
29.03.2002. Brute force
20.11.2006. Help !!!
03.07.2003. Mendeljejev periodni sistem elemenata
12.09.2003. NIZ
19.02.2004. problem sa matricama
Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

pronalaženje podmatrice sa najvećom vrednošću zbira elemenata

[es] :: Art of Programming :: pronalaženje podmatrice sa najvećom vrednošću zbira elemenata

[ Pregleda: 4355 | Odgovora: 9 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

Goran Rakić
Beograd

Član broj: 999
Poruke: 3766

Sajt: blog.goranrakic.com


+125 Profil

icon pronalaženje podmatrice sa najvećom vrednošću zbira elemenata30.11.2002. u 21:32 - pre 259 meseci
Danas sam gledao ovaj zadatak, "razbijao" glavu i nemam uopšte ideju. Da napomenem, zadatak nije niti za ocenu, niti za školu, niti ja imam rok do kada trebam da ga uradim. Čista razonoda. Siguran sam da nije težak, ali...

Naime, data je kvadratna matrica (dvodimenzionalan niz) n x n (n kolona i n redova). Treba naći koordinate početka i kraja glavne dijagonale podmatrice (ne mora biti kvadratna) koja ima najveću sumu elemenata. Svi elementi su celi brojevi, u rasponu od -100000 do 100000, a n je manje ili jednako 60. Znači za matricu:

Code:

  1   1   1   0  -50
  1  -9   1   0    0
  1   2   1   1    1
  0   0   1   8    1
 -50  0   1   1    1


treba pronaći 3 2 5 5, jer je najveća vrednost zbira elemenata u podmatrici čija glavna dijagonala počinje u preseku 3 reda i 2 kolone (broj 2), a završava u preseku 5 reda i 5 kolone (broj 1).

U principu, u ekstremnom slučaju, da su svi elementi pozitivni, najveća podmatrica bi bila sama matrica. Kako je n veliko (max 60) samo izračunavanje svih kombinacija ne dolazi u obzir. Onda sam razmišljao da počnem od matrice označene sa 1 1 2 2 (ako uzmemo da matrica počinje sa index-om 1) pa onda izračunam matricu 1 1 2 3 i tako dalje, ali sam se pogubio kada sam uzeo da n može da bude i neparno, a opet mi se čini mnogo "prolaza".

Onda sam najviše razmišljao o ideji da iz svakog koraka u sledeći mogu na 8 različitih načina. ("smaknem" prvi red, zadnji red, prvu ili zadnju kolonu, kao i kombinacije prvi red i prva kolona, prva kolona i zadnji red, zadnji red i druga kolona, druga kolona i prvi red) Stoga mogu "probati" tih 8 vrednosti na osnovu pozicije gl. dijagonale trenutne podmatrice i odabrati najmanju, jer njenim eliminisanjem dobijam naveću preostalu vrednost. Mana toga je što ako u prvom koraku odem na 3 izbor (druga kolona) onda možda neću ni stići do neke kombinacije u kojoj sam trebao sačuvati tu treću kolonu. (ala sam ovo objasnio, ali nadam se da kapirate).

Da sortiram matricu ne mogu, jer mi trebaju koordinate.

Imate li neke ideje?
http://sr.libreoffice.org — slobodan kancelarijski paket, obrada teksta, tablice,
prezentacije, legalno bez troškova licenciranja
 
Odgovor na temu

Dragoslav Krunić

Član broj: 225
Poruke: 1083
*.rcub.bg.ac.yu



Profil

icon Re: pronalaženje podmatrice sa najvećom vrednošću zbira elemenata30.11.2002. u 23:38 - pre 259 meseci
Zaista interesantan i na prvi pogled lak zadatak. Baš ću da pokušam. Očekujte rešenje u Perlu, a posle je lako to prebaciti u drugi programski jezik ako je potrebno...
 
Odgovor na temu

dRock9
Kragujevac - Beograd

Član broj: 4217
Poruke: 54
*.ptt.yu



Profil

icon Re: pronalaženje podmatrice sa najvećom vrednošću zbira elemenata04.12.2002. u 11:30 - pre 259 meseci
Prvo, ako moze jedna mala ispravka : Matrica koja nije kvadratna NEMA dijagonalu (ni glavnu ni sporednu).....

Drugo: Ovaj tvoj problem spada u kategorijiu poznatih problema koji se resvavaju tehnikom, tzv. dinamickog programiranja (nema veze sa dinamickim strukturama - listama, drvetima i ostalo). Potrudicu se da iskucam resenje pa cu tada da post-ujem i vise objasnjenja, a ti si deo ideje (koju doduse treba doterati, malko) vec dao - ono sa vrstama i kolonama, dodavanje i oduzimanje - sta vise mislim da je slican (ako ne i isti) problem postavljen na nekom takmicenju ranije....

pozdrav, ocekuj source uskoro (Perl ne znam, ali potrudicu se da to bude citljiv C kod...)
 
Odgovor na temu

Goran Rakić
Beograd

Član broj: 999
Poruke: 3766

Sajt: blog.goranrakic.com


+125 Profil

icon Re: pronalaženje podmatrice sa najvećom vrednošću zbira elemenata04.12.2002. u 13:28 - pre 259 meseci
Da bio je 1998. godine na regionalnom, a bio je sličan i u Makedoniji na republickom *97. godine, ali rešenje nigde ne mogu da nađem. Rešenje znam i ja da je tehnikom dinamičkog programiranja, ali ne mogu da pronađem kako tačno. Očekujem source. ;)
http://sr.libreoffice.org — slobodan kancelarijski paket, obrada teksta, tablice,
prezentacije, legalno bez troškova licenciranja
 
Odgovor na temu

Rapaic Rajko
Bgd

Član broj: 4105
Poruke: 810
80.93.225.*



+62 Profil

icon Re: pronalaženje podmatrice sa najvećom vrednošću zbira elemenata06.12.2002. u 10:27 - pre 259 meseci
Sjajan post (mislim na opis algoritma); toliko dobar da je nasao mesto u mojoj kolekciji dragulja.
Inace, zivo me zanima kako si zamislio optimizaciju. Ja vec vidim neki put ka brzem racunanju Item-a pomocne matrice: tu se stalno sabiraju jedne te iste vrednosti...hm, hm, hm...nesto mi se kuva...
Pozdrav

Rajko
 
Odgovor na temu

Ivan Dimkovic

Administrator
Član broj: 13
Poruke: 16683
*.telemaxx.net



+7169 Profil

icon Re: pronalaženje podmatrice sa najvećom vrednošću zbira elemenata06.12.2002. u 10:50 - pre 259 meseci
Ahh

Ja se izvinjavam - slucajno sam obrisao poruku umesto da skinem .zip file

Zamolio bih autora algoritma da ponovo postuje algo :(((((((


Izvinjavam se again!!!


DigiCortex (ex. SpikeFun) - Cortical Neural Network Simulator:
http://www.digicortex.net/node/1 Videos: http://www.digicortex.net/node/17 Gallery: http://www.digicortex.net/node/25
PowerMonkey - Redyce CPU Power Waste and gain performance! - https://github.com/psyq321/PowerMonkey
 
Odgovor na temu

Goran Rakić
Beograd

Član broj: 999
Poruke: 3766

Sajt: blog.goranrakic.com


+125 Profil

icon Re: pronalaženje podmatrice sa najvećom vrednošću zbira elemenata06.12.2002. u 14:25 - pre 259 meseci
hoćeš da kažeš da je ovde bilo rešenje???? NEE" for(i=0;i<10;i++) printf("E"); "!!! ;)
http://sr.libreoffice.org — slobodan kancelarijski paket, obrada teksta, tablice,
prezentacije, legalno bez troškova licenciranja
 
Odgovor na temu

dRock9
Kragujevac - Beograd

Član broj: 4217
Poruke: 54
*.ptt.yu



Profil

icon Re: pronalaženje podmatrice sa najvećom vrednošću zbira elemenata07.12.2002. u 19:20 - pre 259 meseci
Ok, nema problema evo algoritama.

matrica.zip je onaj stari, a optimizovano.zip je ova nova ideja (u stvari slicna je kao stara, ali je izbaceno secenje)..
Analiza slozenosti:
algoritam 1: O(n^4)
algoritam 2: O(n^3) (Worst Case: O(n^4))

pojasnjenje algoritama (detaljno) saljem uskoro - ako je nekom potrebno.
Nisam bas stigao da testiram, javite ako vidite greske.
Kao sto sam rekao prosli put - ANSI C - kompajlirajte u cemu god hocete, a imate i exe ....

poz !
Prikačeni fajlovi
 
Odgovor na temu

dRock9
Kragujevac - Beograd

Član broj: 4217
Poruke: 54
*.ptt.yu



Profil

icon Re: pronalaženje podmatrice sa najvećom vrednošću zbira elemenata07.12.2002. u 19:23 - pre 259 meseci
1 fajl, 25 K, xmmm

evo i drugog
Prikačeni fajlovi
 
Odgovor na temu

dRock9
Kragujevac - Beograd

Član broj: 4217
Poruke: 54
*.ptt.yu



Profil

icon Re: pronalaženje podmatrice sa najvećom vrednošću zbira elemenata07.12.2002. u 23:04 - pre 259 meseci
Posto sam zakasnio na bus za Kragujevac, otkucao sam obecano pojasnjenje.

Da ne bih kopirao zakacicu TXT uz poruku...

Rapaic Rajko: Nisam siguran kako bi se moglo optimizovati racunanje matrice vise od ovog. Ako imas neku ideju reci, mada mora se proci n^2 puta da bi se sracunala cela matrica.... Da ne bude zabune ovaj odgovor se odnosi na post sa predlogom za optimizaciju.

oxo, vidim da je limit za attachment povecan na 45k - pohvalno...

Pozdrav
Prikačeni fajlovi
 
Odgovor na temu

[es] :: Art of Programming :: pronalaženje podmatrice sa najvećom vrednošću zbira elemenata

[ Pregleda: 4355 | Odgovora: 9 ] > FB > Twit

Postavi temu Odgovori

Srodne teme
11.12.2001. Paskal, nije mi jasno...
25.03.2002. Problem sa sumiranjem
29.03.2002. Brute force
20.11.2006. Help !!!
03.07.2003. Mendeljejev periodni sistem elemenata
12.09.2003. NIZ
19.02.2004. problem sa matricama
Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.