Zato sam ja oduvek mrzio takmicenja iz informatike.
Sve sami matematicari, koji u zivotu nisu videli kompajler...

Ovo je najobicnija ABCD kombinatorika...

Samo stavis for petlju u loop until N, i resio si ceo problem...

Hm, koja je prakticna primena ovog "hard-core" kombinovanja zagrada ?
Osim, eventualno, u nekom parseru (i to eventualno), koja je vrednost ovako necega, sem za domaci iz principa programiranja ?

Pa prednost je recimo u tome sto resavajuci ovakve probleme stices vestinu resavanja komplikovanijih problema koji ce ti sutra zatrebati... nije sve u pisanju lepog i sarenog guia i koriscenju tudjeg sourcea, mada nije sve ni u ovome ;)))))

Hmm... To je donekle tacno... Ali da bi resavao vecinu ovakvih problema treba da si dobro potkovan matematikom... A i oni sami nemaju neku veliku primenu, jer uglavnom ljudi koji uce da resavaju take zadatke, uce ih mehanicki, tako da to sve gubi neku svrhu...


Po meni je umece napisati dobar 3D engine, neki sistemski program, 4k intro... I sl...

Za neke osnove 3D programiranja ti ne treba puno matematike, ja sam recimo svoj prvi engine napisao uz pomoc +-*/ i sin/cos funkcija... Nikakva komplikovana matematika...

Mozete recimo da napravite takmicenje ko ce da napravi OPTIMIZOVANIJ 3D engine, u recimo 64K prostora (mada je i to previse, al ajde za pocetak).

Pri takvoj vrsti programiranja mora da se poznaje odlicno samo programiranje, teorija, hardver, kao i same finese i osobitosti prog jezika...

Jeste danko umece je, to i ja pricam ali avakvi problemi su bas zato da bi ljudi stekli feeling da programiraju korektno, jer na zalost danas su racunari previse brzi pa ljudi koji pocinju sa programiranjem ne shvataju problem optimizacije i koliko to znaci, recimo samo crtanje linije od tacke (x0,y0) do tacke (x1,y1) moze da bude nauka za sebe. kada se uzme u obzir svo racunje da se bi se dobio maksimalan rezultat. Opet za 3d grafiku bash mislim da ti treba dobro poznavanje analiticke geometrije ukoliko zelis da to sto pises stvarno bude optimizovano.

Opet ako vidis resenje kombinatorikom :)))) super :)) napisi ga pa da vidimo koliko je brzo resenje.

Opet kazem ovde je cilj brzina izracunavanja. Tako reci znamo svi da napisemo da to proradi ali cilj je da to sto brze proradi. Mozda prvi primer koji sam dao je pre tezak za pocetak, ali pokusacu sa jednim jednostavnijiom problemom da samo ukazem na neke od trikova.

Recimo ako treba da podelim neki niz brojeva sa nekom konstantom npr

Deljenje je jako skupa operacija a mnozenje jeftinija pa je ovo znatno brze, opet mnozenje je dosta skuplje od sabiranja i oduzimanja, dok su bitske operacije najbrze.



e sada ako uzmemo primer da moramo da izracunamo kvadrate svih brojeva od 1 do N klasicno racunjae u for petlji je opet skupo sa aspekta trosenja procesorskog vremena.

Pa onda valja iskoristiti kvadrat binoma za (n+1)^2 = n^2 +2*n+1, gde n^2 vec imam izracunato od ranije a ono 2*n mogu da razlozim na n+n ili jos bolje na n<<1 i na kraju onaj + 1 moze da se sa bitskim ili sabere sa shiftovanim n umesto klasicnog sabiranja. sve te male sitne stvari doprinose brzem racunaju. Mozda sve ovo vama deluje jako smesno ali kada budete bili prinudjeni da pisete prave realtime aplikacije, gde se procesorsko vreme placa zlatom onda cete mozda i razumeti. Vrednost i sustinu ovakvih zadataka.

Opet jos jednom pozivam sve vas da probate da napisete program za gore pomenuti problem pa da vidimo ko je bio najbolji :)

