DevProTalk

Forumi IT profesionalaca
web development, web design, e-business, SEO


Idite nazad   DevProTalk > Web development i web aplikacije > Programiranje
Želite da se reklamirate ekskluzivno na ovoj poziciji? Javite se

Programiranje Java, Perl, VB, ASP, .NET, C, C++, Pascal, Delphi Sponzor: VIP izazov 3

Odgovori
 
Alati teme Način prikaza
Staro 04. 08. 2007.   #1
dee
Domagoj Horvat
Expert
 
Avatar dee
 
Datum učlanjenja: 24.07.2006
Lokacija: Zagreb
Poruke: 502
Hvala: 22
10 "Hvala" u 8 poruka
dee is on a distinguished road
Pošaljite ICQ poruku za dee
Default Matematicki problem

imamo matricu MxN. popunjena je nulama, osim na proizvoljnim mjestima jedinicama. potrebno je pronaci najvecu matricu popunjenu samo jedinicama unutar velike.


dakle, nesto kao

0 0 1 1 0
0 1 1 1 0
0 0 1 1 1
1 1 1 1 1
0 0 0 0 0

ako je ovo pocetna matrica, algoritam bi trebao vratiti 3. i 4. stupac (bez zadnjeg reda)


ima li ko ideju kako uopce pristupit problemu?


bilo bi dosta jednostavnije da se trazi kvadratna, ali treba bas proizvoljan mxn

[Edit: dana matrica slucajno je kvadratna. opci slucaj je mxn osnovne matrice, takodjer]
__________________
postoje ludosti bez kojih je nemoguce ljudsko dostojanstvo

Poslednja izmena od dee : 04. 08. 2007. u 00:16.
dee je offline   Odgovorite uz citat
Staro 04. 08. 2007.   #2
filmil
хардвераш
Qualified
 
Datum učlanjenja: 04.01.2007
Lokacija: Маунтин Вју, САД
Poruke: 117
Hvala: 4
25 "Hvala" u 10 poruka
filmil is on a distinguished road
Default

Како дефинишеш највећу (под)матрицу?

ф
__________________
Рад је створио човека. Рад ће га и уништити.
filmil je offline   Odgovorite uz citat
Staro 04. 08. 2007.   #3
dee
Domagoj Horvat
Expert
 
Avatar dee
 
Datum učlanjenja: 24.07.2006
Lokacija: Zagreb
Poruke: 502
Hvala: 22
10 "Hvala" u 8 poruka
dee is on a distinguished road
Pošaljite ICQ poruku za dee
Default

Citat:
Originalno napisao filmil Pogledajte poruku
Како дефинишеш највећу (под)матрицу?

ф
kao najvecu sastavljenu od samih jedinica, bez ijedne nule.
__________________
postoje ludosti bez kojih je nemoguce ljudsko dostojanstvo
dee je offline   Odgovorite uz citat
Staro 04. 08. 2007.   #4
filmil
хардвераш
Qualified
 
Datum učlanjenja: 04.01.2007
Lokacija: Маунтин Вју, САД
Poruke: 117
Hvala: 4
25 "Hvala" u 10 poruka
filmil is on a distinguished road
Default

Разумео сам да је попуњена јединицама. Али шта значи „највећа“.

Да објасним: шта се дешава ако имаш две пуне подматрице 3x4? Која од те две подматрице је највећа?

Шта се дешава ако имаш пуну подматрицу 1x12 и 3x4? Која од те две подматрице је највећа?

Кад се каже „највећа“ онда се подразумева да може да постоји само једна. Кад се каже „максимална“, онда може да буде више максималних. Али прво мора да се установи мера по којој се матрице уређују. Кад сам питао, мислио сам на дефиницију мере.

ф
__________________
Рад је створио човека. Рад ће га и уништити.
filmil je offline   Odgovorite uz citat
Staro 04. 08. 2007.   #5
dee
Domagoj Horvat
Expert
 
Avatar dee
 
Datum učlanjenja: 24.07.2006
Lokacija: Zagreb
Poruke: 502
Hvala: 22
10 "Hvala" u 8 poruka
dee is on a distinguished road
Pošaljite ICQ poruku za dee
Default

Citat:
Originalno napisao filmil Pogledajte poruku
Разумео сам да је попуњена јединицама. Али шта значи „највећа“.

Да објасним: шта се дешава ако имаш две пуне подматрице 3x4? Која од те две подматрице је највећа?

Шта се дешава ако имаш пуну подматрицу 1x12 и 3x4? Која од те две подматрице је највећа?

