Forum » Programiranje » Kaj naj si zmislim za O(n^m)?
Kaj naj si zmislim za O(n^m)?
Arthur ::
alora, za seminarsko moram med drugim sprogramirat proceduro (iterativno in rekurzivno), ki ima časovno kompleksnost O(n^m), pa nimam pojma kaj bi si zmislil. omejitev je, da mora opravljat neko smiselno nalogo. bi lahko kdo kaj predlagal? ne preveč kompliciranega, ker nisem kak hud programer (smer Informatika pač 
). opis problema, psevdokoda, Java, kakorkoli...
tnx.
). opis problema, psevdokoda, Java, kakorkoli...tnx.
Sergio ::
Dzabe.
Mas drevo, ki ima n otrok ter m nadstropij. Skonstruirat drevo je O(n^m). Pa se rekurzija/iteracija ti ne bo povzrocala problemov.
Sej drevesa ste najbrz ze jemal?
Mas drevo, ki ima n otrok ter m nadstropij. Skonstruirat drevo je O(n^m). Pa se rekurzija/iteracija ti ne bo povzrocala problemov.
Sej drevesa ste najbrz ze jemal?
Tako grem jaz, tako gre vsak, kdor čuti cilj v daljavi:
če usoda ustavi mu korak,
on se ji zoperstavi.
če usoda ustavi mu korak,
on se ji zoperstavi.
Arthur ::
ufff, smo ja, pri Heapsortu recimo. vseeno mi ni čisto jasno, kako naj bi to zgledal. lahko daš par vrstic psevdokode, da vidim kako naj bi to šlo?
Sergio ::
ok ...
mas "vejico v drevesu", ki ji bomo rekli "node". Iz vsake vejice veje n novih vejic. Drevo ima m nadstropij.
Primer binarnega drevesa je, ce si lahko predstavljas, hisa iz kart.
Torej. Imas Node, ki ima kot enega od parametrov Node[], kjer so njegovi otroci.
Potem si mors se izmislit ustrezen problem, pa je. Eden od problemov bi lahko bil de facto konstruiranje drevesa.
Podas stevilo sinov in stevilo stopenj.
V rekurziji skonstruiras 7 sinov korenu, in potem rekurzivno vsakemu sinu reces 'span new prodigies', nekje pa hranis, koliko globoko si ze prisel.
V iterativni verziji enakega algoritma pa operiras z gnezdenimi for stavki. Lahko si pa car, pa naredis stack, in na stack pushnes vsakega od elementov, za katerega moras narest sinove, vse skupaj pa ovijes v while zanko...
Upam da sem ti kaj pomaga. Good luck. :)
mas "vejico v drevesu", ki ji bomo rekli "node". Iz vsake vejice veje n novih vejic. Drevo ima m nadstropij.
Primer binarnega drevesa je, ce si lahko predstavljas, hisa iz kart.
Torej. Imas Node, ki ima kot enega od parametrov Node[], kjer so njegovi otroci.
Potem si mors se izmislit ustrezen problem, pa je. Eden od problemov bi lahko bil de facto konstruiranje drevesa.
Podas stevilo sinov in stevilo stopenj.
V rekurziji skonstruiras 7 sinov korenu, in potem rekurzivno vsakemu sinu reces 'span new prodigies', nekje pa hranis, koliko globoko si ze prisel.
V iterativni verziji enakega algoritma pa operiras z gnezdenimi for stavki. Lahko si pa car, pa naredis stack, in na stack pushnes vsakega od elementov, za katerega moras narest sinove, vse skupaj pa ovijes v while zanko...
Upam da sem ti kaj pomaga. Good luck. :)
Tako grem jaz, tako gre vsak, kdor čuti cilj v daljavi:
če usoda ustavi mu korak,
on se ji zoperstavi.
če usoda ustavi mu korak,
on se ji zoperstavi.
Arthur ::
tnx, bom videl kaj bo ratalo. pol pa še main(), pa x drugih funkcij...
za par ur sem dober, hehe..
za par ur sem dober, hehe..
trs ::
Lahko napises program, ki najde kolko si je ena datoteka podobna z drugimi datotekami. Recimo da definiras da je block podatkov ki ga isces dolg najmanj 10 znakov ... lahko poskusas najt kje se X zaporednih znakov v nekem M bytov vhodnem fileu pojavlja v N drugih fileih. Primer:
Vhodna datoteka:
123
bla
helloworld
Datoteka 1:
if (a == fdlkfds) ... {
fksdjflsd
printf("helloworld\n")
dkslajdlasda
dsalklda
Datoteka 2:
blah blah ratatasalala
dasdashelloslsfksd
dsaldksa
Izhod bi lahko bil da se helloworld pojavi v Datoteki 1 na mestu tem in tem...
Sicer ne vem kako bi lahko naredil rekurzivno to stvar ;)
No, mogoce malo bolj zanimivo bi bilo iskat identicne kose slik(predpostavis da isces samo kvadratne dele slike) ... ali zvocnih datotek ...
lp,
trs
Vhodna datoteka:
123
bla
helloworld
Datoteka 1:
if (a == fdlkfds) ... {
fksdjflsd
printf("helloworld\n")
dkslajdlasda
dsalklda
Datoteka 2:
blah blah ratatasalala
dasdashelloslsfksd
dsaldksa
Izhod bi lahko bil da se helloworld pojavi v Datoteki 1 na mestu tem in tem...
Sicer ne vem kako bi lahko naredil rekurzivno to stvar ;)
No, mogoce malo bolj zanimivo bi bilo iskat identicne kose slik(predpostavis da isces samo kvadratne dele slike) ... ali zvocnih datotek ...
lp,
trs
Arthur ::
primerjanje datotek (slik, mp3-jev) bi bilo precej bolj uporabno, kot pa gradnja drevesa, ki ne počne ničesar drugega razen kurjenja procesorja in pomnilnika.
ampak sem imel že z drevesom take psihe, da se raje ne spuščam v kaj težjega
ampak sem imel že z drevesom take psihe, da se raje ne spuščam v kaj težjega
trs ::
Ja, mogoce ni niti toliko zakomplicirano kot se zdi. Da poenostavis problem lahko reces da isces samo fixne bloke. Potem lepo gres datoteko po datoteko primerjat z izvorno datoteko in je ;) Lahko celo naredis recimo, da ti v vseh slikah, ki imajo iste kose kot izvorna slike, pobarvas s kako barvo, tako da zgleda fancy ;)
lp,
trs
lp,
trs
Vredno ogleda ...
| Tema | Ogledi | Zadnje sporočilo | |
|---|---|---|---|
| Tema | Ogledi | Zadnje sporočilo | |
| » | Java metode;Oddelek: Programiranje | 4910 (4102) | ragezor |
| » | algoritm za pot med dvema točkamaOddelek: Programiranje | 1681 (1374) | detroit |
| » | Ne-rekurzivno iskanje po rekurzivni podatkovni strukturiOddelek: Programiranje | 1122 (968) | blaz_ |
| » | Za programerske teoretikeOddelek: Programiranje | 8782 (5584) | Jerry000 |
| » | Fibonacci in čas računanjaOddelek: Šola | 1401 (1185) | Pegaz |