A jel mora da se radi u C/C++ ili može i neki drugi programski jezik? Mislim je ovo trebalo da se smesti u Art of Programming ...

tako ja odem na republicko iz informatike i tamo mi ne radi ni jedan primer ispod 3s, a na regionalnom su pustali da se vrti i po 30sec... ;)

Gde ti vidis ovde matematiku?

Ovde je nema, ovde je samo logika u pitanju.
OK, priznajem gresku :)

Na prvi pogled mi se ucinilo kao zadatak sa takmicenja iz matematike :)

Dejane, je l' znas da li postoji neka formula za izracunavanje ili mora preko racunara?

Inace problem moze da se svede na sledeci problem. Imamo hiljadu jedinica:
1 1 1 1 1.......
i izmedju tih jedinica treba staviti + ili minus tako da na kraju zbir bude nula a da medjuzbir ubek bude veci ili jednak nuli. Medjuzbir nam je broj koji se dobija kada se redom racuna od pocetka pa do neke proizvoljne jedinice.

Sve ovo jeste tacno, ali je uglavnom vise nebitno. MSVC automatski generise upravo ovakav kod kada se ukljuce optimizacije. Znaci delenje u petlji biva zamenjeno mnozenje sa reciprocnim brojem, 2*n biva zamenjeno sa n<<1, itd. Pogledajte disassembly neke matematicke operacije kada se program iskompajlira sa optimizacijama (obicno release profile), i iznenadicete se sta sve MSVC kompajler radi. Zakljucak: lepo je znati te stvari, ali gledajte da ih ne primenjujete u kodu jer cete uglavnom da pokvarite citljivost koda zarad necega sto bi kompajler ionako sam uradio.

Reljam je potpuno u pravu. Kod rada sa današnjim modernim kompajlerima je pravi zločin pisati ta šiftovanja ulevo i udesno umesto množenja i deljenja. Jednostavno, kompajler u oba slučaja generiše potpuno isti kod.

I uopšte, optimizacija na nivou koda je najčešće potpuno nepotrebna i neisplativa stvar. Ljudi potroše nedelje i nedelje da bi napisali efikasniji algoritam i onda se ispostavi da je "usko grlo" negde sasvim drugde i da je dobitak 0.001%. Jedini ispravan pristup kod razvoja koda je sledeći:

1. Napravi ga da radi i da bude što jednostavniji i čitljiviji.
2. Izmeri performanse.
3. Ako zadovoljava - kraj priče.
4. Ako ne zadovoljava, izvrši profilisanje koda da bi našao delove koji usporavaju aplikaciju. Nikada nemoj da "mozganjem" dođeš do zaključka koji su to delovi koda, nego isključivo merenjem.
5. Unapredi performanse tih kritičnih delova koda.
6. Idi na tačku 2.

U 99% slučajeva je čitljivost koda i jednostavnost implementacije važnija od performansi.

da to bi bilo super organizovati takvu vrstu takmicenja, a pogotovo ako ce biti nesto nalik onoj na www.kuro5hin.org (neki mozda i znaju na sta mislim). odrediti pravila:
.efikasnost (1-5)
.algoritam (1-5)
.jednostavnost koda (1-5)

nemam sada vremena da se raspisem, ali sutra cim se vratim iz skole nastavicu majke mi :)

Hm, slazem se sa Tatkom :D Pokusavanje ovakvog optimizovanje ne moze da se generalizuje na sve profile programera (i samim time, velicati ga kao "jedini, pravi, istinski, hard-core, itd" programming). Mozda je vazno nekome ko radi na kompajleru, low-level biblioteci i slicno, ali ne i ostalima. Kada i hocu da nacrtam nesto, uzecu i koristiti taj moveTo i lineTo sasvim spokojno, jer je armija programera vec pretresla podlogu i njihovu optimizaciju kroz niz godina i ne pada mi na pamet da smisljam rupu na saksiji. Uostalom, zato od pocetka i postoji koncept biblioteka - ko ce sve da pise od pocetka ? Slazem se posebno i sa delom oko citljivosti koda - kada se radi u timu (uz podrazumevanu fluktuaciju programera), to moze biti zlata vredno.