Кад се каже „највећа“ онда се подразумева да може да постоји само једна. Кад се каже „максимална“, онда може да буде више максималних. Али прво мора да се установи мера по којој се матрице уређују. Кад сам питао, мислио сам на дефиницију мере.

ф
u pravu si, nisam do kraja precizan.

najveca je ona koja ima najvise jedinica i takva je uvijek samo jedna.
__________________
postoje ludosti bez kojih je nemoguce ljudsko dostojanstvo
dee je offline   Odgovorite uz citat
Staro 04. 08. 2007.   #6
filmil
хардвераш
Qualified
 
Datum učlanjenja: 04.01.2007
Lokacija: Маунтин Вју, САД
Poruke: 117
Hvala: 4
25 "Hvala" u 10 poruka
filmil is on a distinguished road
Default

Падају ми на памет два приступа. Један је грубом силом, а сложеност је O[max(m,n)^4].

Други треба да обори сложеност на нешто мање.

Први је лакши за објашњавање.

Прво нам треба предикат који за задате координате углова подматрице (нпр. горњи-леви и доњи-десни) одређује да ли је подматрица пуна. Подматрица је пуна ако у њој нема нула.

То се уради тако што се направи табела димензија m*n у којој, у ћелији (m,n) стоји збир свих поља почетне матрице, у подматрици [(0,0),(m,n)]. (тзв. дискретни интеграл) .

Ова табела се лако прави једним пролазом кроз изворну матрицу, тако што се почне од подматрице [(0,0),(0,0)], чији је дискретни интеграл просто вредност уписана у ћелију (0,0). Дискретни интеграл суседних матрица се добија на основу већ израчунатих вредности и нове ћелије.

Када се има ова табела, лако је да се одреди дискретни интеграл било које подматрице [(p,q),(r,s)] као:

DI[(p,q),(r,s)] = DI[(0,0),(r,s)]*[r>0,s>0] - DI[(0,0),(p-1,r)]*[p>1,r>0] - DI[(0,0),(s,q-1)]*[s>0,q>1] + DI[(0,0),(p-1,q-1)]*[p>1,q>1]

овде је DI(x) дискретни интеграл подматрице, а x = [(x,y),(z,т)], тј. пар тачака које редом одређују горњи-леви и доњи десни угао. (ћелија 0,0 је горе-лево а координате расту надесно, одн. надоле); [.] је индикатор функција (тзв. Ајверсонов [Iverson] индикатор), који има вредност 1 када је услов наведен унутар индикатора тачан, одн. 0 ако је услов наведен у индикатору нетачан.

(НБ: [t>=0] је Хевисајдова функција, позната свима који су се бавили рецимо обрадом сигнала)

Ако је дискретни интеграл неке подматрице једнак њеној површини, онда је матрица пуна. Ова провера може да се одради у константном времену, кад смо једном срачунали DI.

Онда направимо два итератора по елементима матрице и пробамо све могуће комбинације горњих левих и доњих десних ћошкова подматрице. То су укупно 4 обгрљене петље.

Проверимо DI да откријемо да ли је посматрана подматрица пуна. Ако јесте, сачувамо је као највећу, под условом да је већа од највеће дотад пронађене.

Када се петље заврше, највећа пуна подматрица је сачувана.

ф
__________________
Рад је створио човека. Рад ће га и уништити.
filmil je offline   Odgovorite uz citat
Staro 04. 08. 2007.   #7
filmil
хардвераш
Qualified
 
Datum učlanjenja: 04.01.2007
Lokacija: Маунтин Вју, САД
Poruke: 117
Hvala: 4
25 "Hvala" u 10 poruka
filmil is on a distinguished road
Default

Други метод је мало сложенији. Заснива се на парцијалном решавању.

Да би решио проблем за матрицу [(0,0),(m,n)] треба прво да га решиш за матрице: [(0,0),(m,n)], [(0,0),(m-1,n)], [(0,0),(m,n-1)] и [(0,0),(m-1,n-1)].

То значи да треба да кренемо са решавањем од [(0,0),(1,1)] и да радимо ка већим матрицама.

За сваку матрицу коју испиташ, памтиш следеће: листу максималних пуних матрица дотад откривених; листу максималних пуних матрица дотад откривених, које се наслањају на доњу ивицу подматрице; и листу максималних пуних матрица које се наслањају на десну ивицу подматрице.

Ове листе могу инкрементално да се праве на основу претходно израчунатих матрица. На пример, на основу срачунатих листа за [(0,0),(p,q)], можеш да срачунаш листе за [(0,0),(p+1,q)] и [(0,0),(p,q+1)]. Листе са „ослоњеним“ подматрицама требају ти, јер то су једине које могу да „порасту“ додавањем једног додатног реда или колоне на постојећу подматрицу.

