Kaj naj si zmislim za O(n^m)?

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?

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. :)

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

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