Napomena: poruka je malo poduža, a vi izaberite ,,masno'' naslovljen deo koji vas zanima

Na poslednju poruku...


Ne mogu da se složim; razlozi dati niže.



Prvo, to ,,slično'' uključuje i one koji rade sa grafikom, zvukom, videom, (de)kompresijom, mrežama (grafovi i načini pravljenja softvera za rutere), i ko zna šta sve ne (upis fajlova na disk (fajlsistemi), traženje najmanjih razlika među fajlovima (diff), zadovoljavanje međuzavisnosti (make)...)

Zapravo, to je ono što zovemo programiranje.



Naravno, ali nemoj se zavaravati da si ti programer. Jednostavno ,,skript'' programiranje je sastavni deo upotrebe računara, i to je ono što svaki korisnik treba da radi: ne može niko predvideti sve operacije koje nekome mogu zatrebati, i zato postoje skript jezici. Izrada VBA koda ili PHP web stranica je ograničenog delokruga, i u tim poljima postoje druga, značajnija ograničenja (protok mreže, pristup podacima sa diska,...), pa je optimizacija nepotrebna.

Slično je i sa upotrebom gotovih biblioteka: ti si korisnik programa, bez obzira na to što i ti napišeš malo koda, ali to nije ovde pomenuto pravo programiranje, već najobičnije, i neophodno ,,skript'' programiranje. Neki shell korisnici ukucavaju i složenije programske linije pomoću gotovih ,,biblioteka'' (programa preko pipes) nego što to rade mnogi u C++-u ili nečemu drugom. Međutim, za takvu upotrebu je upravo i nastao izraz "skript", a ne "program" (nadam se da je jasna razlika koju hoću da istaknem, i pored nezgode da je i svaki "skript" istovremeno i program).





Vrednost biblioteka je poznata, i to ne sporim. Prosto umeće upotrebe istih ne čini bilo koga programerom.

Što se tiče čitljivosti koda, primećujem izvesne nedoslednosti. Tvrdiš kako postoje biblioteke koje su ljudi optimizovali što je bolje moguće, i koristiš samo njihov interfejs (znači uopšte ne čitaš kod), a odjednom ti je stalo da kod bude čitljiv.

Baš kada se radi u timu, tada je najmanje važno da kod bude čitljiv, već da interfejs bude dobar i upotrebljiv. Čitljivost je bitna samo za onoga koji održava, i koji će u budućnosti održavati dotični kod.

Pored svega ovoga, pretpostavljam da si ti preskočio osnovnu školu (nećeš valjda da ,,smišljaš rupu na saksiji''; pa ljudi su naučili da pišu i broje još pre više vekova). Ukoliko je tako, slažem se da treba da preskočiš i osnovno programersko obrazovanje.


A na temu optimizacija...
Što se tiče optimizacija, Dejan Lozanović je naveo neke konstantne (kao što su šiftovanje umesto množenja sa 2^n, množenje umesto deljenja), i tu su vaše primedbe na mestu: dvostruko (ili možda 1,03-struko) ubrzanje nisu vredni gubljenja čitljivosti koda (za to se uzme dva puta brži procesor, i eto rešenja).

Međutim, on je izdvojio i jednu optimizaciju koja ipak nije konstantna, već se radi o prelazu sa kvadratne na linearnu složenost (ako množenje računamo kao linearno slaganje sabiranja, mada se uglavnom implementira kao logaritamsko). Složićete se da je mnogo bolje kada se rezulatat dobije u N=1000 koraka nego u N^2=1000000 koraka. A tek kada se radi o prelazu sa eksponencijalne na polinomijalnu složenost (ili logaritamsku), dobici su mnogo veći.

Naravno, sve vaše tvrdnje su tačne u ograničenom polju delovanja: jednostavnije poslovne aplikacije sa manjom količinom podataka. Međutim, kada treba da pristupite većoj količini podataka (npr. primljeni podaci u Aresibu), i istu da obradite, najvažnije optimizacije će doći do izražaja: izbor boljeg algoritma.