Оне могу да „порасту“ додавањем пуне подматрице-колоне или подматрице-реда, које имају одговарајуће димензије. За проверу да ли су подматрица-колона одн. подматрица ред пуни, можеш да користиш предикат из претходне поруке.

Када цео рачун одвртиш до [(0,0),(m,n)], листа максималних матрица имаће само један елемент (по услову ког си навео) и тај елемент је решење.

ф
__________________
Рад је створио човека. Рад ће га и уништити.
filmil je offline   Odgovorite uz citat
Staro 06. 08. 2007.   #8
dee
Domagoj Horvat
Expert
 
Avatar dee
 
Datum učlanjenja: 24.07.2006
Lokacija: Zagreb
Poruke: 502
Hvala: 22
10 "Hvala" u 8 poruka
dee is on a distinguished road
Pošaljite ICQ poruku za dee
Default

drugi nisam bas razumio, ali prvi mi je vise manje jasan i cini mi se sasvim dovoljan.


puno ti hvala!
__________________
postoje ludosti bez kojih je nemoguce ljudsko dostojanstvo
dee je offline   Odgovorite uz citat
Odgovori


Alati teme
Način prikaza

Pravila pisanja
Možete ne započinjati nove teme
Možete ne slati odgovore
Možete ne slati priloge
Možete ne izmeniti svoje poruke
vB kôd je Uključen
Smajliji su Uključen
[IMG] kod je Uključen
HTML kôd je Isključen
Pogledajte forum

Slične teme
Tema Početna poruka teme Forum Odgovori Poslednja poruka
Double float problem - resen, ali ima dodatni problem :0 ljtruba (X)HTML, JavaScript, DHTML, XML, CSS 34 23. 08. 2008. 03:28


Vreme je GMT +2. Trenutno vreme je 23:53.


Powered by vBulletin® Verzija 3.6.8
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Copyright © DevProTalk. All Rights Reserved.
Mišljenja, saveti, izjave, ponude ili druge informacije ili sadržaji nastali na Sajtu su vlasništvo onoga ko ih je kreirao, a ne DevProTalk.com, tako da ne morate da se oslanjate na njih.
Autori poruka su jedini odgovorni za ovakve sadržaje. DevProTalk.com ne garantuje tačnost, kompletnost ili upotrebnu vrednost informacija, stavova, saveta ili datih izjava. Ne postoje uslovi pod kojima bi mi bili odgovorni za štetu ili gubitak koji je posledica bilo čijeg oslanjanja na nepouzdane informacije, ili bilo kakve informacije nastale kroz komunikaciju između registrovanih članova.
Web sajt može sadržavati linkove na druge web sajtove na Internetu ili neke druge sadržaje. Ne kontrolišemo niti podržavamo te druge web sajtove, niti smo pregledali bilo kakve sadržaje na takvim sajtovima. Mi nećemo biti odgovorni za legalnost, tačnost ili prikladnost bilo kog sadržaja, oglasa, proizvoda, usluga ili informacije lociranim na ili distribuiranih kroz druge web sajtove, niti za bilo kakvu štetu nastalu kao posledica takvih informacija. DevProTalk.com drži i čuva druga prava vlasništva na web sajtu. Web sajt sadrže materijale zaštićene copyright-om, zaštitne znakove i druge informacije o pravu vlasništva ili softver. Članovi mogu poslatu informacije zaštićene pravima vlasništva njihovih nosilaca i ona ostaju zaštićena bez obzira da li su oni koji prenose te informacije to naveli ili ne. Osim informacija koje su u javnom vlasništvu ili za koje dobijete dozvolu, nemate pravo da kopirate, modifikujete ili na bilo koji način menjate, objavljujete, prenosite, distribuirate, izvršavate, prikazujete ili prodajte bilo koju informaciju zaštićenu pravima vlasništva. Slanjem informacija ili sadržaja na bilo koji deo DevProTalk.com, Vi automatski dozvoljavate i predstavljate garanciju da imate pravo da dozvolite DevProTalk.com ili članovima DevProTalk.com bespovratnu, kontinualnu, neograničenu, globalnu dozvolu da koriste, kopiraju, izvršavaju, prikazuju i distribuiraju takve informacije i sadržaje i da iz takvih sadžaja koriste bilo koji deo u bilo koje svrhe, kao i pravo i dozvolu da koriste gore navedene sadržaje. Svi zaštitni znakovi (trademarks), logotipi, oznake usluga, firme ili imena proizvoda koji se pominju na ovom web sajtu su vlasništvo kojim raspolažu njihovi vlasnici.