algoritmi.104galimpic,
-> #101, mmarkovic> Nadam se da će tvoje ime biti još višlje u impresumu, ali ne Gremlinovom
> zaslugom ;)
Uff... jednom prilikom, dok je Gremlin bio na InfoFestu u Budvi, imao
sam svojih nedelju dana glavnouredničke prakse. Kakav haos i užas!
Možda sam ja neorganizovan, možda atmosfera u društvenom preduzeću
kakvo je BIGZ nije najbolja, ali... nikad više! Jedva se iščupah iz
tog pakla! Od tada ne zameram Gremlinu kada po tri puta zaboravi
nešto na šta ga podsećam.
> Pogledah ti res. Ideš u Kanadu. A zašto? I zbog para, sigurno.
Idem da bih bolje živeo i da ne gledam kako ponovo tonemo u komunizam.
Za ovo prvo trebaju pare, jasno, ali kao sredstvo.
> 1. da se za takmičenje otvori neka druga tema u ovoj conf.
Dobra ideja, ali tek ako takmičenje zaživi.
> ne zaslužuje da ostane u temi kao neka vrednost! Toliko je prosto, da
> verovatno može da se reši if-ovima, kakva heuristika )
To sam i ja mislio, pa ispade malo teže. Nije kvadratura kruga, jasno,
ali je potrebno pola sata - sat da se završi ako sve ide OK, taman za
ovo takmičenje.
> 2. da zadaci budu teži i praktičniji, sa većim rokovima i vrednijim
> nagradama ( recimo, licencirani prog.paketi )
Onda bi nam trebao i sponzor, jer Sezam to ne može da finansira.
Mislim da je nagrada koju predlažeš predimenzionirana, ali da bi
duža pretplata na Sezam ili Računare bile dovoljno primamljive.
> 3. da se programi daju u source-u, i da posle takmičenja budu PD
Za PD mislim da se niko neće buniti, ali zamisli kako izgleda source
kada se sve radi na brzinu. Ne mogu da teram autore da to srešuju.
BTW Malo smo odlutali od namene ove teme, lepo su mi govorili da takmičenje
treba da ide u 'razno'.
algoritmi.105mmarkovic,
-> #103, embeSubject: takmičenje u programiranju
> A zadatak se i resavao sa if-ovima. Ne mislis valjda da je trebalo praviti
> "vestacku inteligenciju" za ovaj tip zadatka.
vinkom je spomenuo heuristiku. ( 1.71 ). Takvo rešenje bi bilo i vrednije od
"klasičnog", ali se ne može uraditi na brzinu. Može i heuristika, sigurno,
ali ne na takmičenju "ko prvi" ...
> Ne znam zasto se pljuje po ovoj tako dobroj ideji. Sigurno postoji sansa da
> ovo takmicenje preraste u nesto ozbiljnije. Do tada ce se valjda i
> pronaci prava mera kao i prave propozicije.
Ne, ne pljujem ja po toj ideji. Reakcija je bila pre svega na
"Clipper viri..."
Čak sam predložio:
1. posebna tema
2. teži i praktičniji zadaci
3. vrednije nagrade
> O vecim nagradama moze samo da se sanja, potrebni bi bili sponzori
> koji bi nasli svoj interes u tome.
Tako je. PCPRESS poklanja vrednu nagradu u svakom broju SAMO za popunjavanje
anketnog lista.
Neka im daju popust od 10-20-30% za reklame ako sponzorišu takmičenje. Neka
takmičenje bude na 2-3 meseca. Skupilo bi se, iha.
algoritmi.106embe,
Sta je sa predlogom da se takmicenja proguste ?
algoritmi.107galimpic,
-> #101, mmarkovic> Nadam se da će tvoje ime biti još višlje u impresumu, ali ne Gremlinovom
> zaslugom ;)
Uff... jednom prilikom, dok je Gremlin bio na InfoFestu u Budvi, imao
sam svojih nedelju dana glavnouredničke prakse. Kakav haos i užas!
Možda sam ja neorganizovan, možda atmosfera u društvenom preduzeću
kakvo je BIGZ nije najbolja, ali... nikad više! Jedva se iščupah iz
tog pakla! Od tada ne zameram Gremlinu kada po tri puta zaboravi
nešto na šta ga podsećam.
> Pogledah ti res. Ideš u Kanadu. A zašto? I zbog para, sigurno.
Idem da bih bolje živeo i da ne gledam kako ponovo tonemo u komunizam.
Za ovo prvo trebaju pare, jasno, ali kao sredstvo.
> 1. da se za takmičenje otvori neka druga tema u ovoj conf.
Dobra ideja, ali tek ako takmičenje zaživi.
> ne zaslužuje da ostane u temi kao neka vrednost! Toliko je prosto, da
> verovatno može da se reši if-ovima, kakva heuristika )
To sam i ja mislio, pa ispade malo teže. Nije kvadratura kruga, jasno,
ali je potrebno pola sata - sat da se završi ako sve ide OK, taman za
ovo takmičenje.
> 2. da zadaci budu teži i praktičniji, sa većim rokovima i vrednijim
> nagradama ( recimo, licencirani prog.paketi )
Onda bi nam trebao i sponzor, jer Sezam to ne može da finansira.
Mislim da je nagrada koju predlažeš predimenzionirana, ali da bi
duža pretplata na Sezam ili Računare bile dovoljno primamljive.
> 3. da se programi daju u source-u, i da posle takmičenja budu PD
Za PD mislim da se niko neće buniti, ali zamisli kako izgleda source
kada se sve radi na brzinu. Ne mogu da teram autore da to sređuju.
BTW Malo smo odlutali od namene ove teme, lepo su mi govorili da takmičenje
treba da ide u 'razno'.
algoritmi.108galimpic,
-> #106, embe> Sta je sa predlogom da se takmicenja proguste ?
Već posle prvog kola? Ajde, važi, ali nemoj da mi opet učestvuje
troje ljudi. Dakle, u nedelju u podne idemo opet. Biće i zvanično.
algoritmi.109plovput,
-> #108, galimpic+| Već posle prvog kola? Ajde, važi, ali nemoj da mi opet učestvuje
+| troje ljudi. Dakle, u nedelju u podne idemo opet. Biće i zvanično.
Bolje da zadaci budu vezani za grafiku (barem neki put).
Znaci zoomiranje slike, rotiranje, neki demo efekti..
Pa kome radi program brze i koji je lepsi i kraci odnosi nagradu.
Time bi se i zadovoljio time limit sto se tice brzine slanja resenja.
Da se da rok do nekih 5 dana kako bi svi stigli em da vide zadatak em da
ga posalju.
Ovako imamo situaciju da u jednom textpadu mozemo videti i zadatak
i odgovor a ko zna mozda vec i proglasenje pobednika sto nije dobro.
algoritmi.110embe,
-> #108, galimpic>>>> Vec posle prvog kola? Ajde, vazi, ali nemoj da mi opet ucestvuje
>>>> troje ljudi. Dakle, u nedelju u podne idemo opet. Bice i zvanicno.
Sigurno ce biti MANJE OD TROJE LJUDI, ako se ne uputi poruka koju ce svi
moci da procitaju, tj. sistemska poruka. Tako ce se i oni koji ne
prate ovu konferenciju mozda zaintrigirati !
Sto se tice predloga (1.109 plovput-a), mislim da je ipak bolje da
se ostane u domenu algoritama i ocenjivanja programa sa tacno-netacno.
U suprotnom, pitanje najboljeg resenja moze biti stvar subjektivne
procene, a to je stvarno, stvarno skakljivo....
algoritmi.111vitez.koja,
-> #110, embe#=> Sto se tice predloga (1.109 plovput-a), mislim da je ipak bolje da
#=> se ostane u domenu algoritama i ocenjivanja programa sa
#=> tacno-netacno.
Ocenjivanje programa sa tačno-netačno bi trebalo da bude samo na
osnovu test podataka, te da to što korisnici-takmičari dodatno
ispituju taj program (i nalaze falinke, kao što je autor sada našao
sam sebi za program koji je prvobitno proglašen pobednikom ;), ne bi
smelo da utiče na ocenu tačnosti programa, tj. da je potpuno
dozvoljeno uraditi i program tipa
if test_primer_1 then print bla_bla_1
else if test_primer_2 then print bla_bla_2
else ....
ako se na neki volšeban način dođe do test primera...
sk
algoritmi.112vinkom,
-> #105, mmarkovic> vinkom je spomenuo heuristiku. ( 1.71 ).
Evo da se i ja, kao jedan od ucesnika takmicenja, javim. Zadatak
sam resio pomocu nekakve heuristike koja se sastojala u tome da
sam kod odlucivanja koji cu potez odigrati, odigrao sve moguce
partije do kraja pocevsi od trenutne situacije na tabli (to sam
mogao u realnom vremenu zbog male dimenzije table). Sabirao sam
koja su zadnje odigrana pobednicka polja za kompjuter odnosno
za coveka, te sam odigrao potez na ono polje koje je najvise
odgovaralo coveku (tj. na maksimalnu razliku 'covek je sa tim
poljem pobedjivao' minus 'kompjuter je sa tim poljem pobedjivao').
Sama formula je imala i mana koje sam naknadno 'frizirao' IF
naredbama. Naime prva verzija je gubila od coveka, sledeca nije
dobijala uvek kad je mogla, a nadam se da zadnja ispunjava sve
zadane kriterije.
Ovaj nacin resavanja u momentu mi se ucinio boljim od upotrebe
IF naredbi. Iako sa neizvesnim ishodom istrajao sam do kraja.
Moglo se to i bolje resiti da je kompjuter igrao u tom
'razigravanju' inteligentno, tj. najbolje sto moze, pa se
jednostavno odabere onaj potez gde kompjuter sigurno pobedjuje
ili u najgorem slucaju igra nereseno. No, tada bi uleteo u malo
slozenije rekurzije, gde je postojala mogucnost zapetljavanja,
a to u brzinskom takmicenju nisam smeo dozvoliti.
Eto toliko o zadatku i heuristici.
Sto se tice takmicenja misljenja sam da bi trebalo i dalje da
bude brzinsko. Takmicenje na duzi rok bile su 'Pitalice' u
'Racunarima'. Ne znam zasto se to takmicenje po drugi put ugasilo
kada se vidi da za njega postoji interesovanje. Tu su se mogli
davati i tezi i ozbiljniji zadaci, a u ovakvom brzinskom
takmicenju zadaci bi trebali biti tezine zadataka saveznog
takmicenja iz informatike ili informatickih olimpijada i opsteg
tipa kako bi svi imali podjednake sanse. Samo takmicenje ne bi
trebalo da traje duze od 1 do 3 sata. Vreme odrzavanja je dobro,
dakle kroz jutro neradnim danom kad telefonske linije nisu
zagusene, a i na SEZAM-u nema puno korisnika te se na taj nacin
ne gubi, tada dragoceno, vreme cekajuci na uspostavljanje veze.
I na kraju jos dva predloga:
- da se kontrolor (galimpic) cesce ukljucuje i kontrolise resenja,
te daje izvestaje o toku takmicenja,
- da se datoteka sa test podacima okaci u konferenciju kako bi i
mi mogli da testiramo i vrednujemo pristigla resenja na kraju
takmicenja i eventualno damo svoje primedbe (to se moze izvesti
tako da se sifrovana datoteka sa test primerima okaci zajedno sa
zadatkom (u 12:00), a kad se proglasi pobednik da se dostavi kljuc
kojim cemo desifrovati test datoteku i proveriti svoje i
konkurentske programe).
Izvinjavam se na duzini teksta, ali nakupilo se ovih nekoliko dana :)
algoritmi.113galimpic,
-> #111, vitez.koja> ako se na neki volšeban način dođe do test primera...
Neće se doći do test primera. Tačka.
algoritmi.114galimpic,
-> #112, vinkom> Zadatak
> sam resio pomocu nekakve heuristike koja se sastojala u tome da
> sam kod odlucivanja koji cu potez odigrati, odigrao sve moguce
> partije do kraja pocevsi od trenutne situacije na tabli
Onda to nije heuristika već gruba sila, zar ne?
> - da se datoteka sa test podacima okaci u konferenciju kako bi i
> mi mogli da testiramo i vrednujemo pristigla resenja na kraju
> takmicenja i eventualno damo svoje primedbe (to se moze izvesti
> tako da se sifrovana datoteka sa test primerima okaci zajedno sa
> zadatkom (u 12:00), a kad se proglasi pobednik da se dostavi kljuc
> kojim cemo desifrovati test datoteku i proveriti svoje i
> konkurentske programe).
Tada bi trebale dve prve nagrade za dve različite grupe rešavača:
jedna za najbržeg programera, druga za najboljeg razbijača šifre :)
algoritmi.115galimpic,
Moraćemo da ipak odložimo takmičenje za sledeću nedelju. U pitanju su neki
tehnički razlozi.
algoritmi.116deimos,
-> #112, vinkom>> Evo da se i ja, kao jedan od ucesnika takmicenja, javim. Zadatak
>> sam resio pomocu nekakve heuristike koja se sastojala u tome da
>> Ovaj nacin resavanja u momentu mi se ucinio boljim od upotrebe
>> IF naredbi. Iako sa neizvesnim ishodom istrajao sam do kraja.
Svaka cast, ali zar niko nije razmisljao o tome da su za
ovu igru (sa programerskog stanovista) dovoljni samo par uslova?
S obzirom da je tabla samo 3x3, vazi sledece:
1. Ako je komp u sredini polja ili na sredini strane
onda sme da igra samo po sredini stranica, odnosno u
centar dok je to moguce, a onda pod 3).
2. Ako je komp u uglu, onda mora da igra po uglovima, sve
dok je to moguce , a onda po poljima udaljenim najmanje
za dva, a zatim pod 3).
3. Komp igra bilo gde (ako se dodje do ovde onda je sigurno
nereseno).
Ovim metodom se dobija sledece:
- Program ne mora da prati covekove poteze
- Program ne mora da prati svoje poteze
- Program prati samo zauzeta mesta u 9-o clanom nizu.
- Druga od dve procedure u celom programu samo
proverava da li je partija gotova (ima li pobednika).
Normalno, da je tabla NxM, onda bi bilo mozda zgodnije da se radi
po principu heuristike ili neceg slicnog, mada je i onda ovo primenljivo,
samo sto bi se lista uslova produzila, pa bi bilo suvise glomazno.
>> Sto se tice takmicenja misljenja sam da bi trebalo i dalje da
>> bude brzinsko. Takmicenje na duzi rok bile su 'Pitalice' u
>> tipa kako bi svi imali podjednake sanse. Samo takmicenje ne bi
>> trebalo da traje duze od 1 do 3 sata. Vreme odrzavanja je dobro,
Ne slazem se, jer nisu svi u mogucnosti da rezervisu
nedelju u 12-15h za takmicenje na Sezamu, jer Sezam nije obaveza,
vec je vise na razonodnoj bazi za vecinu korisnika, koji bi i
pored svojih obaveza zeleli da se takmice. Konkretno, ja sam bio
sprecen prosli put da se odazovem u to vreme, a zadatak sam video
tek u ponedeljak po podne, a sigurno nisam poslednji koji je procitao
poruku sa zadatkom.
Ako bi se dao rok, npr: saljite resenja zadatka od trenutka kada
je objavljen do <narednih-par-dana>. Konkretno to bi znacilo sledece:
- Takmicenje traje od 12h u nedelju do 12h u npr. sredu.
- Rezultati u vidu tabele (1., 2., 3. ... mesto ) se
objavljuju izmedju srede i nedelje, kao i prilazu primedbe
i komentari ( za ovo bi stvarno mogla i posebna tema,
narocito ako je u vidu da takmicenja budu redovna ).
- Poslata resenja salju se u conf. da bi i ostali ucesnici, ako
'ziriju' promakne, mogli da ukazu na neispravnost nekog resenja.
Ovime ce se bitno povecati broj ucesnika, a sa tim i konkurencija,
pa ce i celo takmicenje biti zanimljivije.
>> I na kraju jos dva predloga:
>> - da se kontrolor (galimpic) cesce ukljucuje i kontrolise resenja,
Ovo je dobra ideja. 'Kontrolor' bi mogao, u slucaju da takmicenje
traje par dana, svakog dana da neku vrstu 'prolaznog vremena',
diskvalifikacije, ukaze na masovno dezinterpretiranje pravila O:)...
Izvinjavam se na duzini poruke.
.dEiMoS.
algoritmi.117vinkom,
-> #114, galimpic>> Zadatak
>> sam resio pomocu nekakve heuristike koja se sastojala u tome da
>> sam kod odlucivanja koji cu potez odigrati, odigrao sve moguce
>> partije do kraja pocevsi od trenutne situacije na tabli
> Onda to nije heuristika vec gruba sila, zar ne?
Heuristika dolazi posle upotrebe grube sile. Rezultate dobijene
upotrebom grube sile trebalo je na neki nacin intepretirati i
odabrati sledeci potez. Za interpretacije koje sam koristio nisam
unapred znao da li su dobre, dokle nisam testirao program i video
kako ce se ponasati. Sve je bilo bazirano na nekom osecaju da je
to prava stvar. Od svih interpretacija (pa mozemo reci i
heuristickih formula) ja sam izabrao onu koja se najbolje ponasala,
tj. izabirala najbolji potez.
Gruba sila bi ostala gruba sila da je kompjuter u tom razigravanju
igrao inteligentno, tj. kod odigravanja svog poteza koristio ovu
istu proceduru kojom odigrava i potez u pravoj partiji, pa da se
onda odabere onaj pravac gde se sigurno dobija ili igra nereseno.
To nisam igrao jer sam izbegavao komplikacije. Kod razigravanja u
ovom programu potezi su nasumice bili odigrani, tj. popunjavalo se
prvo slobodno polje kako za coveka tako i za kompjuter.
>> takmicenja i eventualno damo svoje primedbe (to se moze izvesti
>> tako da se sifrovana datoteka sa test primerima okaci zajedno sa
>> zadatkom (u 12:00), a kad se proglasi pobednik da se dostavi kljuc
>> kojim cemo desifrovati test datoteku i proveriti svoje i
>> konkurentske programe).
>Tada bi trebale dve prve nagrade za dve razlicite grupe resavaca:
>jedna za najbrzeg programera, druga za najboljeg razbijaca sifre :)
Ja ipak mislim da bi bila dovoljna jedna prva nagrada, ali bi se
zadatak u startu resavao na dva sustinski razlicita nacina. Jedan bi
bio normalno resavanje problema, a drugi razbijanje sifre i pravljenje
programa IF <test1> then <resenje1>... , pa ko bude brzi, samim tim i
bolji :)
algoritmi.118embe,
deimos:(1.116)
>> 1. Ako je komp u sredini polja ili na sredini strane
>> onda sme da igra samo po sredini stranica, odnosno u
>> centar dok je to moguce, a onda pod 3).
>> 2. Ako je komp u uglu, onda mora da igra po uglovima, sve
>> dok je to moguce , a onda po poljima udaljenim najmanje
>> za dva, a zatim pod 3).
>> 3. Komp igra bilo gde (ako se dodje do ovde onda je sigurno
>> nereseno).
Koliko sam razumeo ova pravila, sa njima se dobija SAMO korektno
igranje. U u svakom slucaju ovo nisu najbolji potezi. Gde je tu
anticipacija "mata" u dva poteza...
vinkom:(1.112)
><>< Sto se tice takmicenja misljenja sam da bi trebalo i dalje da
><>< bude brzinsko. Takmicenje na duzi rok bile su 'Pitalice' u
><>< 'Racunarima'. Ne znam zasto se to takmicenje po drugi put ugasilo
deimos:(1.116)
<><> - Takmicenje traje od 12h u nedelju do 12h u npr. sredu.
<><> - Rezultati u vidu tabele (1., 2., 3. ... mesto ) se
<><> objavljuju izmedju srede i nedelje, kao i prilazu primedbe
<><> i komentari ( za ovo bi stvarno mogla i posebna tema,
Mozda bi se mogli pomiriti oni koji su za "brzanjac" i oni
koji su za "sporac", a da pri tome ne budu osteceni ni jedni ni
drugi. Iako bi se takmicenje odrzavalo nekoliko dana, pobednik
bi bio onaj koji prvi posalje potpuno tacno resenje. A da bi se
pomirila ta dva uslova, mora se napraviti jedno ogranicenje:
U jednom danu, jedan takmicar moze da posalje SAMO JEDNO resenje;
Ovime se ocigledno:
- daje veca sansa onima koji nisu na Sezamu u odredjeno vreme,
- i dalje moze objektivno, a ne subjektivno ocenjivati program,
- olaksava posao Kontroloru, jer ce biti manji broj resenja,
- povecava napetost i zanimljivost (morace se dobro testirati
program kod kuce, a za to vreme neko moze da vas preduhitri,
testiranje je neophodno, jer pravo na sledeci pokusaj se ima tek
sledeceg dana)
Pozdrav, EMBE
algoritmi.119embe,
-> #116, deimos>>>> - Poslata resenja salju se u conf. da bi i ostali ucesnici, ako
>>>> 'ziriju' promakne, mogli da ukazu na neispravnost nekog resenja.
Pa i jesu. SVA resenja su se mogla prekontrolisati.
algoritmi.120sjocic,
-> #115, galimpic├> Moraćemo da ipak odložimo takmičenje za sledeću nedelju. U pitanju su
├> neki tehnički razlozi.
U međuvremenu, evo je igrica iz prvog zadatka ali u Win varijanti.
Mogućnosti 3x3, 3x3x3, 4x4x4, ali videćete već sami...
xo.zipalgoritmi.121space.ace,
-> #116, deimos--> Ovo je dobra ideja. 'Kontrolor' bi mogao, u slucaju da takmicenje
Šta je ovo, 'Kontrolori' ponovo među nama? A baš smo ih se otarasili!!! ;)
algoritmi.122deimos,
-> #118, embe>> Koliko sam razumeo ova pravila, sa njima se dobija SAMO korektno
>> igranje. U u svakom slucaju ovo nisu najbolji potezi. Gde je tu
>> anticipacija "mata" u dva poteza...
Ne, ovo su samo osnovni uslovi (po mojoj zamisli) receni
srpskim jezikom, to bi se u realizaciji malo drugacije primenilo,
mada bi i direktna primena ispunila uslove zadatka.
>> >>>> - Poslata resenja salju se u conf. da bi i ostali ucesnici, ako
>> >>>> 'ziriju' promakne, mogli da ukazu na neispravnost nekog resenja.
>> Pa i jesu. SVA resenja su se mogla prekontrolisati.
Tri stavke koje sam naveo trebale su da budu moj predlog za
stalne propozicije takmicenja, a ova poslednja je tu zato sto su
bili i predlozi da se resenja salju na mail, sto ne smatram 'sportski'.
Inace, vise sam uzivao u razgledanju, testiranju i trazenju bagova
u ostalim programima, nego sto sam uzivao dok sam pravio svoj
program, pa bih voleo tako i da ostane...
.dEiMoS.
algoritmi.123vinkom,
-> #116, deimos> 1. Ako je komp u sredini polja ili na sredini strane
> onda sme da igra samo po sredini stranica, odnosno u
> centar dok je to moguce, a onda pod 3).
> 2. Ako je komp u uglu, onda mora da igra po uglovima, sve
> dok je to moguce , a onda po poljima udaljenim najmanje
> za dva, a zatim pod 3).
> 3. Komp igra bilo gde (ako se dodje do ovde onda je sigurno
> nereseno).
Algoritam nije bas najprecizniji, ali recimo:
1. C = 5
2. K = 2 (za prvi potez nista nije precizirano)
3. C = 1
4. K = 4 Po pravilu 1., a na osnovu odigranog 2. poteza
5. C = 9 Covek je pobedio
Ili mozda:
1. C = 5
2. K = 1
3. C = 2
4. K = 7 Po pravilu 2., a na osnovu odigranog 2. poteza
5. C = 8 Covek je pobedio
itd. Dakle, ispada da gore navedeni algoritam samo odigrava poteze
koji i nisu nesto povezani.
> Ovim metodom se dobija sledece:
> - Program ne mora da prati covekove poteze
Pokazali smo da program mora da prati covekove poteze, a posebno
kad covek igra prvi.
> - Program ne mora da prati svoje poteze
Vec se u samom algoritmu kaze se da ako je komp. tu i tu igra tu i
tu, pa ispada da mora da prati i svoj(e) poteze.
Ova igrica koliko god bila mala ima i svoju strategiju koja i nije
bas toliko jednostavna. Koliko god se heuristika cinila komplikacijom
u sustini sve je reseno sa dve dvolinijske uzajamno rekurzivne
procedure i petljom koja trazi maximum. Istina bilo je testiranja
programa, ali nisu bile potrebne detaljne analize strategije igre.
Ja bih posebno bio zadovoljan da nisam morao to resenje dodatno da
friziram sa nekim IF-om, ali sam i ubedjen da bi spretnije izabrana
heuristicka funkcija resila celi problem. U svakom slucaju sa
heuristikom i program ima dusu.
Sve u svemu ipak vodimo diskusiju u okviru teme :)
>> Sto se tice takmicenja misljenja sam da bi trebalo i dalje da
>> bude brzinsko. Takmicenje na duzi rok bile su 'Pitalice' u
> Ne slazem se, jer nisu svi u mogucnosti da rezervisu
> nedelju u 12-15h za takmicenje na Sezamu, jer Sezam nije obaveza,
Sta bi po tebi bio kriterij po cemu bi se rangirali takmicari. Od
njih imas samo EXE kod i vreme kada su ga poslali. Ako je kriterij
ispravan program za ocekivati je da ce vise takmicara u duzem roku
dati tacno resenje. Da ne kazem da neko moze skinuti necije resenje,
preimenovati ga i poslati kao svoje. Ako kao dodatni kriterij uzmes
vreme, opet ce biti osteceni oni koji nisu u igri od pocetka, tj. u
istom PAD-u procitat ce i zadatak i resenje. Zato bi stvarno ovo
takmicenje trebalo ostati brzinsko, a sami takmicari i da se malo
zrtvuju ako zele da ucestvuju, a ako se ne moze i ne mora se svaki
put ucestvovati. Iako mozda zvucim kontradiktorno i meni vise
odgovara duzi rok, ali bi tada takmicenje bilo kao sto su nekad
bile 'Pitalice'. Pa kad sam ih opet spomenuo da pitam galimpic-a
zasto je to takmicenje ukinuto.
algoritmi.124janko,
-> #123, vinkom
> Sta bi po tebi bio kriterij po cemu bi se rangirali takmicari. Od
> njih imas samo EXE kod i vreme kada su ga poslali. Ako je kriterij
Ovo je po meni i glavna slabost takmičenja. Jedino za takmičenja
kod kojih nema interakcije (introi) ima smisla tražiti samo EXE.
Dokazati ispravnost EXE programa je za bilo koji složeniji problem
(dakle čim je reč o interakciji) najčešće praktično nemoguće.
algoritmi.125deimos,
-> #123, vinkom>> Algoritam nije bas najprecizniji, ali recimo:
>> 1. C = 5
Nismo se bas najbolje razumeli, ali vec sam rekao da ga
nisam direktno primenjivao...
>> > - Program ne mora da prati svoje poteze
>> Vec se u samom algoritmu kaze se da ako je komp. tu i tu igra tu i
>> tu, pa ispada da mora da prati i svoj(e) poteze.
Ako gledas tako, onda si u pravu, ali poenta je u tome da
program ne prati sve svoje poteze kako bi nekim predefinisanim
postupkom dobio coveka iz treceg ili petog potezana osnovu onog
od pre dva kruga.
>> Ova igrica koliko god bila mala ima i svoju strategiju koja i nije
>> bas toliko jednostavna. Koliko god se heuristika cinila komplikacijom
>> u sustini sve je reseno sa dve dvolinijske uzajamno rekurzivne
Ima jedna zajednicka stvar za sve programere - svako od nas
misli, i duboko je ubedjen, da je njegovo resenje naj-naj, a ostala
su u najboljem slucaju ok, iako, uglavnom, niko od nas nije u pravu.
(ovo nije uvek pravilo i nije upuceno samo tebi).
Sve u svemu ipak vodimo diskusiju u okviru teme :)
>> Sta bi po tebi bio kriterij po cemu bi se rangirali takmicari. Od
>> njih imas samo EXE kod i vreme kada su ga poslali. Ako je kriterij
1. Tacnost
2. Brzina i velicina programa (efikasnost pri radu)
3. Funkcionalnost, preglednost, pristupacnost korisniku
4. Estetska vrednost programa
5. ...
Moze jos toga da dodje konkurenciju.
Zamisli ovako: imas ispit koji pocinje u 12h i traje do 15h.
Skeledzija prevozi studente preo Morave u grupama od po 15 njih do
fakulteta koji pocinju da rade cim stignu. Ko prvi od svih studenata
uradi vise od 50% (dobije 6-icu), prolazi ispit, a ostali padaju, cak
i ako jos nisu dosli na red kod skeledzije... apsurdno?
Druga stvar bi bila da se skupe svi ucesnici na nekom mestu,
pa da dobiju zadatke i da pocnu u isto vreme. E, onda je tri sata i
vise nego dovoljno, a bilo bi jos bolje da vazi - ko prvi, a ovako...
>> put ucestvovati. Iako mozda zvucim kontradiktorno i meni vise
>> odgovara duzi rok, ali bi tada takmicenje bilo kao sto su nekad
>> bile 'Pitalice'.
Sta fali pitalicama? Sta mislis da su i pitalice bile
brzinske? Verujem da ne bi trajale ni priblizno onoliko koliko jesu...
.dEiMoS.
algoritmi.126vinkom,
-> #125, deimos> Ima jedna zajednicka stvar za sve programere - svako od nas
>misli, i duboko je ubedjen, da je njegovo resenje naj-naj, a ostala
>su u najboljem slucaju ok, iako, uglavnom, niko od nas nije u pravu.
>(ovo nije uvek pravilo i nije upuceno samo tebi).
Nemoj da se ljutis, nisam hteo da kazem da je moje resenje bolje od
resenja sa IF naredbama, vec da ne zaostaje za njima.
> 1. Tacnost
> 2. Brzina i velicina programa (efikasnost pri radu)
> 3. Funkcionalnost, preglednost, pristupacnost korisniku
> 4. Estetska vrednost programa
> 5. ...
Tacnost i brzinu ocekujem od vecine dospelih programa, a velicina
programa bi neke takmicare u startu mogla izbaciti iz igre ako rade
sa losim kompajlerima, a opet druge naterati da pisu programe u
asembleru sto isto nije cilj takmicenja. Sto se tice ostalih
navedenih kriterija mislim da oni spadaju u umetnicki dojam i da nisu
bili cilj ovom takmicenju, a to je napraviti sto brze program koji
resava problem.
> Zamisli ovako: imas ispit koji pocinje u 12h i traje do 15h.
>Skeledzija prevozi studente preo Morave u grupama od po 15 njih do
Slazem se sa tobom da postoje problemi u vidu ogranicenog broja ulaza
u sistem (iako sam se u vreme takmicenja bez problema logovao),
preopterecenosti telefonskih centrala, dvojnika i slicnog. Mozda bi
vreme svakog takmicara trebalo da se racuna od vremena njegovog prvog
logovanja posle ostavljanja zadatka u konferenciju, a da ono mora
biti maksimalno jedan sat posle ostavljanja zadatka.
>>> odgovara duzi rok, ali bi tada takmicenje bilo kao sto su nekad
>>> bile 'Pitalice'.
> Sta fali pitalicama? Sta mislis da su i pitalice bile
>brzinske? Verujem da ne bi trajale ni priblizno onoliko koliko
jesu...
Nisam 'Pitalice' spomenuo u negativnom kontekstu, vec naprotiv.
Mislio sam da bi propozicije za to takmicenje bile iste kao
i za pitalice, tj. slalo bi se resenje sa objasnjenjem i
izvornim kodom programa. Licno mi je jako zao sto je to
takmicenje ponovo prekinuto, kad god sam mogao ucestvovao
sam i o njemu imam veoma pozitivno misljenje.
algoritmi.127galimpic,
-> #123, vinkom> bile 'Pitalice'. Pa kad sam ih opet spomenuo da pitam galimpic-a
> zasto je to takmicenje ukinuto.
Zato što na jesen idem u Kanadu, pa da na vreme stanemo dok se takmičenje
još nije previše razvilo. Ta nova serija "Pitalica" je bila sasvim moja
inicijativa i posao, pa ne znam da li bismo našli drugog da se bavi time.
Sada umesto toga ide nova rubrika (koja još nije do kraja profilisana, btw)
sa lepom osobinom da može da se prekine u svakom trenutku.
algoritmi.128imangovski,
-> #127, galimpic>> bile 'Pitalice'. Pa kad sam ih opet spomenuo da pitam galimpic-a
>> zasto je to takmicenje ukinuto.
>
> Zato sto na jesen idem u Kanadu, pa da na vreme stanemo dok se takmicenje
> jos nije previse razvilo. Ta nova serija "Pitalica" je bila sasvim moja
> inicijativa i posao, pa ne znam da li bismo nasli drugog da se bavi time.
> Sada umesto toga ide nova rubrika (koja jos nije do kraja profilisana, btw)
> sa lepom osobinom da moze da se prekine u svakom trenutku.
Kad smo vec kod Pitalica, jel ima neko resenje one 'cuvene' koju je postavio
DR u kojoj se traze brojevi x i y:jedan covek je rekao 1.matematicaru x, a
drugom y.Kad su se sreli prvi je rekao drugom da zna njegov broj, a na to je
ovaj drugi odgovorio da sad i on zna oba broja. Text je verovatno drugaciji, pa
ako ga neko zna neka ga okaci zajedno sa resenjem.
algoritmi.129deimos,
-> #126, vinkom>> Nemoj da se ljutis, nisam hteo da kazem da je moje resenje bolje od
>> resenja sa IF naredbama, vec da ne zaostaje za njima.
Ma ne ljutim se ja, kometar je bio vise samokriticki, a sto
se tice vrednosti, da ja ocenjujem, sigurno bi vrednovao vise
program koji je radjen putem heuristike nego onaj sa obicnim IFovima.
.dEiMoS.
algoritmi.130embe,
-> #115, galimpic>> galimpic, 10.05.96. 09:49, 95 chr
>> ---------------------------------------------------------
>> Moracemo da ipak odlozimo takmicenje za sledecu nedelju. U pitanju su
>> neki tehnicki razlozi.
Vec je cetvrtak uvece, uoci te sledece nedelje a o takmicenju ni rec!?
Da li ce se odrzati ili ne ?
algoritmi.131galimpic,
-> #130, embe> Vec je cetvrtak uvece, uoci te sledece nedelje a o takmicenju ni rec!?
> Da li ce se odrzati ili ne ?
Ne, ne, biće zadnje nedelje u mesecu kao i prošli put, dakle 26. maja.
Pravila ista, u zavisnosti od broja učesnika prelazimo na nedeljno ili
ostajemo gde jesmo.
algoritmi.133dzakic,
** VANREDNI ZADATAK TAKMIČENJA U PROGRAMIRANJU **
Pošto je galimpić, moderator ove konferencije, ove nedelje zauzet,
pripremili smo još jedan zadatak kao uvertiru za takmičenje koje će,
nadamo se, postati tradicionalno. Propozicije su ovoga puta nešto
drugačije jer je i zadatak malo (?) teži.
Rešenje u izvornom kodu treba dostaviti korisniku 'zadaci'.
Osnovni kriterijum za ocenjivanje je vreme za koje program pronalazi
rešenje, a krajnji rok za dostavljanje rešenja je sreda, 22. maj, do
24.00h ˝ 5 min :). Vreme kada je zadatak poslat ne utiče na plasman.
Autor najboljeg rešenja dobiće tromesečnu pretplatu na SezamNet i
večnu slavu :)
algoritmi.134dzakic,
-> #133, dzakic> ** VANREDNI ZADATAK TAKMIČENJA U PROGRAMIRANJU **
Tekst zadatka biće obljavljen danas (nedelja, 19. maj)
oko 12 časova.
algoritmi.135dzakic,
-> #134, dzakic
** VANREDNI ZADATAK TAKMIČENJA U PROGRAMIRANJU **
Standardni set domina sastoji se od 28 komada od kojih svaki sadrži
dva polja sa određenim brojem tačkica (od 0 do 6, gde je 0 prazna
domina). Pločice su jedinstvene (nema dve domine sa istim rasporedom),
numerisane, i sastoje se od sledećih kombinacija tačkica:
Redni br. Raspored │ Redni br. Raspored
domine polja │ domine polja
─────────────────────────┼─────────────────────
#1 0/0 │ #15 2/3
#2 0/1 │ #16 2/4
#3 0/2 │ #17 2/5
#4 0/3 │ #18 2/6
#5 0/4 │ #19 3/3
#6 0/5 │ #20 3/4
#7 0/6 │ #21 3/5
#8 1/1 │ #22 3/6
#9 1/2 │ #23 4/4
#10 1/3 │ #24 4/5
#11 1/4 │ #25 4/6
#12 1/5 │ #26 5/5
#13 1/6 │ #27 5/6
#14 2/2 │ #28 6/6
Domine X/Y i Y/X su jedna ista domina.
Komplet domina se može postaviti na sto tako da formira pravougaonu
matricu veličine 7 x 8 polja (polje je jedna polovina domine).
Primetimo da ređanje domina nije po pravilima igre, već apsolutno
proizvoljno.
Svaki raspored tačkica (brojeva) može se predstaviti najmanje jednom
"mapom" domina. Mapa se sastoji od matrice iste veličine kao i
struktura domina (7 x 8), takve da element matrice predstavlja redni
broj domine postavljene na odgovarajuće mesto u pravougaonoj
strukturi. Primer jedne pravougaone strukture i odgovarajuće mape
rasporeda domina prikazan je na slici:
Pravogaona struktura Mapa rasporeda domina koje
domina (7 x 8): čine takvu strukturu:
6 6 2 6 5 2 4 1 28 28 14 7 17 17 11 11
1 3 2 0 1 0 3 4 10 10 14 7 2 2 21 23
1 3 2 4 6 6 5 4 8 4 16 25 25 13 21 23
1 0 4 3 2 1 1 2 8 4 16 15 15 13 9 9
5 1 3 6 0 4 5 5 12 12 22 22 5 5 26 26
5 5 4 0 2 6 0 3 27 24 24 3 3 18 1 19
6 0 5 3 4 2 0 3 27 6 6 20 20 18 1 19
Napisati program koji analizira dati raspored brojeva u pravougaonoj
strukturi veličine 7 x 8 i daje pozicije domina iz seta kojima se taj
raspored ostvaruje (mapu).
Ulazna tekst datoteka "DOMINE.IN" nalazi se u tekućem katalogu i
sastoji se od sedam linija sa po 8 celih brojeva u rangu (0..6), koje
odslikavaju raspored polja (tačkica) u matrici. Brojevi su međusobno
razdvojeni sa jednim ili više razmaka (SPACE). Garantuje se korektnost
ulaznih podataka tako da nema potrebe obrađivati situacije koje mogu
nastati usled loše zadatog ulaza (manjak podataka, brojevi van opsega
i sl.)
Korektan program treba da na izlazu prvo ispiše samu ulaznu matricu,
a potom, razdvojenu jednom praznom linijom, mapu domina koje formiraju
zadati raspored polja. Ukoliko ima više rešenja koje zadovoljavaju
zadati problem odštampati ih razdvojene jednom praznom linijom. Na
kraju treba odštampati ukupan broj rešenja.
Primer korektnog ulaza i izlaza dat je ispod:
"DOMINE.IN"
4 2 5 2 6 3 5 4
5 0 4 3 1 4 1 1
1 2 3 0 2 2 2 2
1 4 0 1 3 5 6 5
4 0 6 0 3 6 6 5
4 0 1 6 4 0 3 0
6 5 3 6 2 1 5 3
˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙
Izlaz u "DOMINE.OUT" i na konzolu:
4 2 5 2 6 3 5 4
5 0 4 3 1 4 1 1
1 2 3 0 2 2 2 2
1 4 0 1 3 5 6 5
4 0 6 0 3 6 6 5
4 0 1 6 4 0 3 0
6 5 3 6 2 1 5 3
Mape domina za zadati raspored tačkica:
16 16 24 18 18 20 12 11
6 6 24 10 10 20 12 11
8 15 15 3 3 17 14 14
8 5 5 2 19 17 28 26
23 1 13 2 19 7 28 26
23 1 13 25 25 7 4 4
27 27 22 22 9 9 21 21
16 16 24 18 18 20 12 11
6 6 24 10 10 20 12 11
8 15 15 3 3 17 14 14
8 5 5 2 19 17 28 26
23 1 13 2 19 7 28 26
23 1 13 25 25 7 21 4
27 27 22 22 9 9 21 4
Postoje 2 rešenja za dati raspored.
Rešenje u izvornom kodu dostaviti e-mailom na username "zadaci". U
tekstu poruke napisati okvirno vreme za koje program nalazi rešenje
(procesor, takt), a sors zakačiti kao datoteku uz poruku. Dozvoljeni
su svi živi i mrtvi jezici (nemoj neko da je poslao u Algol-u ;), a
blagu preporuku imaju C/C++ i Pascal.
Kriterijum za ocenjivanje je vreme izvršavanja programa, a krajnji rok
za dostavljanje rešenja je sreda, 22. maj, do 24.00h ˝ 5 min :) Vreme
kada je zadatak poslat ne utiče na plasman.
Autor najboljeg rešenja dobija tromesečnu pretplatu na SezamNet i
večnu slavu :)
algoritmi.136dzakic,
U sredu, 22. maja, u 24h istekao je rok za predaju rešenja zadatka
iz vanrednog kola takmičenja u programiranju.
Da se najpre podsetimo zadatka: Od standardnog seta domina, napravljen
je pravougaonik dimenzija 7 x 8. Trebalo je napisati program koji će
naći sve moguće rasporede domina kojima se može dobiti zadati raspored
"tačkica".
Red je i da otkrijemo poreklo ovog zadatka: Međunarodno takmičenje
u programiranju (ACM) u okviru kojeg je odigran i čuveni meč Kasparov
protiv Deep Blue računara. Dakle, zadatak nije bio nimalo naivan, tako
da ne treba da čudi što je samo 5 rešavača uspelo da izađe na kraj sa
njim! Doduše, naši učesnici su u takmičenju su bili u "nešto" boljem
položaju jer su za zadatak za koji je predviđeno da se rešava najviše
par sati, imali tri dana.
Od 5 pristiglih rešenja, 4 su potpuno tačna, dok jedan program na našem
referentnom testu, na kome je trebalo pronaći 90 rasporeda, nije našao
sva rešenja (doduše ona koja je našao bila su tačna). Očigledno da je
autor imao rešenje "u šaci" ali izgleda da je prevideo neke sitnice :)
U svakom slučaju zaslužuje pohvalu...
Uslovi su bili vrlo "liberalni", tako da smo ostavili potpunu slobodu
u izboru programskog jezika, a kriterijum za rangiranje je bila brzina
nalaženja (svih) rešenja. Moramo priznati da smo i pored ovoga očekivali
uglavnom rešenja na C-u ili Pascalu, eventualno Fortranu, obzirom da je
u pitanju bio rad sa matricama. Međutim, bilo je i iznenađenja...
Moramo napomenuti da su svi programi pronalazili rešenja "munjevito"
tako da je bilo vrlo nezahvalno naći najbrži program. U rešenjima su
se mogle videti svakojake dosetke i optimizacije, ali jedan korisnik
je otišao korak dalje, pa je uzeo "stvar u svoje ruke" ;) i napisao
program u asembleru!
Očigledno je da su optimizacije kompajlera dostigle zavidan nivo, ali
vešt asembleraš će, naravno uz kvalitetan algoritam, napraviti čudo.
Zbog toga, zasluženu pobedu ovoga puta odnosi Boris Daljević (biber)
čiji je program pronalazio rešenja za red veličine brže od svojih
konkurenata. Očigledno je da sledeći put moramo malo "skresati" izbor
alata na više programske jezike, pošto nam je primarni cilj bio da
pobedi najbolji algoritam a ne najbolja optimizacija. Međutim Borisova
pobeda je čista kao suza, jer je on imao i vrlo efikasan algoritam,
koji je ručno optimizovao, za šta je, priznaćete, potrebno izuzetno
znanje i trud (pogledajte kako izgleda učitati matricu u asembleru!)
Pored njega, skrenuli bismo pažnju na program Vinka Marinkovića koji
je, rekli bismo, "najelegantniji" od svih pristiglih, a i vicešampion
u brzini! Svi ispravni programi, u izvornom kodu, nalaze se u arhivi
uz poruku.
Na kraju da damo spisak programera koji su ukrstili koplja oko ovog
problema. (u zagradi je dat indeks koji odslikava odnose brzina
nalaženja rešenja). Programi su testirani na "golom" računaru sa RAM
diskom gde je mereno za koje vreme pronalaze potrebnih 90 rasporeda
domina.
Na našem referentom računaru postigli su sledeće indekse brzine
(poređenja radi, "prazan" C program ima indeks 100):
1. Boris Daljević (biber) 236
2. Vinko Marinković (vinkom) 1335
3. Miloš Hrkić (mhrkic) 2420
4. Milan Blagojević (embe) 3537
5. Vladimir Stojanović (deimos) (Nije pronašao sva rešenja)
Pobedniku čestitke i nagrada, a ostalima više sreće u narednom
(redovnom) kolu, koje će biti već u nedelju! Zadatke ponovo postavlja
galimpic.
P.S. Da ne bude sve ozbiljno pobrinuo se i jedan naš stari korisnik
koga ipak nećemo pomenuti (sigurni smo da se šalio ;). Poruku prenosimo
u celini:
----
ja sam rešijo zadatak,ali neznam kako da ga posaljem,jer je sve na
papiri\u,neznam ni jedan programski jezik,ali sam veoma pametan,pa
sam ga resijo usmeno.ako je ikako moguce,ja cu da dodjem da ti
objasnim kako se radi,a vi da mi date nagradu.tata mi kaze da treba
to da naplatim,ali ovaj put to poklanjam NAJBOLJEM BBSU NA
SVETU!!!!?!???!!!!!! NABOLJI STE!!!! JESTEEEEEEEEE!!!!!! POGOTOVU
CHAT!!!!!
.S
exit
save
Ctrl-Z Kraj
Ctrl-O Pomoć
,
domine.zipalgoritmi.137zvezdan,
-> #136, dzakic>> Očigledno je da sledeći put moramo malo "skresati" izbor
>> alata na više programske jezike
Mislim da ovo ne bi bilo fer prema onima koji, kao pobednik
ovog kruga takmičenja, programiraju na asembleru. Nije biber
kriv što je njegov program drastično brži u odnosu na ostala
rešenja. Čovek se ispraksovao na Spectrum-u gde nije ni mogao
da razmišlja o C-u, a ne kao mnogi koji danas odmah u startu
počinju da rade sa Visual C++ od 650 MB CD-a.
algoritmi.138embe,
Hteo bih da cestitam vinkom-u, mhrkic-u (i deimos-u). Pobedniku
biber-u se iskreno divim. Moram priznati da sam se nadao pobedi (ne
bih ni ucestvovao da nisam), ali bolji su pobedili.
Samo cu malo iskomentarisati takmicenje (u stvari, zatraziti
dodatni komentar dzakic-a)
- Pobednika su odlucivale milisekunde. Kako je to izmereno ?
- Kojim kompajlerima su kompajlirani programi ?
- Da li mogu da se dobiju i EXE verzije programa ? (nemam
Paskal kompajler da bi to sam napravio, a neko nema C...)
> Ocigledno je da sledeci put moramo malo "skresati" izbor
> alata na vise programske jezike, posto nam je primarni cilj
> bio da pobedi najbolji algoritam a ne najbolja optimizacija.
Sto se ovoga tice, mislim da nije u redu. Ovo pokazuje da je
dzakic malo potcenio mogucnosti programera i da nije verovao da
ce neko napraviti program koji moze da uradi posao za nemerljivo
vreme (pobednicki program biber-a). Ne bi trebalo nista "skresati",
jer se time nece dobiti na objektivnosti. Mozda, pouceni ovim
iskustvom, treba izabrati takav zadatak kod koga nece biti potrebe
ili rezona da se pribegava asembleru, odnosno klasama u C++.
Svako neka radi sa onime sto voli, a vi se potrudite za ravnopravnost
takmicara, izborom pravog kriterijuma vrednovanja i pravog zadatka.
Ovo jeste bio pravi zadatak, doduse nesto tezi nego sto se ocekivalo,
ali kriterijum vrednovanja je bio nedefinisan.
Bilo je jako zanimljivo, i neka se nastavi ovo takmicenje. Jos jednom
cestitke biber-u,vinkom-u,mhrkic-u i deimos-u.
Puno pozdrava, embe
P.S. Hoce li ovo takmicenje u nedelju biti "ko-pre" ili nesto
drugo ??
algoritmi.139obren,
-> #138, embePošto smo dzakic i ja zajedno testirali programe, evo "ukratko" da
dam odgovor na neka problematična pitanja. Zak će se i sam sigurno
javiti, no dobro... :)
> - Pobednika su odlucivale milisekunde. Kako je to izmereno ?
Evo kako je vršeno merenje pristiglih programa:
Napravljen je BATCH fajl sledeće sadržine:
cls
timer
%1>nul
%1>nul
...
%1>nul (10 puta)
timer
Prvo je provereno da li programi ispravno nalaze nekoliko "kratkih"
rešenja koje su svi ispravno našli.
Merenje je zatim vršeno na RAM disku, sa isključenim "turbom", na golom
računaru (samo himem.sys) u seriji od 10 merenja i uzimanjem srednje
vrednosti.
Dakle, svi izvršni programi, ulazne i izlazne datoteke sve vreme su bili
u memoriji, tako da brzina diska i video karte nije uticala na merenje.
Sadržaj datoteke DOMINE.IN koja je bila ulaz za finalno merenje je bio
sledeći:
0 1 5 5 0 5 2 2
1 6 2 4 6 3 2 5
1 4 1 3 6 3 5 3
2 4 5 4 2 6 1 0
4 5 6 4 5 1 3 4
6 0 0 0 2 3 1 1
3 0 0 2 3 4 6 6
Trebalo je da programi nađu 90 rešenja za ovaj raspored tačkica, što
su učinili svi programi osim deimos-ovog, koga je izgleda ovaj ulaz
malo zbunio.
> - Kojim kompajlerima su kompajlirani programi ?
C programi su kompajlirani pomoću Borland C v3.1 sa uključenom maksimalnom
optimizacijom i 386 instrukcijama u small memorijskom modelu. Turbo Pascal
programi su kompajlirani pomoću Borland Pascala 7.0, takođe sa maksimalnim
optimizacijama.
C programi su se nešto brže izvršavali prevedeni za OS/2 flat memorijski
model, ali je vreme izvršavanja prilično variralo tako da smo odlučili da
ipak vršimo merenja na goloj DOS mašini.
Što se tiče .EXE programa, biće okačeni koliko sutra (ne zovem od kuće).
Pozdrav, Dragan
algoritmi.140dzakic,
-> #138, embe> > bio da pobedi najbolji algoritam a ne najbolja optimizacija.
> Sto se ovoga tice, mislim da nije u redu. Ovo pokazuje da je
> dzakic malo potcenio mogucnosti programera i da nije verovao da
> ce neko napraviti program koji moze da uradi posao za nemerljivo
> vreme (pobednicki program biber-a).
Upravo tako :) Našli smo interesantan zadatak koji, priznaćete, ako
se rešava 'grubom silom' radi zaista dugo. Osnovna ideja je naravno
odbaciti što je više moguće potencijalnih rešenja tokom pretrage kako
bi se i vreme izvršavanja svelo na minimum. Priznajem da nisam imao
mnogo vremena da posvetim zadatku, a cela ideja sa takmičenjem u
programiranju mi se svidela, pa smo odlučili da problem postavimo
ovde. Kriterijum je u osnovi trebalo da bude najbolja ideja,
algoritam, ali smo bili svesni da se to teško može objektivno
proceniti pa je zato tako i formulisan (nakraće vreme izvršavanja).
Sva primljena rešenja zaista su prijatno iznenadila, posebno rešenje u
asembleru. Meni lično je drago da je neko posvetio vreme asemblerskom
rešavanju ovog zadatka, jer znam koliko je potrebno uložiti truda -
čak više na obradu ulaza i izlaza nego na realizaciju samog algoritma.
Ali, kao što rekosmo, biberova pobeda je čista kao suza i sa moje
strane sve čestitke.
> Mozda, pouceni ovim iskustvom, treba izabrati takav zadatak kod koga
> nece biti potrebe ili rezona da se pribegava asembleru, odnosno
> klasama u C++.
Naravno, samo treba naći takav zadatak. Ako imate predloge kako
propozicijama definisati što ravnopravnije uslove rešavanja, bilo bi
lepo da ih čujemo. I ovim vanrednim zadatkom proverili smo u praksi
koliko propozicija utiču na ishod. Nadam se da smo bliže onome što
želimo da postignemo.
> P.S. Hoce li ovo takmicenje u nedelju biti "ko-pre" ili nesto
> drugo ??
Propozicije narednog takmičenja objaviće galimpić, dakle nastavak
prepuštamo moderatoru.
Pozdrav, Zak
algoritmi.141biber,
-> #137, zvezdan>> ostala resenja. Covek se ispraksovao na Spectrum-u gde nije ni mogao
Ipak je to bilo na Commodore 64 (uglavnom).
algoritmi.142galimpic,
**********************************
** TAKMIČENJE U PROGRAMIRANJU **
**********************************
Pripremite se za drugo, redovno kolo u nedelju u 12.00h. Propozicije su u
poruci 1.59.
algoritmi.143biber,
-> #138, embe>> Svako neka radi sa onime sto voli, a vi se potrudite za ravnopravnost
E ova ti je na mestu! :)
algoritmi.144obren,
Evo prevedenih programa koji su učestvovali na takmičenju...
EMBE.EXE (BC 3.1)
MHRKIC.EXE (BP 7.0)
VINKOM.EXE (BP 7.0)
BIBER.COM (A86 v3.22)
U arhivi je i ulazna datoteka DOMINE.IN
dominexe.zipalgoritmi.145galimpic,
*******************************************
TAKMIČENJE U PROGRAMIRANJU - Zadatak broj 2
*******************************************
Napraviti program koji za zadati broj prstenova rešava problem "Hanojskih
kula" koji se sastoji u sledećem:
Postoje tri stuba: A, B i C. Na Stubu A nalazi se zadati broj prstenova
naslaganih prema veličini: prsten sa najvećim prečnikom nalazi se na dnu,
a sa najmanjim na vrhu gomile. Cilj je prebaciti sve prstenove u istom
rasporedu na prsten B, poštujući sledeća pravila:
1. U jednom potezu se može prebaciti samo jedan prsten sa vrha jednog na
vrh drugog stuba.
2. U svakom trenutku na svakom stubu prstenovi moraju biti raspoređeni prema
prečniku, tako da je najveći na dnu a najmanji na vrhu.
Ulazne veličine: broj prstenova
Izlazne veličine: tekstualni fajl POTEZI.TXT sledećeg sadržaja:
- U prvom redu je zadati broj prstenova
- Slede potezi oblika XY, u značenju sa stuba X na stub Y
svaki potez u posebnom redu
- U poslednjem redu nalazi se ukupan broj poteza.
PRIMER:
c:\>HANOJ.EXE
Unesi broj prstenova: 3
c:\>TYPE POTEZI.TXT
3
AB
AC
BC
AB
CA
CB
AB
7
c:\>_
Zamišljeni početni izgled hanojske kule sa tri prstena:
| | |
=== | |
===== | |
======= | |
-------------------------------
A B C
Zamišljeni završni izgled hanojske kule sa tri prstena:
| | |
| === |
| ===== |
| ======= |
-------------------------------
A B C
Uz zadatak je dat program koji proverava ispravnost fajla POTEZI.EXE
Rešenja šaljite u obliku izvršnih DOS fajlova prikačenih uz poruku koja
je odgovor na ovu poruku. Za detaljnije propozicije pogledajte poruku 1.59.
provera.exealgoritmi.146galimpic,
Pošto sam kasnio 1 minut sa postavljanjem zadatka, za kaznu vam evo i
rešenja. Jedini problem je što morate da provalite šifru ;)
resenje.zipalgoritmi.147galimpic,
-> #145, galimpicKo radi, taj i greši. U postavci piše:
> Uz zadatak je dat program koji proverava ispravnost fajla POTEZI.EXE
Treba, naravno, POTEZI.TXT
algoritmi.148vinkom,
-> #145, galimpicEvo da probamo
hkule.exealgoritmi.149galimpic,
-> #148, vinkom****
STOP
****
vinkom je uspeo iz prve! Prvo da vidimo da li ima zalbi, pa mozemo malo da
popricamo o resenju.
algoritmi.151deimos,
-> #149, galimpic
>> 1.145 PCPROG.6:algoritmi
>> galimpic, 26.05.96. 12:01, 1849 chr
>> 1.148 PCPROG.6:algoritmi
>> vinkom, 26.05.96. 13:21, 16 chr
Time difference 1h 20min
Ja lepo govorih da su propozicije krajnje ne-fer, ali niko
me ne slusa. Ajde ti meni lepo reci u cemu je poenta takcmicenja? Zar
mislis da ce ovo takmicenje zaziveti pored ovakvih pravila? A i zadatak
je 'ubi boze' (za takmicenje u programiranju osnovaca za kvalifikacije
na opstinsko takmicenje, a cak je i laksi od iks-oks za koji smo vec
konstatovali da je prelak). Ako je bilo ljudi koji su uspeli da rese zadatak
sa medjunarodnog takmicenja (ne racunam sebe) i to na vec poznat nacin,
krajnje je glupo postavljati ovako lak zadatak. Daj lepo ko covek ozbiljan
zadatak i ceni zadatak po kvalitetu, a ne po brzini pristizanja resenja
(dzakicev kriterijum je bio odlican). Ja se logovao specijalno da vidim
zadatak, kad, eto tamo i resenja... i to iz prve.
Ako se nismo razumeli, ovo sto kazem je dobronamerno, jer meni je
stalo do takmicenja, i zato ti ovo i govorim, a da mi je sve jedno ili da
mi je samo malo manje stalo do njega, ovo ne bih ni napisao, vec bi
jednostavno ignorisao poruke koje se ticu takmicenja i ne bih vise ni
pokusavao da resim zadatak (ako se ovakva pravila nastave, kroz par kola
ce to biti slucaj sa vecinom, jer znaju da ako je neko slucajno dobio
vezu 1min pre njega, prakticno nema sanse da na vreme posalje resenje).
A i krajnje je vreme da se otvori tema za takmicenje, jer je u ovoj
temi konferencije vecina poruka u vezi istog, a za _algoritme_ prakticno
nema mesta od diskusije. I jos jedna stvar, da me ostali ne bi
preduhitrili konstatacijom - nije pitanje ko ce pobediti, vec je pitanje
duha celog takmicenja, njegovog kvaliteta, zdrave konkurencije i fer
pravila.
Zao mi je, ali sam morao na ovako drastican nacin da dam svoje
misljenje, jer pored onolike diskusije o pravilima, nisi nasao ni jedan
valjan razlog da ucinis neki kompromis, a mislim da je bilo dosta razloga
za to, jer se jako malo ljudi u potpunosti slozilo za navedenim
propozicijama i tezinom zadataka.
.dEiMoS.
algoritmi.152embe,
-> #140, dzakic>> Kriterijum je u osnovi trebalo da bude najbolja ideja,
>>algoritam, ali smo bili svesni da se to tesko moze objektivno
>>proceniti pa je zato tako i formulisan (nakrace vreme izvrsavanja).
S obzirom na nacin testiranja programa to niste mogli. Ako je
najposteniji kriterijum najefikasniji algoritam, a tu se mislim
svi slazemo, onda je testiranje moralo biti drugacije.
Naime, pustajuci moj program kroz Profiler, dosao sam do jednog
podatka: Vreme potrebno za ulaz i izlaz iznosi: 98.6% (rad sa diskom
i konzolom) i 96.1% (ako je u pitanju ram-disk, i bez konzole) ukupnog
vremena izvrsavanja programa. Na prvi pogled razlika je previse mala,
a ocigledan je dobitak na brzini (oko 2-3x za ovaj program) ?
Odgovor je prost, dva su razloga za to:
1. enormno ucesce rada sa periferijama,
2. sam program se brze ucitava u memoriju i spreman je za
ivrsavanje (oko 6x za program ove velicine, na mom racunaru)
Pri ovome treba razbiti zabludu da ce rad sa periferijama biti
brzi onoliko puta koliko je memorija brza od diska ! To vazi
samo za ulaz i izlaz VELIKE kolicine podataka i malo poziva.
Za malu kolicinu podataka i vise pozivanja ulaza i izlaza taj
dobitak je mnooogo manji.
Zakljucak je sledeci:
Bez obzira na izvrsavanje programa sa ram-diska, uticaj rada sa
periferijama je bio preko 90% na vreme izvrsavanja programa.
Ovo se odnosi kako na program pisan u C++ tako i na dva programa
pisana u Paskalu. Kod programa pisanog u asembleru to nije slucaj.
Ispada, a vi me ispravite ako gresim, da su poredak odlucile
brzine sledecih naredbi :
- otvaranje i zatvaranje fajla
- citanje i pisanje po fajlu
- ispis na konzolu
a koje smo bili prinudjeni da koristimo. Vreme izvrsavanja
algoritma uopste nije tretirano!
KAKO TESTIRATI (predlog)
Videli ste da svi programi rade jako brzo. Onda se moralo pristupiti
testiranju tacnosti. Pustiti 2,3,10.. primera, i uveriti se u to.
E sad, dolazi ono najvaznije. Nije mi jasno kako i vi o tome niste
razmisljali. Svaki program se sastojao od dela za ulaz-izlaz i
samog algoritma. Definisete ulazne podatke u samom programu,
pozovete algoritam 1000.... puta, (bez ulaza-izlaza) i razresite sve
dileme o efikasnosti algoritma. Intervenciju biste mogli sasvim lako
izvrsiti, za 3 minuta programerskog posla po programu. Tada biste
mogli reci taj i taj algoritam je najbrzi. Mislim da bi to bilo
korektno.
>>Naravno, samo treba naci takav zadatak. Ako imate predloge kako
>>propozicijama definisati sto ravnopravnije uslove resavanja, bilo bi
>>lepo da ih cujemo.
Propozicije treba da budu : najtacniji, najbrzi, najelegantniji
(bas ovim redosledom) ALGORITMI (kao sto se zove konferencija),
pa bilo oni pisani u Fortranu, Bejziku ili asembleru, svi moraju
biti ravnopravni. To vas obavezuje na pronalazenje metoda za
testiranje ALGORITAMA - iskljucivo. A takmicarima treba dati
uslov da napisu program tako, da algoritam bude jedna kompaktna
celina, koju vi mozete lako upotrebiti za testiranje.
Bio sam opsiran, ali trazili ste predloge.
Pozdrav EMBE
P.S. Jos jednom, sve cestitke pobedniku biberu.
algoritmi.153embe,
-> #151, deimos>>krajnje je glupo postavljati ovako lak zadatak. Daj lepo ko covek ozbiljan
>>zadatak i ceni zadatak po kvalitetu, a ne po brzini pristizanja resenja
>>(dzakicev kriterijum je bio odlican). Ja se logovao specijalno da vidim
Potpuno si u pravu da je zadatak bio prelak. Ipak, svaka cast vinkomu
na brzini. I ja sam resavao zadatak ali sam ga resio sa cetrdeset minuta
zakasnjenja. Bio je laksi nego IKS-OKS jer je ovde bila u pitanju
jedna obicna rekurzija i NISTA vise. Ko je krenuo na pravu stranu,
mogao je zadatak da resi za otprilike sedam minuta.
Ipak je dzakicev zadatak bio primereniji takmicenju. Najveci
problem lezi na organizatoru takmicenja da izabere pravi zadatak.
Mozda treba oformiti konzilijum za izbor i sastavljanje zadataka?
Pozdrav, EMBE
algoritmi.154mmarkovic,
-> #153, embe> Potpuno si u pravu da je zadatak bio prelak. Ipak, svaka cast
> vinkomu na brzini. I ja sam resavao zadatak ali sam ga resio sa
> cetrdeset minuta zakasnjenja. Bio je laksi nego IKS-OKS jer je
> ovde bila u pitanju jedna obicna rekurzija i NISTA vise. Ko je
Nisam učesnik, više navijač;)
Algoritam za Hanojske kule je veoma poznat. Ko je imao QL-a i na
njemu Computer One Pascal, imao je kule kao primer sa čak grafički
prikazanim rešenjem ( animacija prebacivanja prstenova ).
Iako se slažem da je zadatak čak i lakši nego IKS-OKS ( uz poznavanje
problema ili "nanjušivanje" rekurzije ), čini mi se da je ipak bolje
izabran.
Jedino mi se zaista ne sviđa sistem "ko prvi". Kažu stari ljudi,
"na brzinu se samo muve love" :)
Ovako, prvo besomučno kucate, a zatim besomučno zovete...
P.S. U svakom slučaju, čestitke pobednicima i učesnicima u sva tri kruga
algoritmi.155galimpic,
Moje rešenje koje je kao šifrovani ZIP fajl okačeno uz poruku 1.146 može
se (posle skidanja) raspakovati komandom pkunzip resenje.zip -showdoyoudo
Kao što su neki primetili, zadatak je bio lak, ali je algoritam za njegovo
rešavanje zaista elegantan. Čudi me da je bilo potrebno i toliko vremena
(1h i 20min) da neko pošalje odgovor.
algoritmi.156galimpic,
Re: kritike propozicija takmičenja
Gospodo, u pravu ste. Žalim što nisam odmah uvažio vaše mišljenje, ali
sam smatrao da bi trebalo da prođe više od jednog kola za konačnu ocenu
usvojenih pravila. Posle prvog zadatka mišljenja su bila podeljena,
ali je sada jasno da sve mora da se menja iz korena.
Od sada važe sledeće propozicije:
- Zadatak se i dalje postavlja poslednje nedelje u mesecu, tačmo u podne.
Sistemskih obaveštenja više neće biti, ali će biti ostavljena najava u
temi algoritmi.
- Rešenja se dostavljaju kao mail korisniku "zadaci", u obliku razumno
komentarisanog sorsa (isključivo BASIC, C, C++ ili Pascal) i izvršnog fajla,
sa napomenom o vremenu izvršavanja i konfiguraciji na kojoj je postignuto.
- Krajnji rok za slanje rešenja je ponedeljak u ponoć (36 sati kasnije).
- Kriterijum za ocenjivanje je sledeći: uzimaju se u obzir samo potpuno
tačna rešenja u okviru kojih pobeđuje najkvalitetniji algoritam po
subjektivnom utisku organizatora - moje malenkosti. Ako postoji više
sličnih rešenja, pobednika određuje brzina izvršavanja. Nagrada za sada
ostaje ista - mesec dana pretplate.
- Rezultati, sa svim rešenjima i komentarom objavljuju se u utorak popodne.
Napomene:
* Videću sa upravom da li možemo da pređemo na nedeljni umesto mesečnog
režima, s obzirom na nagradu.
* Mislim da je izbor jezika dovoljan, jer obuhvataju najveći procenat
programera. Mogu se naći pogođeni neki koji koriste Modulu-2, FORTRAN
i slično, ali mislim da takvih i nema ovde, a iskomplikovalo bi celu
situaciju. Asembler moram da izbacim iz konkurencije jer ovo od sada
praktično postaje takmičenje algoritama, a asembler jednostavno nije
zgodan za implementiranje algoritama, još manje za analizu i poređenje
sa jezicima opšte namene.
* Shodno ovim pravilima, zadaci će biti nešto teži, a dobro bi bilo da se
posle povede rasprava o kvalitetu pojedinih rešenja, kako bismo najzad
smanjili šum i opravdali naziv teme koju koristimo. Ipak, subjektivna
odluka (koja će biti maksimalno moguće objektivna) o pobedniku je konačna.
Pretpostavljam da se nekima ni ovo neće svideti, pa da vas čujemo.
algoritmi.157space.ace,
-> #151, deimos--> Ja lepo govorih da su propozicije krajnje ne-fer, ali niko
--> me ne slusa. Ajde ti meni lepo reci u cemu je poenta takcmicenja?
--> Zar
Potpisujem sve rečeno. Krajnje ne-fer!!!!
SPA
algoritmi.158obren,
-> #152, embe> KAKO TESTIRATI (predlog)
> Videli ste da svi programi rade jako brzo. Onda se moralo pristupiti
> testiranju tacnosti. Pustiti 2,3,10.. primera, i uveriti se u to.
> E sad, dolazi ono najvaznije. Nije mi jasno kako i vi o tome niste
> razmisljali. Svaki program se sastojao od dela za ulaz-izlaz i
> samog algoritma. Definisete ulazne podatke u samom programu,
> pozovete algoritam 1000.... puta, (bez ulaza-izlaza) i razresite sve
> dileme o efikasnosti algoritma. Intervenciju biste mogli sasvim lako
> izvrsiti, za 3 minuta programerskog posla po programu. Tada biste
> mogli reci taj i taj algoritam je najbrzi. Mislim da bi to bilo
> korektno.
Hmm, meni je recimo ta ideja izuzetno odbojna. Kao prvo, to je
neovlašćeno intervenisanje po tuđem kôdu (ja ne bih dozvolio da mi neko
prepravlja program da bi "merio brzinu"), a drugo, ko zna kako sve mogu
biti napisani programi koji ˙rade˙ tačno! Tu se (verovatno) niko sem
autora ne bi snašao...
Oko vrednovanja prethodnog zadatka (domine) možda je bilo nekih propusta
ali to je tek drugo kolo i treba utabati stazu.
Mislim da je najbolja varijanta u slučaju vrlo bliskih rezultata na
objektivnim testovima (tačnost i brzina), biranje najelegantnijeg rešenja.
Na kraju krajeva, treba dati prednost onome ko piše jase, "lepe" i lako
čitljive progame. Svi će kad tad doći u situaciju da treba da održavaju
tuđi kôd, i tada će znati da cene trud uložen u pregledan i elegantan
program. Sudeći po tvom rezimeu, ti bi to trebao najbolje da znaš.
Problem kod ovog pristupa (elegancija rešenja) je subjektivnost, ali
treba razmotriti ideju da i sami učesnici odlučuju u izboru pobednika?
Takođe, mislim da rešenja treba da budu u izvornom kodu a ne .EXE,
i da treba ograničiti jezike na jezike "najšire populacije" a to su
C/C++, Pascal i BASIC. Čak i oni koji inače upotrebljavaju druge alate
(Modula 2, Fortran i sl.) sigurno znaju i neki od navedenih jezika, a
teško da će zadaci biti takvi da ih ovo jezici sputavaju da se izraze.
Što se tiče asemblera, definitivno sam protiv njega u ovoj temi. Cilj
ovog takmičenja (nadam se) nije materijalna korist, već da se razmrdaju
vijuge, nešto nauči i stekne iskustvo. Mislim da je asembler prevaziđen
u današnje vreme, naročiti za ovakve primene, a i kako će recimo vlasnik
Amige ili Atarija naučiti bilo šta iz ASM sorsa za PC (i obratno)?
Pozdrav, Dragan
algoritmi.159ognjen,
-> #152, embe)-> dileme o efikasnosti algoritma. Intervenciju biste mogli
)-> sasvim lako izvrsiti, za 3 minuta programerskog posla po
)-> programu. Tada biste mogli reci taj i taj algoritam je
)-> najbrzi.
Ne, ne i ne. Da si malo vise gledao izvorne kodove razlicitih
programera, shvatio bi da to nije ni malo lako. Nekad su
potrebni _sati_ da bi neko sa strane provalio kako algoritam
radi. Zato se na svim svetskim olimpijadama i takmicenjima ne
meri lepota samo glavnog algoritma, vec samo celokupna brzina
programa u celini.
algoritmi.160ognjen,
-> #156, galimpic)-> tacna resenja u okviru kojih pobeduje najkvalitetniji
)-> algoritam po subjektivnom utisku organizatora - moje
)-> malenkosti.
Sta znaci najkvalititniji algoritam, po tvom misljenju,
naravno? Najbrzi? Najelegantniji? Najcistiji?
algoritmi.161embe,
-> #158, obrenJa>>> dileme o efikasnosti algoritma. Intervenciju biste mogli sasvim lako
Ja>>> izvrsiti, za 3 minuta programerskog posla po programu. Tada biste
>>Hmm, meni je recimo ta ideja izuzetno odbojna. Kao prvo, to je
>>neovlasceno intervenisanje po tudem kôdu (ja ne bih dozvolio da mi neko
>>prepravlja program da bi "merio brzinu"), a drugo, ko zna kako sve mogu
>>biti napisani programi koji ˙rade˙ tacno! Tu se (verovatno) niko sem
>>autora ne bi snasao...
Ni meni samom se ne svidja da neko drugi vrsi izmene u kôdu, ali jos
manje mi se svidja ideja o pausalnom ocenjivanju vrednosti algoritma
na osnovu brzine CELOG programa. To bi bilo, kao kada bi se kvalitet
jednog automobila merio potrosnjom goriva , ili njegovom brzinom, a
ne izradom ili kvalitetom njegovih delova.
Zato sam, u daljem tekstu mog komentara i bio napisao da program
mora da bude tako napisan da algoritam bude kompaktna celina
koja se moze zasebno analizirati. Jedna od analiza je i logicka
analiza algoritma, ali po potrebi (vise dobrih resenja) mora se
omoguciti i "testiranje motora na stolu", sto bi izuzetno lako
moglo da se resi od strane takmicara, sa par #define -a u C-u,
a za ostale jezike je verovatno isto tako jednostavno.
Opet napominjem, sve se ovo odnosi na uporedjivanje kvaliteta
priblizno dobrih algoritama, znaci, kada logicka analiza ne moze
pouzdano da odgovori na pitanje ko je najkvalitetniji?
>>citljive progame. Svi ce kad tad doci u situaciju da treba da odrzavaju
>>tudi kôd, i tada ce znati da cene trud ulozen u pregledan i elegantan
>>program. Sudeci po tvom rezimeu, ti bi to trebao najbolje da znas.
Naravno, makar i po cenu "smanjene" brzine, uvek, UVEK, se mora
pisati pregledan kôd.
Pozdrav, EMBE
algoritmi.162embe,
-> #156, galimpic> Resenja se dostavljaju kao mail korisniku "zadaci", u obliku razumno
> komentarisanog sorsa (iskljucivo BASIC, C, C++ ili Pascal) i izvrsnog fajla,
> sa napomenom o vremenu izvrsavanja i konfiguraciji na kojoj je postignuto.
Opet ce se meriti brzina ? Onda se potrudite da razlika izmedju prvog
i poslednjeg bude veca od jedne milisekunde. :)) (naravno izborom
zadatka)
>> Videcu sa upravom da li mozemo da predemo na nedeljni umesto
>> mesecnog rezima, s obzirom na nagradu.
Mislim da bi jednom u DVE nedelje bilo sasvim dobro, jer:
- imace se dovoljno vremena za pronalazenje prigodnih zadataka.
- ako bude nedeljno, jos uvek ce trajati diskusija o prethodnom
a vec ce se zadavati novi.
- je dovoljno cesto.
Pozdrav, EMBE
algoritmi.163nenad,
-> #161, embe> manje mi se svidja ideja o pausalnom ocenjivanju vrednosti algoritma
> na osnovu brzine CELOG programa.
Ako se ne varam zadatak je uključivao i čitanje i pisanje
datoteke, kao i ispisivanje na konzolu. Jeste veći deo toga lakše
izvesti u C-u nego u ASM-u, jeste lakše i "čistije" uraditi posao
sa funkcijama nego sa jednom jedinom 'main' funkcijom i svim
globalnim promenljivama (da ne govorimo o definisanju klasa i
objektima), ali zato se mora platiti cena: startup kod,
inicijalizacije, pozivanje funkcija, stek - uz pretpostavku da je
kompajler savršen...
Cilj je bio najbrži program, biber je napravio najbrži
program. Napomenuo bih i da su prevodioci bili podešeni tako da
generišu 386 kod, dok je biber-ov program bio (ako se ne varam)
za XT. :)
Jedni se bune što može ASM, drugi što neće ubuduće moći... Kako
li bi tek naoštreni bili učesnici da je žiri rekao da je merio
tako što je modifikovao programe zarad merenja... :)
algoritmi.164deimos,
-> #156, galimpic Sva nova pravila su ok, osim jednog:
>>- Kriterijum za ocenjivanje je sledeci: uzimaju se u obzir samo potpuno
>> tacna resenja u okviru kojih pobeduje najkvalitetniji algoritam po
>> subjektivnom utisku organizatora - moje malenkosti. Ako postoji vise
>> slicnih resenja, pobednika odreduje brzina izvrsavanja. Nagrada za sada
Algoritam je bolji ako je brzi, zar ne ? Kriterijum ti je
diskutabilan. Uzmi na primer sledeci kriterijum:
Ucestvuje npr. 38 takmicara. Najbrzi algoritam dobija 38 poena,
drugi 37... i tako dalje. Na te poene ti dodaj svojih 38/4, 38/5 i 38/6
poena po subjektivnom misljenju. Krajnji zbir odlucuje pobednika.
Predlozio bih takodje i jednu malu konvenciju, kako bi se izbeglo
pri testu merenje 'nebitnog' dela koda (dakle, onoga koji nije u
direktnoj vezi sa algoritmom). Uz pomoc jednog malog C hedera koji sadrzi
precizan tajmer (1/18.2 sec) i koji se lako konvertuje u Pascal, a ciji
prototip prilazem uz poruku, program bi mogao da izgleda ovako:
void main(void)
{
...
StartTimer():
Algoritam()
StopTimer();
printf("Vreme izvrsenja: %d",ElapsedTime());
...
}
Eto, nemam vise zameki :) A sto se tice cesceg takmicenja, delim
misljenje embea da bi bilo najlepse da ide na svake dve nedelje.
.dEiMoS.
timer.halgoritmi.165galimpic,
-> #162, embe> Opet ce se meriti brzina ? Onda se potrudite da razlika izmedju prvog
> i poslednjeg bude veca od jedne milisekunde. :)) (naravno izborom
> zadatka)
Zahtev da se navede brzina je majušni problem za takmičara, a
velika pomoć za mene da ne lupam glavu da li se program zaglavio
ili treba da čekam XXX sekundi da se završi. To je u pitanju.
algoritmi.166galimpic,
-> #160, ognjen> Sta znaci najkvalititniji algoritam, po tvom misljenju,
> naravno? Najbrzi? Najelegantniji? Najcistiji?
Zavisi od problema. U principu, onaj koji ima najbolju mešavinu
elegancije, brzine, efikasnosti i ostalih parametara. Kao i
u književnoj kritici, na primer, ocena je subjektivna.
algoritmi.167biber,
-> #152, embe>> samog algoritma. Definisete ulazne podatke u samom programu,
>> pozovete algoritam 1000.... puta, (bez ulaza-izlaza) i razresite sve
>> dileme o efikasnosti algoritma. Intervenciju biste mogli sasvim lako
>> izvrsiti, za 3 minuta programerskog posla po programu. Tada biste
Hajde uradi to ako te ne mrzi, i okaci rezultate ovde.
Znatizeljan sam.
algoritmi.168galimpic,
************************************
TAKMIČENJE U PROGRAMIRANJU - 3. KOLO
************************************
Tačno u podne, u nedelju, 9. juna 1996. u temi "algoritmi" biće postavljen
nagradni zadatak. Rešenja se šalju isključivo kao mail korisniku "zadaci"
najkasnije do ponedeljka, 10. juna u ponoć (36 sati posle postavke).
Rešenje treba da bude u obliku izvornog i izvršnog koda koji su kao fajlovi
prikačeni uz mail poruku. U obzir dolaze samo BASIC, Pascal, C i C++.
Najbolji program, po mišljenju moderatora dobija prvu nagradu - mesec dana
gratis pretplate na SezamNet. Rezultati u utorak popodne.
Srećno!
algoritmi.169boko,
e jel zna neko opis TIF formata, i to nekompresovanog ?
cini mi se da ima heder od 200-tinak byte-ova, pa ide raw slika ?
algoritmi.170galimpic,
*******************************************
TAKMIČENJE U PROGRAMIRANJU - ZADATAK BROJ 3
*******************************************
Dat je crtež u ravni sastavljen od više tačaka povezanih pravim linijama.
Odrediti putanju kojom se crtež može nacrtati kontinuirano, bez prekida
u putanji i prelaženja više puta preko iste linije.
Ulaz je tekstualna datoteka ULAZ.TXT sledećeg sadržaja:
1. U prvom redu dat je ukupan broj tačaka - T (T>1)
2. U sledećih 2*T redova slede parovi X i Y koordinata svih tačaka redom
(X i Y su prirodni brojevi)
3. Sledi broj linija kojima su povezane tačke - L
4. U sledećih 2*L redova slede redni brojevi parova tačaka koje su povezane,
pri čemu su tačke numerisane po redosledu kojim su zadate
Pretpostavlja se da će postavka uvek biti pravilna: nema dve tačke sa istim
koordinatama, nijedna tačka ne ostaje izolovana niti se ijedna linija
ponavlja. Međutim, redosled zadavanja tačaka i linija ne mora biti ni na koji
način sortiran.
Izlaz je JEDNO rešenje u obliku tekstualne datoteke IZLAZ.TXT u kojoj je
navedena putanja po kojoj treba ići, u obliku rednih brojeva tačaka, svaka
u posebnom redu. U slučaju da rešenje ne postoji, umesto izlazne datoteke na
ekranu se izdaje obaveštenje o tome.
Rešenja slati kao mail korisniku "zadaci". najkasnije do 10.06. u 24h.
Uz poruku okačiti fajl sa izvornim i izvršnim kodom.
PRIMER KOMENTAR
------ --------
C:\>TYPE ULAZ.TXT
5 ;ima 5 tačaka
1 ;X1
1 ;Y1
3 ;X2
1 ;Y2 itd
3
4
1
2
2
2
6 ;ima 6 linija
1 ;1. linija spaja tacke 1...
2 ;...i 2
3 ;2. linija spaja tacke 3...
5 ;...i 5 itd
4
1
1
5 4| 3
2 | /
5 3| /
4 | /
5 2| 4---5
C:\>RESI.EXE | | / \
C:\>TYPE IZLAZ.TXT 1| 1-------2
3 |___________
5 1 2 3
2
1
5
4
1
C:\>_
algoritmi.171boko,
-> #169, bokoBO■>e jel zna neko opis TIF formata, i to nekompresovanog ?
BO■>cini mi se da ima heder od 200-tinak byte-ova, pa ide raw slika ?
e nadjeno...
\dos\info\tiff-50.zip :)
algoritmi.172biber,
-> #169, boko>> e jel zna neko opis TIF formata, i to nekompresovanog ?
Postoji opis i TIF i GIF formata u sezamovim direktorijumima.
algoritmi.173galimpic,
********************************************
REZULTATI 3. KOLA TAKMIČENJA U PROGRAMIRANJU
********************************************
Stigla su 4 rešenja, i to od korisnika mhrkic, deimos, embe i vinkom. Na
žalost, embe je odmah diskvalifikovan jer je poslao samo .CPP fajl, a od
.EXE ni traga.
Svi korisnici su ispravno ignorisali podatke o koordinatama tačaka. Ova
zamka je bila suviše providna za Sezamovce - položaj tačaka je, naravno,
potpuno nebitan za rešenje zadatka. Ipak, deimos se potrudio pa je i
te podatke iskoristio za opciju grafičkog prikaza.
Vinkom je bio teorijski najviše potkovan: rešenje je imenovao kao Eulerov
put koji postoji samo kada je broj tačaka sa neparnim brojem veza 0 ili 2.
Iskoristio je i ostala teorijska uputstva koja se tiču nalaženja rešenja,
pa je uspeo da ostavi najbolji utisak na žiri, tj. mene :). Dakle,
*** VINKOM je pobednik i dobija mesec dana pretplate ***
Ostalim učesnicima zahvaljujem na trudu i pozivam sve da učestvuju u narednom
kolu koje će se odigrati u nedelju, 23. juna. Ako mislite da je zadatak
bio previše lak, previše težak, dosadan ili imate kakav drugi razlog ili
želite da komentarišete rešenja, tema 'algoritmi' je otvorena.
resenja.zipalgoritmi.174embe,
-> #173, galimpic>>Stigla su 4 resenja, i to od korisnika mhrkic, deimos, embe i vinkom.
>>Na zalost, embe je odmah diskvalifikovan jer je poslao samo .CPP fajl, a
>>od .EXE ni traga.
To uopste nije dobar postupak prema meni, s obzirom da se pravila
menjaju iz nedelje u nedelju. Moj trud je omalovazen. Sta ce EXE ako
imate source. Sta ce source ako trazite EXE ? Ovo nije medjunarodno
takmicenje sa 1000 ucesnika. Ovo je takmicenje sa 4-5 ucesnika.
Ovakvim nelogicnim postupcima, umesto prijateljskim i kolegijalnim
pristupom nista se ne postize! Ajde da nisam poslao source, ali zato
sto nisam poslao EXE ???? JAKO sam ljut. Pa prema cemu se ocenjuje ??
Milan.
algoritmi.175galimpic,
-> #174, embe> Ovakvim nelogicnim postupcima, umesto prijateljskim i kolegijalnim
> pristupom nista se ne postize! Ajde da nisam poslao source, ali zato
> sto nisam poslao EXE ???? JAKO sam ljut. Pa prema cemu se ocenjuje ??
Pravila su bila jasna i niko se nije bunio kada su predlozena. Bez obzira,
ionako ne bi pobedio. To sto si diskvalifikovan ne znaci da nisam obratio
paznju na tvoj program.
algoritmi.176embe,
-> #175, galimpic>>Pravila su bila jasna i niko se nije bunio kada su predlozena. Bez
>>obzira,ionako ne bi pobedio. To sto si diskvalifikovan ne znaci da nisam
>>obratio paznju na tvoj program.
Uopste se ne bunim protiv pravila (sto bi neki rekli "zamenjuju se
teze"), bunim se protiv treniranja strogoce. Sta to znaci
diskvalifikovan? Zar nije moglo bez te kvalifikacije? Sto se tice
pobede, znao sam da necu da pobedim, s obzirom da sam znao da negde
postoji teoretsko objasnjenje ovog zadatka. Resio sam zadatak na
najbolji nacin sto sam u tom trenutku znao, ali sam ga ipak resio.
I sta znaci "ne znaci da nisam obratio paznju na tvoj program"?
Zasto si tu odstupio od pravila ? Zasto se uopste "obraca paznja" na
"diskvalifikovane" radove.
Vinkom-u cestitam, stvarno je resio problem na najbolji nacin,
i tu nema diskusije. Po mome misljenju, apsolutno najbolje resenje je
pobedilo, a interesantno mi je bilo to sto smo svi koristili razlicite
nacine. Zadatak je bio srednje tezine. Jedino mi je zao sto iz kola u
kolo ucestvuje isti (mali) broj ljudi. Hteo bih da znam, da li samo mi
resavamo ili resavaju i neki drugi ali ne mogu da rese? Pitam se,
pitam se?
Pozdrav, Milan.
algoritmi.177mango,
-> #174, embe> Ovakvim nelogicnim postupcima, umesto prijateljskim i kolegijalnim
> pristupom nista se ne postize! Ajde da nisam poslao source, ali zato
> sto nisam poslao EXE ???? JAKO sam ljut. Pa prema cemu se ocenjuje ??
Covek se opravdano ljuti. Zamisli kako je kad se mucis oko nekog
zadatka par sati i onda ti zbog ovakvog necijeg postupka (mo-deratovog)
ceo trud propadne. BTW, milane, stavljaj po red razmaka izmedju citata i
odgovora.
algoritmi.178dr.grba,
-> #177, mango>> Covek se opravdano ljuti. Zamisli kako je kad se mucis oko nekog
>> zadatka par sati i onda ti zbog ovakvog necijeg postupka (mo-deratovog)
Za mislite vi da se mučite oko nekog projekta par meseci, pa direktor
na kraju kaže "nije potrebno". E, kad to doživite, onda se upišite u
listu strelaca: ovo je "pioniri maleni" (:
algoritmi.179galimpic,
************************************
TAKMIČENJE U PROGRAMIRANJU - 4. KOLO
************************************
Tačno u podne, u nedelju, 23. juna 1996. u temi "algoritmi" biće postavljen
nagradni zadatak. Rešenja se šalju isključivo kao mail korisniku "zadaci"
najkasnije do ponedeljka, 24. juna u ponoć (36 sati posle postavke).
Rešenje treba da bude u obliku izvornog i izvršnog koda koji su kao fajlovi
prikačeni uz mail poruku. U obzir dolaze samo BASIC, Pascal, C i C++.
Najbolji program, po mišljenju moderatora dobija prvu nagradu - mesec dana
gratis pretplate na SezamNet. Rezultati u utorak popodne.
Srećno!
algoritmi.180galimpic,
*******************************************
TAKMIČENJE U PROGRAMIRANJU - ZADATAK BROJ 4
*******************************************
Ulaznom datotekom ULAZ.TXT zadat je lavirint veličine 19*19 polja. Svako polje
predstavljeno je simbolom ' ' (blanko) što predstavlja prolaz ili '*'
(zvezdica) koja označava zid. Prolazi su uvek debljine 1, a sva ivična polja
lavirinta su zidovi, osim levog polja gornjeg zida (drugog znaka u datoteci)
i desnog polja donjeg zida (predzadnji znak u datoteci, ne računajući oznaku
novog reda).
Odrediti bar jednu putanju kojom se može, pošavši od gornjeg levog ulaza
doći do izlaska iz lavirinta na suprotnoj strani. Putanja treba da bude
data kao redosled pravaca sveta (N, S, E ili W) kojima treba ići do prve
raskrsnice ili zida. Na svakom mestu prateći trenutni pravac gde se može
skrenuti i drugim pravcima ili udara u zid, potrebno je dati novu oznaku
pravca. Početni podrazumevajući pravac na jug ne treba navoditi.
Izlaz je JEDNO od rešenja u obliku tekstualne datoteke IZLAZ.TXT u kojoj je
navedena putanja po kojoj treba ići u jednom redu. U slučaju da rešenje ne
postoji, umesto izlazne datoteke na ekranu se izdaje obaveštenje o tome.
Rešenja slati kao mail korisniku "zadaci". najkasnije do 24.06. u 24h.
Uz poruku okačiti fajl sa izvornim i izvršnim kodom.
PRIMER (u postavku je ucrtana i putanja sa potezima radi jasnoće rešenja)
------
C:\>TYPE ULAZ.TXT
*|*****************
*S * * *
*|********* ***** *
*E---S* * * * *
*****|* *** *** * *
* *S * ** * *
*S---W** *
*|*** * * * **** *
*|* * **** * ** * *
*|* * * ** * *
*|* ******** ** * *
*E----S* *
******|* * * ** * *
* S-WW* * * ** * *
* *|* ********* * *
* *|* * *
* *|****** ****** *
* *E------E------S*
*****************|*
C:\>RESI.EXE
C:\>TYPE IZLAZ.TXT
SESSWSESWWSEES
C:\>_
algoritmi.181galimpic,
********************************************
REZULTATI 4. KOLA TAKMIČENJA U PROGRAMIRANJU
********************************************
Ovaj put su stigla tri rešenja, i to od korisnika embe, obren i vinkom.
Najlepše rešenje (po meni) ponudio je obren koji dobija mesec dana gratis
pretplate. Izvorni kod sva tri rešenja nalazi se u datoteci uz ovu poruku.
Pošto je već postalo simptomatično da samo nekoliko istih korisnika iz kola
u kolo učestvuje na takmičenju, moraću da najavim njegovo gašenje u slučaju
da se nešto ne promeni sledećeg puta. Zadatak će biti lakši, pa pozivam sve
Sezamovce da šalju rešenja. Vidimo se za 2 nedelje!
res4.zipalgoritmi.182obren,
-> #181, galimpic> Ovaj put su stigla tri rešenja, i to od korisnika embe, obren i
> vinkom. Najlepše rešenje (po meni) ponudio je obren koji dobija
> mesec dana gratis pretplate.
Rešenje je bazirano na rekurzivnom probijanju kroz "hodnike" u sva
četiri moguća smera. Znači krene se od ulaza na jug, i proba se prolaz
na onu stranu sveta na kojoj nema zida. U slučaju da se udara u zid,
ili put može da se grana (testira se brojanjem polja bez zida oko
trenutne pozicije) pamti se marker (S-W-E-N) kao naznaka daljeg smera.
Da kažem još da sam se dvoumio između ovog rešenja i štosa sa držanjem
uz levi (desni) zid. Ipak, učinilo mi se da je ovo rešenje elegantnije
i primereno dimenziji problema.
> Pošto je već postalo simptomatično da samo nekoliko istih korisnika
> iz kola u kolo učestvuje na takmičenju, moraću da najavim njegovo
> gašenje u slučaju da se nešto ne promeni sledećeg puta. Zadatak će
> biti lakši, pa pozivam sve Sezamovce da šalju rešenja. Vidimo se za
> 2 nedelje!
Ne znam šta je razlog za mali broj učesnika, najverovatnije ispitni
rokovi, kraj školske godine, prijemni i sl. Zadaci su u zadnja dva kola
bili po mom mišljenju prilično zanimljivi za rešavanje (za razliku od
Hanojskih kula). Šteta bi bilo da se gasi... Što se tiče težine, možda
treba da postoje dve-tri kategorije zadataka? Treba dati šansu i nekim
mlađim učesnicima, za koje su možda ovi zadaci preteški...
Kao mali podstrek nastavku takmičenja, poklanjam svojih mesec dana u
fond nagrada za sledeće kolo. Znači ili neka pobednik dobije 2 meseca,
ili dva najbolja rešenja po mesec dana, svejedno.
algoritmi.183mango,
-> #181, galimpic> Ovaj put su stigla tri resenja, i to od korisnika embe, obren i vinkom.
Pa naravno da su stigla 3 resenja kad si iskljucio biber-a. Inace bi
stigla cak cetiri;)
algoritmi.184hercog,
Ima li ko algoritam ili source nekog programa za pretraživanje
težinskog grafa?
Sale
algoritmi.185pedjak,
-> #184, hercog> Ima li ko algoritam ili source nekog programa za pretraživanje
> težinskog grafa?
Šta ti konkretno treba, mininalna dužina puta...?
algoritmi.186mbasta,
-> #182, obren=> Hanojskih kula). Steta bi bilo da se gasi... Sto se tice tezine, mozda
=> treba da postoje dve-tri kategorije zadataka? Treba dati sansu i nekim
=> mladim ucesnicima, za koje su mozda ovi zadaci preteski...
I ja se slazem da ima vise kategorija zadataka (neznam bas puno o
programiranju, ali brzo ucim).
=> Kao mali podstrek nastavku takmicenja, poklanjam svojih mesec dana u
=> fond nagrada za sledece kolo. Znaci ili neka pobednik dobije 2 meseca,
=> ili dva najbolja resenja po mesec dana, svejedno.
Svaka ti cast za poklon. :) To se ceni!
P.S. Predlozio bih da se takmicenje cesce odrzava (sa laksim zadacima
naravno),a nagrade i nisu tako vazne (10 din. manje-vise).
Pozdrav, Mbasta.
algoritmi.187sasab,
-> #181, galimpic> Pošto je već postalo simptomatično da samo nekoliko istih
> korisnika iz kola u kolo učestvuje na takmičenju, moraću da
> najavim njegovo gašenje u slučaju
Pa "gašenje" baš ne mora, ali mogla bi da se otvori nova tema.
Ovako je pad opterećen iako me takmičenje ne zanima (nema se
vremena a i sa godinama takmičarski duh opada:). Moglo bi posle
završetka "kola" postavka zadatka, pobednik i uz poruku datoteka
sa rešenjima u temu algoritmi (nikad ne znaš šta će zatrebati,
a topla voda je otkrivena već n! puta), ali sve ostalo (diskusije
o težini zadatka, prigovori, čestitke pobedniku i sl.) u drugu
temu.
Bogi
algoritmi.188mango,
-> #182, obren> Resenje je bazirano na rekurzivnom probijanju kroz "hodnike" u sva
> cetiri moguca smera. Znaci krene se od ulaza na jug, i proba se prolaz
Zar je bilo moguce zadatak uraditi i na neki drugi nacin?
algoritmi.189hercog,
-> #185, pedjak@> Šta ti konkretno treba, mininalna dužina puta...?
Može i to, može i vreme (ako se zna brzina)...
Sale
algoritmi.190obren,
-> #188, mango> Zar je bilo moguce zadatak uraditi i na neki drugi nacin?
Kao što sam (doduše šturo) napomenuo, moguće je i držati se "slepo"
jedne strane zida, pa ga pratiti ma gde on skrenuo. Evo, malo sam
grafički dočarao kako bi izlgledalo kretanje na ovaj način...
ulaz
:
████ │ ██████████████
██ ┌─┘ ██
██ │ ████
██ └─>─┐ ██
██████ │ ██
██ ┌───┘
██ │┌──>───┐
██ ││ ████ │
██ └┘ ██ ┌─┘
████████ :
Posle konačno mnogo ;) tumaranja sigurno dolaziš do izlaza. Probaj
recimo na onom lavirintu koji je galimpic dao kao primer, ali pre toga
uradi search & replace '*' sa '█' da bi se lakše snašao. Međutim, ima
jedno ali:
Iako sigurno izlaziš napolje, dobijaju se vrlo "tupave" putanje, (prođeš
istim pravcem u dva smera jer si okrenuo u nekom ćorsokaku) pa treba
filtrirati koordinate putanje da bi izlaz bio u traženom formatu. Zato
je rekurzivno rešenje znatno lepše i primerenije ovom konkretnom
problemu.
algoritmi.191maksa,
-> #188, mango>> Zar je bilo moguce zadatak uraditi i na neki drugi nacin?
Na razne. Na pr. preko matrice susednosti grafa (Dijkstra,
Warshall), zatim na način opisan u knjizi Diskretna Matematika,
Dragoša Cvetkovića, i sl. Prolaznost i najkraći put kroz graf
(na šta se svodi problem sa lavirintom, koji se u matematici
zove planarni digraf) je dosta obrađivan. Za neke moje potrebe
imam implementirano rešenje iz pomenute knjige, al' sam kasno
video zadatak i nisam stigao da ga isčupam iz objekata i
"prepevam".
Primedbica: nije OK što ste izbacili asm iz takmičenja, čime
ste automatski isključili korisnika 'biber'. Ako čovek stvarno
sve svoje piše u asembleru onako brzo i efikasno, onda ga treba
čuvati kao nacionalno bogatstvo. :)
algoritmi.192embe,
-> #181, galimpic>> Posto je vec postalo simptomaticno da samo nekoliko istih korisnika
>> iz kola u kolo ucestvuje na takmicenju, moracu da najavim njegovo
>> gasenje u slucaju da se nesto ne promeni sledeceg puta. Zadatak ce
>> biti laksi, pa pozivam sve Sezamovce da salju resenja. Vidimo se za
>> 2 nedelje!
I meni je jako zao sto su sada pristigla samo tri resenja. Mozda
bi se moglo pametovati o uzrocima ovako slabog odziva, ali situacija
je bila takva od samog pocetka. Naime broj ucesnika je bio ako se
ne varam: 1.kolo(X-Oks) - 4 , 2.kolo(vanredno-domine) - 5, 3.kolo
(Hanojske kule)- 1 (super brzi vinkom), 4.kolo(linije)-4 i
5.kolo(lavirint)- 3.
Pametovati se moze samo o sudbini takmicenja. Prvo, smatram da nije
dobro da se takmicenje ugasi. Drugo, mislim da je potrebno formirati
novu temu "takmicenje" u ovoj konferenciji. Trece, potrebno je
iz temelja rekonstruisati pravila takmicenja (vec smo ih menjali,
ali tim koji NE dobija...). Promene se nece desiti same od sebe.
Po mom misljenju:
- izmene se ne bi odnosile samo na kriterijum ocenjivanja radova,
jer smatram da uprkos nedostacima subjektivne procene radova,
ipak je to najobjektivniji nacin za vrednovanje. Do sada nije bilo
nikakvih primedbi na rad moderatora po tom pitanju, pa smatram da
ovo treba da ostane.
- treba promeniti sistem takmicenja, tako da se, recimo jednom
mesecno objave zadaci (vise zadataka odjednom - npr. 5-6) razlicitih
tezina, i za svaki zadatak u skladu sa njegovom tezinom, koeficijenti
bodovanja. Posle dve nedelje, zadaci bi se pregledali, moderator bi
svakom resenju dodeljivao bodove (0 - 5), mnozio sa koeficijentom
tezine, i dobijao bi se zbirni rezultat za svakog takmicara. Sustina
ovoga je pravljenje lige programera, koje bi trajalo recimo tri
ili cetiri meseca. Posle svakog mesecnog tamicenja proglasavao bi se
pobednik ("nosilac zute majice"), a nagrade bi mu bile: moralne
prirode - pohvala i ucestvovanje u pripremi i pregledanju sledeceg
kompleta zadataka (naravno zajedno sa moderatorom) i simbolicno
"materijalne" prirode - pretplata. Naravno on ne bi ucestvovao u
takmicenju kada zadaje zadatke. Liga bi isla dalje, pri cemu, da
pobednici pojedinih takmicenja ne bi bili hendikepirani, osnovni
kriterijum za plasman bio bi kolicnik ukupnih poena i broja
odrzanih "utakmica" kojima je prisustvovao.
Ukupni pobednik je onaj ko je ucestvovao na pola ili vise
takmicenja a ima najbolji gorepomenuti kolicnik.
Na kraju, ne mogu da odolim, moram da dam jednu digresiju. Za vreme
od 36 casova, u vote za vic meseca, glasa 3-6 ljudi. Za 15 dana,
javi se 30-60 ljudi. A mnogo je lakse glasati za vic meseca nego
resavati zadatak. Znaci, nerealno je ocekivati da ce u takmicenu
ucestvovati vise od 3-6 ljudi ma kako laki zadaci bili. Resenje
je u produzenju roka za slanje resenja. To je jasno.
Nadam se da ovde postoje ljudi kojima je stalo do nastavljanja
takmicenja u programiranju. Meni je stalo.
Izvinjavam se zbog opsirnosti.
Pozdrav, Milan.
algoritmi.194embe,
-> #181, galimpic>> Ovaj put su stigla tri resenja, i to od korisnika embe, obren i
>> vinkom. Najlepse resenje (po meni) ponudio je obren koji dobija
>> mesec dana gratis pretplate.
Obrenu cestitam, moj algoritam je bio slican njegovom pa mi se zato
svidja kako razmislja :))))) (sala mala)
Svaka cast Obrenu i za onaj lepi gest sa svojom nagradom.
Pozdravljam i starog rivala vinkom-a koji je opet bio na nivou.
A sada nesto o samom zadatku. Ne znam da li je to bilo namerno ali
zadatak je bio skoro POTPUNO isti kao prethodni (linije). Da li je to
previd ili...
Naime, sa slicnom organizacijom podataka (koja je ipak najvazniji
deo svakog algoritma) mogao se resiti i jedan i drugi zadatak, a cilj
je bio nesto modifikovan ali nedovoljno razlicit. Kod linija, svaki
cvor je mogao da ima N veza sa drugim cvorovima, a ovde maksimalno 4,
kod linija se moralo proci kroz sve cvorove a ovde, od vec zadatog cvora,
do zadatog cvora. Znaci, razlike su samo u kriterijumu zavrsetka
i u tome sto je broj veza u drugom zadatku bio fiksiran.
Ne znam sta misle ostali, ali potenciranje na _igri_zasnovanim_ zadacima
moze da dovede do monotonosti.
Pozdrav, Milan.
algoritmi.195mbasta,
-> #192, embe=> odrzanih "utakmica" kojima je prisustvovao.
=> Ukupni pobednik je onaj ko je ucestvovao na pola ili vise
=> takmicenja a ima najbolji gorepomenuti kolicnik.
Potpuno se slazem sa tobom.
=> Izvinjavam se zbog opsirnosti.
Nemas zasto. Sve sto si napisao je vredno potrosenog vremena.
Pozdrav, Mbasta.
algoritmi.196cozymc,
-> #181, galimpicNikakvo gasenje takmicenja ne dolazi u obzir, u toku je ispitni rok(ovi).
Imam resenje, ali nisam stigao da ga posaljem jer se po Marfiju necete
ulogovati pet minuta pre 12!
algoritmi.197biber,
-> #192, embe>> pobednik ("nosilac zute majice"), a nagrade bi mu bile: moralne
>> prirode - pohvala i ucestvovanje u pripremi i pregledanju sledeceg
Pre bih rekao da u ovom grmu lezi zec. Naime kad bi nagrade
bile jace verujem da bi daleko vise ljudi ucestvovalo. Ipak tesko
da tako nesto moze Sezam da uradi samostalno. Dakle ne bi bilo
lose da u takmicenje umesa prste neki sponzor. I to neko ko bi imao
neke koristi od toga. Npr neka firma koja se bavi izradom programa.
Mozda bi joj se isplatilo da prati takmicenje i primi nekog mladog
i kvalitetnog programera pod svoje okrilje.
Koliko vidim na internetu (prateci 3d animaciju) cesto firme
same organizuju takmicenje u animaciji, uz velike nagrade. To naravno
ne rade iz nakih altruistickih pobude, vec da bi otkrila potencijalne
saradnike...
algoritmi.198biber,
-> #194, embe>> zadatak je bio skoro POTPUNO isti kao prethodni (linije). Da li je to
A kad malo razmislis slican je i sa "dominama". Na kraju krajeva sva
racunarska tabacenja sa svode na rekurziju.
>> Ne znam sta misle ostali, ali potenciranje na _igri_zasnovanim_ zadacima
>> moze da dovede do monotonosti.
Vidis meni mi bili interesantni zadaci kao sto je bilo jedno pitanje
postavljeno valjda u ovoj temi. Neko je pitao za algoritam sencenja
trougla, pod uslovom da se zna intenzitet osvetljenja temena.
(ovo pisem po secanju, mozda gresim, ali kao zadatak mi deluje
zanimnjivo)
algoritmi.199dr.s,
-> #191, maksa/* ste automatski iskljucili korisnika 'biber'. Ako covek stvarno
/* sve svoje pise u asembleru onako brzo i efikasno, onda ga treba
/* cuvati kao nacionalno bogatstvo. :)
Raritet, bre!
Mada znam jos neke 'asemblerase' kojima bas i nije do takmicenja. :)
(ogradjujem se od necije pomisli da sam ja taj; nisam! O:))
algoritmi.200hercog,
-> #184, hercog
@> Ima li ko algoritam ili source nekog programa za pretraživanje
@> težinskog grafa?
@>
@> Sale
algoritmi.201embe,
-> #197, biberJa>>> pobednik ("nosilac zute majice"), a nagrade bi mu bile: moralne
Ja>>> prirode - pohvala i ucestvovanje u pripremi i pregledanju sledeceg
Ti> Pre bih rekao da u ovom grmu lezi zec. Naime kad bi nagrade
Ti> bile jace verujem da bi daleko vise ljudi ucestvovalo.
E, ja stvarno ne mislim da je osnovni razlog malog odziva - mala nagrada.
Mislim da su "zec i grm" u tome sto takmicenje nije dovoljno atraktivno i
sto je rok za slanje resenja kratak. Na kraju krajeva, programeri su
toliko sujetni i ljubomorni na svoje znanje (u pozitivnom smislu), i
zeljni dokazivanja, a u praksi imaju malo prilika za dokazivanje, da
jedva cekaju da se dokazu i dobiju priznanje za svoje umece. Materijalna
satisfakcija je sasvim nebitna u procesu dokazivanja. Naravno potrebno
ih je zainteresovati lepim i razlicitim zadacima. Takodje, ako je rok
za slanje dovoljno dug, imace vremena da daju najbolje od sebe i s
pravom se nadaju da ce biti uspesni takmicari.
Da sam bar delimicno u pravu, govori i cinjenica da si i Ti ucestvovao
u takmicenjima, sto znaci da nisi bio animiran nagradom, vec si takmicenje
shvatio kao izazov. Ne mislim da ovde postoji i jedan "teski profesionalac"
koji zbog niskih nagrada ne zeli da ucestvuje. S obzirom da na drugim
mestima nema takmicenja na kojima bi se dokazali, oni ostaju anonimni,
sto je suprotno programerskom duhu.
Pozdrav, Milan.
algoritmi.202pedjak,
-> #189, hercog> Ž> Šta ti konkretno treba, mininalna dužina puta...?
> Može i to, može i vreme (ako se zna brzina)...
Ovako, algoritam zvani Minimal, daje minimalnu dužinu puta između dva
čvora u grafu.
Na osnovu poznate strukture grafa formira se njemu odgovarajuća
matrica susednosti, vrednost elementa na poziciji (i,j) je u stvari
težina grane između čvora i i j. Matrica susednosti koja se ovde
koristi se dodatno modifikuje, tako što se svi elementi čija bi
vrednost trebala da bude nula (čvorovi nisu povezani), zamenjuje
nekom velikom vrednošću, teorijski sa beskonačno. Na tako dobijenu
matricu primeni se sledeći algoritam:
for i = 1 to n
for j = 1 to n
for k = 1 to n
C(i,j) = min (C(i,j), C(i,k)+C(k,j))
endfor
endfor
endfor
gde je C matrica susednosti, n broj čvorova, a funkcija min vraća
manju vrednost od dve.
Kao rezultat u matrici C na poziciji (i,j) se pojavljuje minimalna
dužina puta između čvorova i i j, ili beskonačno (tj. ono što smo
proglasili beskonačnim) , ako čvorovi nisu povezani.
Ovaj metod _ne daje_ listu čvorova koji se nalaze na minimalnom
putu. Ovako nešto daje Dijkstra algoritam. Ako ti ovo gore ne radi
posao, objasnićemo i ovo :)
pedja
algoritmi.203hercog,
-> #202, pedjak@> Ovaj metod _ne daje_ listu čvorova koji se nalaze na minimalnom
@> putu. Ovako nešto daje Dijkstra algoritam. Ako ti ovo gore ne radi
@> posao, objasnićemo i ovo :)
Trebala bi mi i lista čvorova na minimalnom putu...
Sale
algoritmi.204biber,
-> #201, embe>> shvatio kao izazov. Ne mislim da ovde postoji i jedan "teski
>> profesionalac" koji zbog niskih nagrada ne zeli da ucestvuje.
Pa sad da li kod nas uopste ima profesionalaca u racunarskim
poslovima... Svi pomalo rade prelom, dizajniraju u korelu, crtaju
u autokedu, programiraju u kliperu...
E sad zamisli tako nekoga koga ceka neki projekt koji na kraju
krajeva donosi neki novac, a on treba da se zabavlja sa zadacima?
Ne shvati pogresno, lepo je ucestvovati. Ali kad bi nagrada
bila odgovarajuca zaradi na nekom od gore pobrojanih poslica
(a to nije mnogo), vise ljudi bi imalo motiva da ucestvuje u
takmicenju.
algoritmi.205spantic,
-> #204, biber> Pa sad da li kod nas uopste ima profesionalaca u racunarskim
> poslovima... Svi pomalo rade prelom, dizajniraju u korelu, crtaju
> u autokedu, programiraju u kliperu...
Veruj da ima. Pogotovo nemaš stavku crtaju pomalo u AutoCad-u.
Na prvi pogled se razlikuje rad profesionalca i amatera, pogotovo
svaštara.
algoritmi.206galimpic,
************************************
TAKMIČENJE U PROGRAMIRANJU - 5. KOLO
************************************
Tačno u podne, u nedelju, 7. jula 1996. u temi "algoritmi" biće postavljen
nagradni zadatak. Rešenja se šalju isključivo kao mail korisniku "zadaci"
najkasnije do ponedeljka, 8. jula u ponoć (36 sati posle postavke).
Rešenje treba da bude u obliku izvornog i izvršnog koda koji su kao fajlovi
prikačeni uz mail poruku. U obzir dolaze samo BASIC, Pascal, C i C++.
Najbolji program, po mišljenju moderatora dobija prvu nagradu - mesec dana
gratis pretplate na SezamNet. Rezultati u utorak popodne.
Srećno!