I konačno o samom zadatku...
Prema tome, za dati problem sa zagradama (ili prema srkijevoj reformulaciji), treba naći bolji algoritam, a ne brinuti se oko brzine množenja i deljenja, sabiranja i oduzimanja. Mada može dosta doprineti, to se može izvesti i mehanički (kompajleri), a i najbolje je to raditi tek za najbolji poznat algoritam.

A o praktičnosti ovog problema, evo vam primera.

Imate Tag pri obradi XML dokumenta, koja naravno može sadržati nijedan, jedan ili više drugih Tag-ova, prema određenoj DTD. Provera validnosti nekog XML dokumenta je nešto složenija od datog problema zbog složenije prirode pravila XML-a, ali i nešto jednostavnija pošto se radi o proveri pripadnosti konkretne vrednosti (instance) skupu svih vrednosti, a ovde se traži kardinalnost tog skupa vrednosti.

Primer koji se sam po sebi nameće je, naravno, obrada LISP koda, ili bilo kakvog drugog koda koji ima slično definisana pravila ugnježdavanja (da li su zagrade ili nešto drugo nije toliko bitno).

I malo brbljanja
Ko i dalje ne veruje u prednosti optimizacije, neka proba da aktivno radi na Word dokumentu od 2000 strana (znači ne da dodaje tekst na kraj, nego da menja i dodaje sadržaj u sredinu, i sve ostale gluposti). Moja iskustva su zasnovana na starijim Word izdanjima -- 1995/97 -- pa situacija može biti sada mnogo bolja.



Kod sledećeg javljanja na ovu temu se nadam da ću dodati i moju verziju koda za postavljeni problem.

Pozdrav


PS. Biblioteke služe da se uštedi vreme, a ne pamet.

Danilo,

Ne mogu da polemišem sa tobom iz prostog razloga što je za tebe programiranje izgleda više umetnost. Ja sam inženjer i moj pristup je da program napravim tako da mušterija (ili šef, sasvim svejedno) bude zadovoljan, a to u praksi znači držati se onog algoritma gore koji sam naveo. Kada se rade "real-life" projekti, gde je to potrebno postave se tzv specifikacije performansi, npr: "ta i ta komponenta treba da obradi toliko i toliko zahteva u minuti na takvom i takvom hardveru" i kada jednom pređeš tu donju crtu, dalje nema optimizacije. Zabranjeno je - vreme software inženjera je previše skupo da bi se trošilo na takve zezancije.

Drugo, možeš ti slobodno da gledaš sa visine ljude koji koriste gotove biblioteke umesto da sve pišu iz početka - umetnicima je sve dozvoljeno. Međutim, uveravam te da u stvarnom svetu takav pristup vodi u kašnjenje, pa u probijanje budžeta, pa u bankrotstvo. Nove biblioteke se pišu u dva slučaja: 1) Na tržištu ne postoji ništa slično ili ako postoji nije dovoljno kvalitetno za naše zahteve 2) Šefovi su izračunali da je jeftinije da mi to sami razvijemo nego da kupimo od nekog drugog.

I najzad nešto što je i meni samom bilo potrebno dugo da ukapiram i zbog čega nisam ni malo srećan: Kvalitet proizvoda (pa i softvera) je samo jedan od sporednih činilaca koji određuju njegov uspeh ili neuspeh na tržištu. Marketing je mnogo važniji. Tužno, ali istinito.

Hm, izgleda da ce ova tema da odvede na sasvim drugu stranu, ali hajde da se ipak malo razjasnimo. Trudicu se da ne budem toliko sarkastican kao ti, Danilo - ako mi malo sklizne tastatura, svima se izvinjavam.

Kratak uvod - ne razumem zasto ljudi tako "nadmocno" reaguju, pokazujuci da su oni jedini i istinski nosioci znanja - ubismo se od silne armije profi programera, koji listom dele ostale na "prave programere" i "kvazi programere" (uglavnom se time najvise i bave uz ono "mala moja neiskusna deco"), zato sto je neko, Boze moj, upotrebio API funkciju (zamisli) umesto da je to lepo sam 'hardkodovao'.
Ako je potrebno radi onog "VBA i PHP skripting" - ne, ne radim u tome. C/C++ i Delphi/Kylix za windows i linux. Radim napolju kao programer godinama i verovatno mi je takav posao bio ponudjen zato sto umem da zavrsim posao kako treba. Izmedju ostalog, radio sam i na nekim drajverima za linux, kao i na sw-u za RTlinux i dobro znam sta je optimizacija i gde je treba staviti, a za sta se *nema vremena*.

Sad kad si me lepo raspodelio "tamo gde spadam", hajde da procitamo zajedno citat na koji si tako posprdno odgovorio - mozda nadjemo jos neku rupu na saksiji. Daklem, na "Kada i hocu da nacrtam nesto, uzecu i koristiti taj moveTo i lineTo sasvim spokojno, jer je armija programera vec pretresla podlogu i njihovu optimizaciju kroz niz godina i ne pada mi na pamet da smisljam rupu na saksiji." si ustvrdio da, naravno, nisam uopste programer. Mozda ne bi bilo lose da mi otvoris oci kako to da optimizujem moveTo i lineTo i ima li to nekog smisla uopste. Nisam pricao uopste o nacinu na koji JA koristim te funkcije - napisao sam sasvim jasno da cu spokojno da ih koristim, ne razmisljajuci o tome kako je MS ili Borland optimizovao moveTo -> ja licno nemam vremena da je pisem od nule, izvini. U tome i jeste bila poenta kod 'nedoslednosti' - uopste me ne interesuje da li je i kako optimizovan printer manager, openfile dijalog, itd ako radi svoj posao. Da, tu cu biti korisnik biblioteke - ne verujem da si ni ti napisao ovo sve svoje, da vrsis operacije nad registrijem kao binarnim fajlom, i slicne stvari - korisnik NEKIH biblioteka moras da budes. Na njih sam se odnosio kada sam pominjao armiju programera i rupu na saksiji. Naravno da kada pisem svoje komponente ili rutine vodim racuna o algoritmu i optimizaciji (tamo gde mora, a tamo gde moze jedino ako ima vremena). Tu je vazna ta citljivost. Jeste, ona je bitna timu koji odrzava tu biblioteku, ali to smo upravo mi koji smo je pisali. Najcesce je mi i koristimo u izradi finalnog proizvoda. Sutra ti ode programer koji je bio zaduzen za nesto i dodje drugi, pa krene da se krsti na zadatak nekih izmena. Resio bi on to sigurno, ali nema se vremena za lagano analiziranje. Dobijes mesec dana za napravis update ili plugin ili ko zna sta i niko te ne pita kako bi ti to voleo da uradis, niko ne obraca paznju na to sto kukas da za tako nesto treba bar dva meseca - to se zove trzisna trka i to nisam smislio ja, vec neko drugi. Postaces "korisnik biblioteke" hteo ti to ili ne (ili ces promeniti firmu, naravno) i to nije uopste razlog za ovako lepa cascavanja i vredjanja.

Elem, da se vratim problemu; nisam zeleo da nipodastavam trud coveka koji je postavio thread, daleko od toga (ako je stekao takav utisak, ja se njemu ovde izvinjavam). Moje pocetno osvrtanje se odnosilo na naslov "hard-core programming" na zadatak koji je (ponavljam, bez uvrede) u prvi mah licio na domaci iz informatike.

Izvinjavam se što sam bilo koga uvredio (ako jesam), ali me niste razumeli.

Kratko (koliko je to moguće):
1. Biblioteke su korisna stvar, i koriste se iz već navedenih razloga (koje vi ističete)

2. Pogrešno ste razumeli moje reči kada sam rekao da upotreba biblioteka ne čini bilo koga programerom. Obratite pažnju na to da nisam rekao ,,Neko je programer ako i samo ako ne koristi biblioteke'' (znači ne radi se o ekvivalenciji). Sigurno je da programeri koriste biblioteke. Prema tome, nisam rekao da silverglider, ili neko drugi ovde, nije programer. Već da je tu nešto drugo što tebe čini programerom, a ne upotreba biblioteka (a upotreba biblioteka u C/C++-u je gotovo isto kao i PHP ili VBA skripting).

3. Hteo sam da istaknem potrebu razumevanja rada istih: čak sam i dodao da je u pitanju vreme: vi i navodite da štedite vreme koristeći postojeće biblioteke, a ne zato što ne umete da ih napišete. O tome se i radi.

4. Nemanja, to što ti spominješ nazivamo kompromisima, i to je obavljanje posla (ne znam zašto stičete utisak da ja mislim da je to loše). Za mene programiranje nije baš umetnost, već više nauka. Dalje, ne posmatram ikoga sa visine, i verujem da ste vi trenutno veći programeri od mene, a lako je moguće da će tako i ostati u daljoj budućnosti.

Međutim, u nekim poslovnim aplikacijama kakve će ti naručiti recimo NASA ili ESA, teško ćeš naći postojeće biblioteke, a veoma je važno da se rezultat dobije što brže (tj. algoritam da bude što bolji).

Dobar primer vam je i ovaj zadatak koji zaista i jeste tipski (tj. kao domaći), a moje jednostavno rešenje pogledajte niže.

Još jednom, javno izvinjenje svima koji su se našli uvređeni: za to zaista nije bilo razloga, a nadam se da sam sada pojasnio moje reči.

Dodatak: I kako je ova tema sada na forumu ,,Art of Programming'' (ili veština programiranja, prema čuvenim knjigama TAOCP), rasprave o poslovnim primenama treba prebaciti negde drugde (isto kako je i ova tema prebačena ovde). Prema tome, ovde se radi jedino i samo o načinu implementacije složenijih algoritama, a ne o smanjenju cene proizvodnje programa.

[Ovu poruku je menjao tOwk dana 04.11.2002. u 19:16 GMT]

Evo mene, kako sam i obećao, sa rešenjem.
U istom kodu je običan primer koji radi, ali veoma sporo, i jednostavna optimizacija koja se pokazala kao vrlo uspešna za dati problem: samo se pamte vrednosti F(i) u nizu, i ukoliko su već izračunate, ne računaju se ponovo. Zbog osobina izabranog algoritma, broj poziva F(i) je eksponencijalan (čini mi se 3^n), ali na ovaj način se smanjuje na polinomijalan broj.

Program je sledeći (zagrade.c):


Varijanta Zagrade.c je


Razlika u brzini se jasno vidi:




E, problem je što broj mogućnosti prevazilazi opseg int64-a već na 36, a ,,brzi'' program kvadratno usporava, i tada i dalje ima neprimetno vreme izvršavanja. Nadam se da se slažete da je O(n^2) prilično dobar rezultat za ovakav program (nisam dokazao, ali rast utrošenog CPU vremena mi ukazuje na to, a ne rešavaju mi se rekurentne jednačine :).

I primetite da ovaj program vraća pogrešnu vrednost za nula zagrada, ali to se lako proveri posebno (vraća 1, umesto 0). Razlog za to provalite sami :)

Nadam se da će neko uraditi bolje! (npr. bez upotrebe O(n) memorije, a ista složenost; ili manja složenost).

Toliko


PS. Nadam se da je program ispravan :)

Pa ukoliko gledas da pises program nezavisno od kompajlera pitanje sta svaki kompajler radi na polju optimizacija, ne kazem da ta oblast nije napredovala, ali neke stvari kompajleri josh uvek ne mogu da "vide" ovo sa racunanjima kvadrata je bilo dato samo kao primer pitanje je da li takve neke konstrukcije kompajler zna da izvuce, ali recimo ne mora se ici do optimizacija na krajnjem nivou da se pise siftovanje, ali opet ljudi za sta postoje komentari, po meni dobar kod je onaj koji na svake dve tri linije bude lepo iskomentarisan da se zna sta program gde radi. Evo vam primer pogledajte an sta mislim pod time komentari kako i koliko
http://www.matf.bg.ac.yu/r3nm/vjezbe/libnumerics.tar.gz

Tada i sve moguce vratolomije koje pisem mogu lepo u svakoj liniji da iskomentarisem, mozda ce neko reci da pisem komentare izmedju koda. Ali rezultat je kod dobro optimizovan i olaksan kompajleru, a sa druge strane razaumljiv.

Da ako planiras da budes programer gotovan i planiras da koristis samo gotove stvari tako reci slazes kockice od drugih programera to je ok onda ,ali ako budes nekada razvijao nove tehnologije i biblioteke koje ce koristiti drugi progrtameri onda se zna sta je prioritet.

Ako sa 4 para zagrada postoji 14 kombinacija koje su to jos 3 kombinacije od ovih:

1. () () () ()
2. ( () ) () ()
3. ( () () ) ()
4. ( () () () )
5. () ( () () )
6. () () ( () )
7. ( ( ( () ) ) )
8. ( ( () ) ) ()
9. () ( ( () ) )
10. ( () ) ( () )
11. () ( () ) ()

osim ako se ne ukjlucuju i
))))((((
i njegove varijacije gde one ne zatvaraju zagrade, ali mislim da to nije u opisu zadatka?

Mislim da je to maksimum sa programerske strane, koji moze da se dobije, primenom grube sile, peca je dobro osetio jadac ;)), pravo resenje dolazi uz matematiku naime radi se o Katalanovim brojevima

E sada moze mala optimizacija tog izraza da se uradi u samom programu, ali nadam se da ce ljudi shvatiti i videti razliku u brzini oba izracunavanja, narocito kada trebaju da se racunaju vrednosti preko 20 :))), ali opet mi je drago sto je barem neko pokusao :)))


Ventura je ipak izvalio da jeste neka kombinatorika u pitanju ;))




[Ovu poruku je menjao Dejan Lozanovic dana 05.11.2002. u 15:12 GMT]

Dejane, hvala na komplimentu. Mislio sam da smo se malcice bili razumeli nakon prvog 'nesporazuma', ali ocigledno da nismo. Dacu kratak primer radi ilustracije; recimo da pises neki program za komunikaciju (ovo je proizvoljan primer). Potrudicu se da dobro razradim protokol, enkripciju, portovanje medju OSovima, solidan GUI i slicne stvari. Medjutim, uz sam taj 'core', program treba da ima niz 'dodataka' - recimo da imam neki addressbook u tom programu i da mi treba format za export/import tako necega; odlucim se da bude XML baziran, recimo. Situacija je sledeca: rok je bio relativno kratak - deadline ti dise za vratom, placaju se fini penali za kasnjenje - da li ces za tako nesto **sta nije kljucno** uzeti gotovu, proverenu XML komponentu za $50 i utrositi dobijeno vreme na testiranje i sredjivanje paketa, ili ces se kockati sa vremenom i odvojiti jednog programera da pise XML komponentu, s tim da njegov radni sat kosta $25 (verujem da ne moze da napise jednu ili vise komponenti tog tipa za dva sata, zajedno sa testiranjem i debuggingom) ?? Ja to ne shvatam kao 'gotovanstvo', a ni mnogo vece firme od moje, koliko mogu da vidim. Nadam se da je primer dobro ilustrovao ono na sta sam mislio celo vreme. Ako nije, onda j....

I tu je, sto se mene tice, kraj ovoj polemici - vratite se temi koju je covek postavio.


P.S.
Towk, stvar u redu, covek.

Zanimljivo. Retko kad naiđem na probleme ovog tipa (domaći, takmičenja) koji zaista mogu da se lepo izračunaju, pa i ne pomišljam da to pokušam.



Pa nisi potpuno u pravu. Ono vreme dato za moj primer za 20 je ,,user'' vreme: 0.000s, tj. manje od milisekunde. Zbog toga bi osetnije razlike mogle da se primete tek za možda vrednosti od nekoliko stotina na modernijim procesorima (naravno, na 286 bi to bilo mnogo pre; moj procesor PIII Celeron 700MHz je sada u nekoj srednjoj kategoriji, ako ne već i slabijoj).


Ni moj program nije baš toliko loš. Naime, kvadratna složenost u odnosu na linearnu i nije toliko loša za manje vrednosti. Pored toga, imam osećaj i da bi se program mogao srediti da radi u linearnoj složenosti ako bi se eliminisao ,,call overhead'', i koristile zapamćene vrednosti bez poziva funkcije (zato što se svaka nova vrednost dobija od prethodnih, a ta ubrzo biva zapamćena, i ne treba je ponovo tražiti). Uostalom, proveriću, pa ću i javiti.

Na primer, kod mene vreme od 1 sekunde dozvoljava rad sa približno vrednostima do 4000 (ali je tada problem što moj primer vraća , umesto , ali to je do izbora unutrašnjeg zapisa brojeva, i isti problem bi postojao i sa računanjem faktorijela na jednostavan način --- prosto, rezultat za n veće od 35 ne staje u opseg od 64 bita.


Toliko

(prvo da se ogradim da nisam gledao primer, ali komentarisem ono sto si ti opisao)

ma daj. pa ne treba ja da objasnjavam svaku (drugu, trecu) liniju koda. pa taj ko ce da cita moj kod ce da bude programer prilicno slicnog nivoa kao ja, ili bolji/gori programer od mene, ali svakako ne amater. jedan od velikih magova programiranja (ne secam se tacno, Wirth cini mi se) je jedared rekao da je najbolji komentar prazna linija u kodu.

i tu se poprilicno slazem. prazna linija u smislu da odvaja logicne celine i postupke u kodu.

dovoljno je recimo na pocetku svake metode napisati red-dva (tri) komentara o tome sta ta funkcija radi, koji su ulazni, koji izlazni parametri. i toliko. tek ako funkcija ne radi svoj posao, covek treba da ulazi u njene detalje.

drugo, imenovanje promenjivih. tu postoje dva stila. prvi je davanje_dugackih_i_opisnih_imena_promenjivima, a drugi je koriscenje a, b, c, x, y, i, j, k, sx, sy, ex, ey, etc. ovaj drugi podrazumeva kratak komentar pri deklaraciji promenjivih (sta cemu sluzi...)

i to je to. onda josh treba gledati da metode mogu da stanu na jedan ekran, (30-40 linija koda) jer je to neka zgodna merka zbog vise razloga. i dodati tome onaj prazan red svuda gde je to logicno, i to je to...

ovo sto ti opisujes je preterano. to se obicno radi u knjigama koje objasnjavaju neku tematiku, ili u kodu koji se koristi na predavanjima (to sto si ti naveo kao primer) ali u stvarnom zivotu, to je veci smor nego pomagalo.

Treba da je to to. Može se naravno optimizovati tako da je zahtev za memorijom
a ne , preciznije ali to zaista ne mogu sada da radim, iskočio sam iz kreveta u 4 ujutro sa rešenjem.

f



Hm, jutro je izgleda pametnije od večeri... ,



, ali od toga ništa ne bi bilo da nije formule...



I, napokon, prljavi pokvareni udarac kog se neću usuditi da komentarišem jer radi samo na računarima sa beskonačno tačnom floating point aritmetikom.

Naime,



Ali je



što se može izračunati u konstantnom prostoru i linearnom vemenu. Zatim:



f



[Ovu poruku je menjao filmil dana 18.11.2002. u 20:42 GMT]

Hm, ja sam se zezao malo na casu i dosao da je resenje 2^(n-1)... ?! Moze biti da gresim, ali ako sam u pravu:


Mada pretpostavljam da nisamo pogodio... :(

Dokaz da neko tvrđenje nije tačno je izvedeno ako ono nije tačno za jedan primer. Dati primer u prvoj poruci je za n=3, a rezultat je 5.

Pretpostavljam i ja da nisi pogodio :)


A komentar uz moj kod (pre formule): T(n^2), M(n)

Formulu dalje ne komentiram :)

Pozdrav

Nisam mogao da odolim ali da ne kažem jedno na sve ovo - ova tema ODGOVARA U POTPUNOSTI nazivu ove diskusione grupe! :) Dakle, ipak se desi da neke teme odgovaraju... ;)