PCPROG.6

25 Sep 1995 - 24 Dec 1999

Topics

  1. algoritmi (449)
  2. baze.podataka (309)
  3. ms.dos (17)
  4. windows (294)
  5. asembler (553)
  6. basic (458)
  7. jezici (42)
  8. pascal (1297)
  9. cccc (522)
  10. cpp (299)
  11. clipper (601)
  12. fox (70)
  13. cavo (14)
  14. delphi (1130)
  15. java (100)
  16. razno (776)
  17. unknown (127)

Messages - algoritmi

algoritmi.207 omega,
Iz tehnickih razloga Goran Alimpic nije u mogucnosti da se javi na Sezam. Zadatak iz takmicenja u programiranju ce ostaviti do 20 casova.
algoritmi.208 galimpic,
******************************************* TAKMICENJE U PROGRAMIRANJU - ZADATAK BROJ 5 ******************************************* Sa tastature se unosi pozitivan ceo broj manji od 100. Potrebno je pronaci sve razlicite nacine na koje se taj broj moze prikazati kao zbir drugih prirodnih brojeva. Rezultat se upisuje u datoteku IZLAZ.TXT tako da svaki red predstavlja po jedan zbir, a sabirci se razdvajaju znakom '+'. U zadnjem redu datoteke treba navesti ukupan broj razlicitih kombinacija. PRIMER: C:\>RESENJE.EXE Unesi broj: 4 C:\>TYPE IZLAZ.TXT 1+1+1+1 1+1+2 1+2+1 2+1+1 1+3 3+1 2+2 4 8 C:\_
algoritmi.210 galimpic,
********************************************** TAKMIČENJE U PROGRAMIRANJU - REZULTATI 5. KOLA ********************************************** Zadatak je bio namerno lak: nadao sam se da ću time privući više takmičara. Kako je pristiglo samo dva rešenja (korisnici bokir i vinkom, embe je pre isteka roka izbrisao svoj prilog), takmičenje se ukida do daljnjeg. Pobednik ovog kola je VINKOM. res5.txt
algoritmi.211 hercog, -> #200, hercog
»» Ima li ko algoritam ili source nekog programa za pretraživanje »» težinskog grafa? Sale
algoritmi.212 pedjak, -> #211, hercog
> Ima li ko algoritam ili source nekog programa za pretraživanje > težinskog grafa? Deder, potseti me, ovo je bilo pre mesec dana... Čini mi se da sam ti dao alogoritam Minimal, možda ti treba nešto drugo..?
algoritmi.213 hercog, -> #212, pedjak
»» Deder, potseti me, ovo je bilo pre mesec dana... Čini mi se da sam »» ti dao alogoritam Minimal, možda ti treba nešto drugo..? Pa ja rekoh da mi treba algoritam koji em što nalazi najoptima- lniju granu u nekom grafu između dva čvora nego i pamti kojim čvorovima treba proći... Sale
algoritmi.214 dr.grba, -> #213, hercog
>> Pa ja rekoh da mi treba algoritam koji em što nalazi najoptima- >> lniju granu ... Književniče, ne postoji NAJOPTIMALNIJE. Ili je optimalno ili nije.
algoritmi.215 vitez.koja, -> #214, dr.grba
#=>>> Pa ja rekoh da mi treba algoritam koji em što nalazi najoptima- #=>>> lniju granu ... #=> Književniče, ne postoji NAJOPTIMALNIJE. Ili je optimalno ili nije. Nemoj tako oštro, evo i stari latini su znali za pojam Optimus Maksimus, milim da je prevod na naš jezik jasan (treba li i reference da navodim ;)? sk
algoritmi.216 tehnikum,
Ima li nekog ko zna kako se rachnaju koeficijenti za matematichki model 2-pole filtera ili nekog multi-pole filter (vishe od 2 "poluge") ??? Byte Pointer Of Distorsion
algoritmi.217 nlazic,
Da li neko nešto zna o algoritmu za raspoređivanje ravanskih figura na datu površinu, tako da procenat iskorišćenja površine bude maksimalan (optimizacija rasporeda figura na pravougaonoj osnovi)?
algoritmi.218 sasab,
Zna li neko kako se formira matični broj građana? Ide datum rođenja pa dalje ... Bogi
algoritmi.219 dr.grba, -> #218, sasab
>> Zna li neko kako se formira matični broj građana? Ide datum rođenja >> pa dalje ... Pa tri cifre za šifru opštine rođenja, pa 0 za muške, 1 za ženske, pa cifra za redni broj rođenog tog dana, pa kontrolna cifra po tamo nekom modulu... Ili će biti dve cifre za šifru opštine, a dve za redni broj.... Ne sećam se više, a imao sam (i izgubio ): ) ovu šemu.
algoritmi.220 isekulovic, -> #219, dr.grba
>> Pa tri cifre za sifru opstine rodenja, pa 0 za muske, 1 za zenske, pa Dve za opstinu, 0 za muske 5 (!) za zenske, dve cifre redni broj i jedna kontrolna cifra.
algoritmi.221 dr.grba, -> #220, isekulovic
>> Dve za opstinu, 0 za muske 5 (!) za zenske, dve cifre redni broj i >> jedna kontrolna cifra. E, tako, tnx. Hajde sad da nas neko priseti načina izvođenja kontrolnog broja.
algoritmi.222 firus, -> #218, sasab
> Zna li neko kako se formira maticni broj gradana? Ide datum > rodenja pa dalje ... Jedinstveni maticni broj gradjana (JMBG) je trinaestocifreni broj sacinjen po sledecoj semi: DDMMGGGXXBBBC gde su: DD - datum rodjenja MM - mesec rodjenja GGG - godina rodjenja (bez cifre 1 za hiljadu) XX - ovo je oznaka za administrativn/upravnu oblast (ono 7 je za Srbiju, za ostale, sada bivse republike, ne znam podatke) BBB - 000-499 - muska osoba 500-999 - zenska osoba (ovo je uzeto na osnovu statistickog proseka da se u Beogradu, koji ima najveci broj rodjenih tokom dana, dnevno ne moze roditi vise od 500 dece istog pola) C - kontrolna cifra koja se proracunava po sledecem algoritmu (Pascal, nadam se da je svima jasno): var JMBG:string[13]; i,j,result:word; begin readln(JMBG); result:=0; j:=1; for i:=7 downto 2 do begin result:=result+(ord(JMBG[j])-48)*i; result:=result+(ord(JMBG[j+6])-48)*i; j:=j+1 end; result:=11-(result mod 11); if result>=10 then result:=0; if (result=ord(JMBG[13]-48)) then writeln ('Kontrolna cifra je u redu ... ',result) else writeln ('Kontrolna cifra je neispravna ...', result) end. Recimo, u mom slucaju JMBG je 1905974762613 jer sam rodjen 19.05.1974. u Pozarevcu, opstina Pozarevac, Republika Srbija, i upisan sam pod brojem 261 u neku knjigu (nema pojma koju, valjda je maticna knjiga rodjenih u pitanju) ...
algoritmi.223 mdimitrijevic,
Ovo je jedan od najkompletnijih tutorial-a o texture mappingu koji sam video. Potrebno je određeno predznanje. Obuhvaćen je teorijski, C (Watcom C) i ASM pristup. Većinom 32-bitni kod i za one koji nisu previse upoznati moze predstavljati problem. Uz malo probe, sa dobrim texture mapping rutinama mogu se uraditi i environement mapping (ogledanje okoline na objektu), phong sencenje ... fatmap.zip
algoritmi.224 centrotextil, -> #217, nlazic
Potreban algoritam, isti kao sto trazi nlazic: Algoritam bi trebao da optimizuje raspored narucenih elemenata za secenje (pravougaoni komadi proizvoljnih dimenzija, u proizvoljnom broju primeraka) iz table materijala standardne velicine, a sve sa ciljem minimizacije "restlova" (neiskoriscenih povrsina). Kako nemam nikakvu ideju o algoritmu, svaki pointer je dobrodosao hvala pozdrav branko
algoritmi.225 isekulovic, -> #224, centrotextil
>> Kako nemam nikakvu ideju o algoritmu, svaki pointer je dobrodosao Prevrni stare pc.prog konferencije (lakse reci nego uraditi, ali sta je tu je). Bilo je price o algoritmima za optimalno pakovanje fajlova na diskete, odnosno pesama na kasete. Mislim cak da je pominjan i tvoj problem kao primer 2D ekvivalenta gore navedenih problema.
algoritmi.226 hercog,
Neko je pominjao da negde u starim PCPROG konferencijama ima algoritam za određivanje optimalnog rasporeda snimanja pesama na kasetu. Bih bi veoma zahvalan kad bi mi neko ukazao na lokaciju na kojoj se taj algoritam nalazi... Sale
algoritmi.227 nenad, -> #226, hercog
> Neko je pominjao da negde u starim PCPROG konferencijama ima > algoritam za određivanje optimalnog rasporeda snimanja pesama na > kasetu. Bih bi veoma zahvalan kad bi mi neko ukazao na lokaciju na > kojoj se taj algoritam nalazi... Ne znam gde se nalazi i ima li ga uopšte, ali algoritam je prilično jednostavan. Sortiraj pesme po dužini i kreni od najduže redom da ih snimaš. Kada pred kraj ne budeš mogao neku da snimiš probaš onu "ispod" nje. pa opet, pa opet... Za sledeću kasetu/stranu uzmeš one što su ostale, takođe od najveće ka najmanjoj. Algoritam nije idealan i savršen, ali u gotovo svim "realnim" situacijama daje zadovoljavajuće rezultate.
algoritmi.228 nenad,
Nova datoteka: dos\comm\*.* ------------------ pgp263is.zip 645k ű Izvorni kod programa PGP v2.6.3i (internacionalna verz.) U pitanju je sors internacionalne verzije PGP-a (one koja koristi nelicencirani, brži RSA algoritam). Ovu verziju zabranjeno je koristiti u USA.
algoritmi.229 zkis,
HELP: Problem je prakticne prirode. Resavam problem iz termickih proracuna gde ima puno tabela sa empirijskim podacima. Tabele su trodimenzionalne, tj za ulazne vrednosti X i Y dobija se trazena vrednost Z. Na primer jedna (mala) tabela izgleda ovako: \ y 10 12.5 15 17.50 x\_____________________________ 5 | 0.05 0.06 0.14 0.21 10| 0.07 0.09 0.13 0.17 15| 0.09 0.10 0.16 0.19 Dakle tabela ne mora imati isti broj redova i kolona ! Na primer za ulaznu vrednost X=10 i Y=12.5 dobijam rezultat Z=0.09 Na na koji nacin da dobijem matematicku jednacinu aproksimativne povrsi tipa Z=F(X,Y) koja sa dovoljno tacnosti prikazuje ovaku tabelu ??? Napominjem da je ovaj primer ovde zbog konciznosti isecen iz sadrzaja, tabele su inace mnogo vece i ima ih dosta. Probao sam Excel, MicroCal Origin, MatLab u kome se bas i nisam snasao. Potreban je univerzalni matematicki princip resavanja ovakvih problema. Ocajnik sa Banovog Brda.
algoritmi.230 vasic, -> #229, zkis
> \ y 10 12.5 15 17.50 > x\_____________________________ > 5 | 0.05 0.06 0.14 0.21 > 10| 0.07 0.09 0.13 0.17 > 15| 0.09 0.10 0.16 0.19 > > Na na koji nacin da dobijem matematicku jednacinu aproksimativne > povrsi tipa Z=F(X,Y) koja sa dovoljno tacnosti prikazuje ovaku tabelu > ??? Priznajem da ovo nisam nikad radio, ali mi jedno pade na pamet: Mogao bi da pokušaš da ideju Lagranžove interpolacije proširiš sa funkcije jedne na funkciju dve promenljive. Elem, u Lagranžovoj interpolaciji za funkciju jedne prom. kada imaš k+1 par (x[i], y[i]) ti pretpostaviš da ti je funkcija oblika k k-1 k-2 y(x) = A x + A x + A x + ... + A x + A 0 1 2 k-1 k Kada u ovu jednačinu uvrstiš k+1 parova poznatih vrednosti (x[i], y[i]) dobijaš sistem od k+1 jednačine sa k+1 nepoznatih: A[0], A[1], ... A[k] a to su koeficijenti pretpostavljene interpolacione funkcije. U tvom slučaju imaš (m+1)*(n+1) trojki (x[i,j], y[i,j], z[i,j]). Možeš da pretpostaviš da ti je funkcija oblika m n m n-1 m n-2 m z(x,y) = A x y + A x y + A x y + ... + A x + 00 01 02 0n m-1 n m-1 n-1 m-1 n-2 m-1 + A x y + A x y + A x y + ... + A x + 10 11 12 1n ... n n-1 n-2 + A y + A y + A y + ... + A m0 m1 m2 mn Uvrsti ovde konkretne vrednosti za (x,y,z) i dobićeš sistem od (m+1)*(n+1) jednačine sa (m+1)*(n+1) nepoznatom. Gadan posao za čoveka, ali računar će ga rešiti, pre ili kasnije. :) Na ovaj način dobijaš funkciju koja _sigurno_ prolazi kroz sve zadate tačke, a ako su ti ulazne vrednosti onako zgodne kao u gornjem primeru, i između njih bi trabalo da ostane prilično mirna. Ono što me stvarno brine su brzina i potrošnja memorije. Ako ti je ulazna matrica kvadratna, dimenzija n*n, sistem je n^2*n^2. Znači, za ulaznu matricu 100*100, rešava se sistem 10000*10000. 'Ajde što će da traje, nego što će za to biti potrebna matrica od 100 miliona elemenata što uz 4-bajtni float izađe 400MB! :( U takvom slučaju mogao bi da podeliš podeliš ulaznu matricu 100*100 na recimo 8 delova 25*25 čime se zahtev za memorijom svodi na mnogo razumnijih 1.5MB. Slično važi i za vreme izračunavanja - mrzi me sad da tačno računam vremensku dimenziju problema. Ako se odlučiš da iskoristiš ovu ideju, obavezno mi javi kako je ispalo na kraju. > Ocajnik sa Banovog Brda. Pozdrav, komšija. :)
algoritmi.231 embe, -> #229, zkis
ŢŢProblem je prakticne prirode. Resavam problem iz termickih proracuna ŢŢgde ima puno tabela sa empirijskim podacima. Tabele su ŢŢtrodimenzionalne, tj za ulazne vrednosti X i Y dobija se trazena ŢŢvrednost Z. ŢŢNa na koji nacin da dobijem matematicku jednacinu aproksimativne ŢŢpovrsi tipa Z=F(X,Y) koja sa dovoljno tacnosti prikazuje ovaku tabelu ŢŢ??? ŢŢPotreban je univerzalni matematicki princip resavanja ovakvih ŢŢproblema. ŢŢOcajnik sa Banovog Brda. Komsija, moram odmah da ti kazem jednu tuznu i jednu radosnu vest. Tuzna - Univerzalni matematicki princip ne postoji. Radosna - Postoji beskonacno mnogo "resenja". Recimo: Radi konciznosti objasnjenja uzecu na primer tablicu 2 X 2 (znaci imamo poznate 4(cetiri) tacke) (Ovo NARAVNO vazi i za tablicu proizvoljnih dimenzija!) x/y | 1 2 ili simbolima: x/y | y1 y2 ------------- --------------- 10 | 0.5 0.7 x1 | z11 z12 15 | 0.6 0.9 x2 | z21 z22 Mozemo samo da mastamo o tome koja je povrs u pitanju. Da li je to deo lopte, paraboloid ,hiperboloid , a da ne pominjemo logaritamske, trigonometrijske, eksponencijalne ... povrsi. Bilo kako bilo, ma koju povrs usvojili, za vrednosti (x,y) iz tablice mora se dobiti vrednost z iz tablice dok ce unutar (ponavljam: unutar) oblasti, (u ovom slucaju oblast je pravougaona 10<x<15, 1<y<2 ) dobiti interpolirane vrednosti koje su realnije ukoliko je broj tacaka (citaj: broj vrsta i kolona tablice) veci. Elem, evo jednog od resenja: ------------------------------- Za tablicu sa V - vrsta i K-kolona imacemo N=V*K tacaka. Izabracemo povrs oblika: (1) f(x,y) = suma(Ci * x^(N-i-1) * y^i ) , za i=0 do N-1, Ci - nepoznate konstante Ovo je polinom sa dve nepoznate, stepena N-1. sto za N=4 daje: (2) f(x,y)= C1* (x^3) + C2* (x^2 * y) + C3* (x * y^2) + C4* (y^3) C1,C2,C3,C4 su konstante koje treba odrediti. Postupak odredjivanja konstanti je sledeci: Imamo cetiri tacke kroz koje mora da prodje povrs, odnosno cetiri uslova: C1* (x1^3) + C2* (x1^2 * y1) + C3 *(x1 * y1^2) + C4 *(y1^3) = z11 C1* (x1^3) + C2* (x1^2 * y2) + C3 *(x1 * y2^2) + C4 *(y2^3) = z12 C1* (x2^3) + C2* (x2^2 * y1) + C3 *(x2 * y1^2) + C4 *(y1^3) = z21 C1* (x2^3) + C2* (x2^2 * y2) + C3 *(x2 * y2^2) + C4 *(y2^3) = z22 (x1,x2,y1,y2,z11,z12,z21,z22 su vrednosti iz tablice, dakle, poznate vrednosti) Vrednosti koeficijenata C1..C4 se dobijaju kao resenja ovog sistema linearnih jednacina. Kada se dobiju vrednosti za C1,C2,C3,C4 uvrste se u (2) Na kraju se dobija jednacina povrsi koja ima oblik (1), pa se mogu dobiti i vrednosti koje nisu u tablici. NAPOMENA: Ovo je samo jedno od resenja cije je malo ogranicenje da ne smeju da postoje dve tacke sa odnosom koordinata: x1/x2=y1/y2=z1/z2 Ovo ogranicenje se lako prevazilazi "siftovanjem" x ili y koordinata cele tablice za proizvoljnu konstantu. Na primer: Tacke: x1=1 y2=2 z1=5 i x1=2 y1=4 z1=10 nalaze se u "nedozvoljenom" polozaju. Ako y koordinate "pomerimo" na primer za +51 (proizvoljno) dobicemo x1=1 y2=53 z1=5 i x1=2 y2=55 z1=10 (sada vec nisu u "nedozvoljenom" polozaju!) Kada se odredi polinom (odnosno koeficijenti C1...CN), jednostavno, ako zelimo vrednost za x=1.5 i y=3 u funkciju ubacimo x=1.5 i y=3+51=54. (Ne treba preterivati u velicini konstante koja se dodaje jer se radi sa stepenovanjem, pa moze doci do gubitka preciznosti pri resavanju sistema) Komsija, ukoliko zelis jos neka dodatna objasnjenja ili program koji sam napravio da radi po ovom principu, slobodno javi. PS. Sada se svima izvinjavam sto ovo opsirno objasnjenje nisam stavio u fajl, ali s obzirom da se tema zove algoritmi i da nisu svi algoritmi u deset recenica, nadam se da cete biti uvidjavni. Pozdrav.
algoritmi.232 embe, -> #230, vasic
>>Priznajem da ovo nisam nikad radio, ali mi jedno pade na pamet: Mogao >>bi da pokusas da ideju Lagranzove interpolacije prosiris sa funkcije >>jedne na funkciju dve promenljive. Hmm... dobro je, komsija. Razlika je samo u izboru polinoma. >>>Ono sto me stvarno brine su brzina i potrosnja memorije. Ako ti je >>>ulazna matrica kvadratna, dimenzija n*n, sistem je n^2*n^2. Znaci, za >>>ulaznu matricu 100*100, resava se sistem 10000*10000. 'Ajde sto ce da >>>traje, nego sto ce za to biti potrebna matrica od 100 miliona >>>elemenata E bas fino sto si ovo napomenuo. Predlazem da se malo u ovoj temi pozabavimo jednom naizgled trivijalnom a ipak izuzetno kompleksnom temom: RESAVANJE VELIKIH SISTEMA LINEARNIH JEDNACINA (naravno racunarom). Sa aspekta brzine, upotrebe resursa racunara, tacnosti i slicno. Pozdrav.
algoritmi.233 ppecanac, -> #232, embe
> pozabavimo jednom naizgled trivijalnom a ipak izuzetno > kompleksnom temom: RESAVANJE VELIKIH SISTEMA LINEARNIH > JEDNACINA (naravno Ja sam svojevremeno trazio resenje za sistem linearnih jednacina sa simetricnom matricom, trebalo mi je hitno. Cini mi se da niko nije reagovao. 'Morao' sam zato da ga zbrzim sam, pa na optimizaciju nisam ni pomisljao. Koga jos to interesuje kad je pentium pro u modi. Salim se. (ja sam jos u uvek na amd-u)
algoritmi.234 jjerry,
Mozda ovo pitanje i nema veze sa temom algoritmi ali ,ipak, saljem. Naime,posto sam relativno nov u asemblerskim vodama interesuje me samo algoritam (ako neko zna moze i kod) neke interapt hendler rutine. U ovoj temi su ,izgleda,svi sa Banovog Brda,dakle, moje komsije ;)
algoritmi.235 mmilosh, -> #233, ppecanac
>> pozabavimo jednom naizgled trivijalnom a ipak izuzetno >> kompleksnom temom: RESAVANJE VELIKIH SISTEMA LINEARNIH >> JEDNACINA (naravno > > Ja sam svojevremeno trazio resenje za sistem linearnih > jednacina sa simetricnom matricom, trebalo mi je hitno. Evo ja sam zaiteresovan za razglabanje o tome pošto upravo to sada radimo na fakultetu (Matematički, smer za računarstvo i informatiku, I godina). Ali još sam početnik u tome pa bih u početku samo slušao ;))
algoritmi.236 janko, -> #234, jjerry
> Mozda ovo pitanje i nema veze sa temom algoritmi ali ,ipak, saljem. Nema, vidi dalje. > Naime,posto sam relativno nov u asemblerskim vodama interesuje me > samo algoritam (ako neko zna moze i kod) neke interapt hendler > rutine. Ne, diskusiji na ovu temu mesto je u temi asembler. Ovo što tebe zanima ipak nema veze sa algoritmima.
algoritmi.237 embe,
Subject: Resavanje velikih sistema linearnih jednacina. Hteo bih samo malo da usmerim paznju i diskusiju (ako je uopste bude bilo). Dakle ... Pre pojave racunara, a u doba logaritmara veliki izazov je predstavljao i sistem linearnih jednacina reda 3 i vise. Onda je postojao jedan praktican nacin resavanja (gausov postupak eliminacije) i nekoliko teoretskih (teoretskih, zato sto nisu bili primenljivi zbog velikog broja aritmetickih operacija.) I onda je dokazano da je od svih direktnih (= neiterativnih) postupaka, gausov postupak najbrzi jer je potrebno najmanje operacija. I tu se, sto se tice direktnih postupaka, stalo. Pre vise od 150 godina. Iterativni postupci su druga prica. Od pojave racunara poceli su da prezivljavaju drugu mladost. Povecavanjem broja jednacina, neprikosnovenost gausovog postupka se sve vise dovodila u pitanje. Cak, da apsurd (a u stvari to i nije) bude veci, nesto sto se na prvi pogled ne bi nikad moglo dovesti u pitanje, - pocela je da se gubi tacnost. Zna se da gausov postupak nagomilava gresku i da je ona veca sto je broj jednacina veci. Sa druge strane, iterativni postupci ne pate od problema nagomilavanja gresaka jer se sami iterativno popravljaju. Tako je doslo do toga da je Gaus i definitivno out a da su iterativni postupci in. Naravno, Gaus se jos, tu i tamo drzi, uz neke modifikacije, ali... Koja je dakle, osnovna mana gausovog algoritma za resavanje ? Odgovor je pomalo apsurdan, to je njegova univerzalnost ! Naime, ovim nacinom je moguce resiti sve sisteme linearnih jednacina koji uopste imaju resenja. Takodje, resava simetricne, nesimetricne, trakaste i pune sisteme. Ali, veliki sistemi linearnih jednacina, cije se resavanje zahteva u novije vreme, nisu toliko proizvoljni. Oni su uglavnom simetricni (lepa strana prirode ona sa isto toliko nepoznatih !!! Kada bi se to resavalo uz pomoc Gausa, puna matrica bi stala na "tricavih" 96 gigabajta (za dvostruku tacnost). Medjutim, to ne pije vodu. Dakle, ovo je samo bio slagvort, otvaram diskusiju o resavanju velikih (specificnih) sistema linearnih jednacina. Specificni sistemi = svi koji imaju neku bitnu karakteristiku, kao sto je simetricnost, trakastost, dijagonalna dominantnost, pozitivna definitnost ili nesto deseto.... Ovakvi sistemi se najcesce i javljaju u nekim konkretnim problemima (izuzimam zbirke zadataka :) ) Ukoliko neko nesto zna i hteo bi to da podeli, neka se ukljuci. Ukoliko neko ima neki problem, takodje neka se ukljuci.
algoritmi.238 vdjole,
> 1.229, 1.230, 1.231, ... 1.235 Evo jedan objedinjeni komentar na nekoliko poruka koje su se odnosile na aproksimaciju funkcije dve promenljive a zatim na resavanje sistema linearnih jednacina. Izvinjavam se zbog nedostatka YU slova u ovoj poruci, ali kako koristim yuscii a ovde ce biti malo uglastih i viticastih zagrada, trenutno je set code=none. A izvinjavam se i zbog duzine, ali, kako neko ovde rece, neke stvari se ne mogu objasniti u dve-tri recenice. Daklem, pocetni problem je bio kako aproksimirati tablicno zadanu funkciju dve promenljive. Ovde su moguca dva pristupa, a moguce je da autor pocene poruke nije bio bas najprecizniji u tome koji mu treba: 1- interpolacija funkcije: resenje u obliku neke jednostavne funkcije vazi samo unutar jedne "pravougaone" oblasti u tablici koja se prostire od (x1,y1) do (x2,y2). Pri trazenju vrednosti za proizvoljno x i y prvo se odredi u koje "polje" padaju vrednosti x i y, pogodna jednostavna funkcija se odredi (kasnije o tome kako se odredi) na osnovu vrednosti u okolnim tackama i izracuna se z=f(x,y). 2- aproksimacija funkcije: resenje u obliku neke (manje-vise) jednostavne funkcije vazi unutar cele oblasti definisane tablicom. Medjutim, aproksimativna funkcija ne mora biti jednaka tablicnim vrednostima ni u jednoj tacki iz tablice, vec se obicno uzima da je najopogodnije da zbir kvadrata odstupanja aproksimacije od tablicnih vrednosti bude minimalan. Ovo je poznati "metod najmanjih kvadrata" i vrlo je pogodan pri obradi rezultata iz raznih merenja i sl. zato sto sluzi i kao "filter" za "peglanje" slucajnih gresaka u merenju pojedinih vredosti iz tablice. I za 1- i za 2- vazi da izabrani oblik funkcije mora biti u skladu sa raspolozivim brojem tacaka, tj. broj koeficijenata funkcije koja se odredjuje ne sme biti veci od broja raspolozivih tacaka. U prvom slucaju to je broj "okolnih" tacaka, a u drugom ukupan broj tacaka u tablici. Inace, ako je raspolozivi broj tacaka jednak najmanjem dozvoljenom broju tacaka za izbrani oblik interpolacione ili aproksimacione funkcije, pristup 2- se, de fakto, svodi na pristup 1-. Obicno je pogodno za "jednostavnu" funkciju uzeti polinom, osim ako se zna da, teoretski, problemu koji se razmatra odgovara neka druga funkcija. Medjutim, polinom gotovo uvek "upali" jer se i druge funkcije razvijanjem u red mogu aproksimirati polinomom. Ako se radi INTERPOLACIJA resenje se manje vise svodi na odredjivanje Lagranzevog polinoma ili na neki drugi postupak koji, u sustini, daje potpuno isti polinom. U najjednostavnijem slucaju interpolacija se radi samo na osnovu 4 okolne tacke. Resenje je pravoizvodna povrsina tipa hiperbolickog paraboloida. Na sve 4 ivice oblasti u kojoj se interpolira (tj. na potezima x1y1...x1y3 ili x1y1...x2y1 itd.) resenje se dobija linearnom interpolacijom. Unutar oblasti resenje je funkcija drugog stepena. Meni licno uvek je bilo nekako zgodno ovu interpolaciju raditi koristeci "funkcije stapanja" (blending functions, sto bi rekli Englezi). Ako za 4 okolne "praovugaono" rasporedjene okolne tacke imamo x1,y1,z1... x4,y4,z4 (x1=x3, x2=x4, y2=y1, y3=y4), za proizvoljno x,y unutar ili na granici ove oblasti interpolira se: z= f1(x,y)*z1 + f2(x,y)*z2 + f3(x,y)*z3 + f4(x,y)*z4 gde su f1...f4 funkcije koje mogu imati vrednost od 0 do 1: f1 = (x2-x)/(x2-x1) * (y3-y)/(y3-y1) f2 = (x-x1)/(x2-x1) * (y3-y)/(y3-y1) f3 = (x2-x)/(x2-x1) * (y-y1)/(y3-y1) f4 = (x-x1)/(x2-x1) * (y-y1)/(y3-y1) (btw. tacno na sredini oblasti sve cetiri imaju vrednost 0.25, tj. sve 4 okolne tacke ravnopravno ucestvuju u odredjivanju vrednosti) Za interpolaciju na osnovu 4 okolne tacke NEMA NIKAKVOG OPRAVDANJA koristiti vise stepene polinoma jer gornji postupak daje "najglatkiju" (uh, al je rec) povrsinu dok za polinome viseg stepena ima beskonacno mnogo resenja koja mogu sadrzati neocekivane "krivine" unutar oblasti, iako su tacna u one 4 tacke. Postoje i neke egzoticne varijante tzv. "transfinitne" interpolacije ( (c) : Coons ) kod koje se na granicama oblasti aproksimaciona funkcija tacno poklapa sa nekim slozenijim unapred zadatim funkcijama a unutar oblasti se takodje koriste "blending functions". Ako su granicne funkcije funkcije linearne, transfinitna interpolacija se svodi na gornji slucaj. Ako se radi APROKSIMACIJA (tj. metodom najmanjih kvadrata) takodje se treba cuvati polinoma viseg stepena. Generalna smernica moze biti da polinomi stepena veceg od 3. imaju tedenciju da sadrze neocekivane prevojne tacke, tj. da budu "talasasti" unutar oblasti za koju se odredjuju. Ovo je vrlo nepozeljna osobina ako se zeli automatizovati postupak nalazenja vrednosti funkcije, jer se bez vizuelnog uvida u aproksimiranu funkciju nikad ne moze znati da dobijena vrednost nije "iskocila" na nekom talasu. Ako se zna teoretski oblik funkcije koja se aproksimira takodje moze biti pogodno upotrebiti takve - druge- funkcije a ne polinome. Na primer, postoji problem koji je pogodno aproksimirati kao: z(x,y) = a0 + a1*sin(x) + a2*cos(x)*sin(y) + a3*cos(x)*cos(y) O tome kako se odredjuju koeficijenti funkcija metodom najmanjih kvadrata, mozemo nekom drugom prilikom, ako nekoga bude interesovalo (da ne tupim bas previse). I aproksimacija i interpolacija zahtevaju odredjivanje koeficijenata neke pogodne funkcije. U oba slucaja ovo se svodi na resavanje sistema linearnih jednacina. Na zalost kolega koji su ovde razmatrali mogucnost resavanja sistema 10000*10000, ovde postoje brojni prakticni problemi, koji nemaju veze samo sa brzinom racunara. Nezgoda je u tome sto su sistemi linearnih jednacina koji nastaju pri odredjivanju interpolacione ili ekstrapolacione funkcije, tzv. "ill-conditioned systems". tj. teze da imaju relativno male vrednosti u blizini glavne dijagonale matrice sistema (ili se njihova matrica svodi na takvu matricu). Ovakvi sistemi imaju malu determinantu i pri njihovom resavanju egzaktnim metodama DOLAZI DO VRLO VELIKIH NUMERICKIH GRESAKA! Recimo, standardni postupak za sisteme lin. jednacina je Gausov. Medjutim, vec kod ovakvih sistema velicine, recimo 20x20, ako se radi sa 4-bajtnim FLOAT brojevima, dolazi do tolikog nagomilavanja gresaka da su resenja, iako formalno tacno dobijena, prilicno besmislena- sto se lako moze ustanoviti proverom. Ako se resenje sistema dobija inverzijom matrice, kao: -1 ŠAĆšxć=šbć ---> šxć = ŠAĆ šbć ( šxć su ovde zapravo trazeni koeficijenti aproksimacione funkcije ) greske bivaju jos i vece. Koriscenje 8-bajtnih FLOAT brojeva moze malo pomoci, ali ne mnogo. Postoje jos neki postupci za ovakve sisteme, kao tzv. L-R postupak, gde se matrica sistema razbija na dve trougaone, itd. Za resavanje sistema koji nastaje pri aproksimaciji metodom najmanjih kvadrata postoji i znatno bolji, ali relativno slozeni postupak pod nazivom "singular value decomposition". Jedan jednostavan postupak za poboljsanje resenja za "ill-conditioned" sisteme je sledeci: 1: Svakako treba koristiti 8-bajtne promenljive 2: Sistem ŠAĆšxć=šbć se resi inverzijom matrice, kao gore. Medjutim, zbog gresaka, tada se, zapravo, dobije resenje šx+dxć gde je šdxć vektor gresaka pri odredjivanju šxć. 3: Izracuna se šb+dbć kao ŠAĆšx+dxć=šb+dbć; oduzimanjem šbć izdvoji se šdbć -1 4: Nadje se šdxć kao: šdxć = ŠAĆ šdbć 5: Koriguje se šxć oduzimanjem šdxć od prvobitnog resenja. 6: Tacke 3-5 se ponove u nekoliko iteracija (obicno je 5-6 dovoljno), pri cemu se (nadamo da se) dobija sve manje šdxć. Konacna vrednost za šxć se uzme za resenje sistema. Moglo bi se savetovati da se NE KORISTE "home made" rutine za inverziju matrica ili za resavanje sistema jednacina, osim ako covek TACNO zna sta radi. Korektna inverzija matrica zahteva gomilu zamena mesta i kolona s obzirom na vrednosti clanova, sve u cilju smanjivanja pomenutih numerickih gresaka. Uh, toliko za sada Š i previse :) Ć. Na kraju, da neko ne misli da se sad ja pravim strasno pametan, ovo je uglavnom po secanju na sadrzaj jedne VRLO korisne knjige kojoj se sad ne secam tacnog naziva ni autora, a zove se nesto kao "A Cookbok of Numerical Recipes", sa brojnim primerima koda (u FORTRAN-u). Negde na poslu imam tacan naziv, pa ako nekome treba neka vice. A mislim da se ta knjiga vec i pominjala negde u ovoj konferenciji.
algoritmi.239 qpele,
Evo i mog doprinosa raspravi o interpolaciji Evo i mog doprinosa rasparavi o interpolaciji.Uz poruku ide moj maturski rad (program ) za interpolaciju. Sam program je prilicno amaterski uradjen ,ali interpolaciju dobro radi i crta priblizan grafik funkcije na intervalu (x-min,y-min)-(x-max,y-max). interpol.rar
algoritmi.240 mmilosh, -> #238, vdjole
> ŠAĆšxć=šbć ---> šxć = ŠAĆ šbć > > ( šxć su ovde zapravo trazeni koeficijenti aproksimacione > funkcije ) Eh, ti i tvoj #$!@'& yuscii! :))) Sad su velike i srednje zagrade š i ć :(( Al shvatili smo kako treba da izgleda. Mislim, ako se već baviš matematikom bio bi red da pređeš na neki ljudski raspored. Izvinjavam se, ali sam morao da primetim.:) Pozdrav.
algoritmi.242 vdjole, -> #240, mmilosh
>Eh, ti i tvoj #$!Ž'& yuscii! :))) Sad su velike i srednje zagrade š i ć :(( >Al shvatili smo kako treba da izgleda. >Mislim, ako se već baviš matematikom bio bi red da pređeš na neki ljudski >raspored. Kuku! sad sam tek video šta sam uradio- poslao poruku po yuscii iako sam mislio na code-none. Sorry svima koji su imali problema da ovo pročitaju. Ne znam da l' je vredno truda da onu poruku obrišem pa da pošaljem ponovo. 'zvinte!
algoritmi.243 bokir,
Jel može neko da objasni LZ/LZW algoritam za kompresiju?
algoritmi.244 vector, -> #243, bokir
│ Jel moze neko da objasni LZ/LZW algoritam za kompresiju? └───────── Uz poruku je datoteka iz \Sezam\RSoft direktorijuma. Cini mi se da su primeri pisani u C-u ... r059lzw.zip
algoritmi.245 biber,
Kako skeneri rade softversko povećanje rezolucije? Ili drugim rečima, kako pretvoriti npr. sliku 320x200 u 640x400, a da ta slika stvarno izgleda kao da joj je povećana rezolucija?
algoritmi.246 vdjole, -> #245, biber
> Kako skeneri rade softversko povećanje rezolucije? Pretpostavljam da se to radi interpolacijom. I mene interesuje ako neko ima detaljniji odgovor.
algoritmi.247 nenad, -> #246, vdjole
>> Kako skeneri rade softversko povećanje rezolucije? > > Pretpostavljam da se to radi interpolacijom. I mene interesuje ako neko > ima detaljniji odgovor. Neko je ovde dao lepo i detaljno objašnjenje pre... recimo godinu dana ili nešto više. Ne sećam se tačno cele priče, ali nije interpolacija, za to bi bio dovoljan i softver. Čini mi se da je bila neka priča sa realnom optičkom rezolucijom i rezolucijom do koje se dolazi finim pomerajem "valjka". Znači nešto slično kao ona 360x360 rezolucija kod 24-igličnih matričnih štampača, dakle bolja nego tadašnji laseri, ali zato je jedna tačka "malo" poveća... Kod skenera je ipak nešto povoljnija situacija jer i ta "softverska" rezolucija je stvarna, samo zahteva duže skeniranje i obradu - sva se mesta gledaju onoliko puta koliko puta je zahtevana rezolucija veća od realne optičke rezolucije... ako me razumete šta hoću da kažem. :) U svakom slučaju mislim da pravo objašnjenje nećemo naći u ovoj konferenciji.
algoritmi.248 biber, -> #247, nenad
>> interpolacija, za to bi bio dovoljan i softver. Čini mi se da je >> bila neka priča sa realnom optičkom rezolucijom i rezolucijom do >> koje se dolazi finim pomerajem "valjka". Dobro, mene više zanima software-only tehnika. Dakle da li postoji algoritam za softversko povećanje rezolucije. Pretpostavljam da se time nešto mora i izgubiti (takozvani zakon o održanju... piksela :) Pretpostavljam da će slika postati malo "umekšana".
algoritmi.249 silence,
Zdravo svima. Potreban mi je algoritam za minimizaciju isecanja manjih pravougaonika iz zadatog veceg. Ako neko ima nesto slicno bio bih zahvalan na istom. Svi dogovori su moguci. Dakle rezime: Imamo n ploca povrsine A i m1, m2,..., mx ploca razlicitih povrsina? Koji je minimalan broj ploca A potreban da bi sve ploca mi
algoritmi.250 nenad, -> #248, biber
> Dobro, mene više zanima software-only tehnika. Dakle da li > postoji algoritam za softversko povećanje rezolucije. Pretpostavljam > da se time nešto mora i izgubiti (takozvani zakon o održanju... > piksela :) Pa ne izgubi se ništa, ali se i ne dobije mnogo - količina informacije je ista. Ono što se promeni jeste način na koji je ta informacija prezentovana, to jest očima niko nije rekao da je to isto ono od pre samo malo ulepšano - i rezultat je bolji. :) E sad, ono što ti hoćeš - softversko povećanje rezolucije - možda i nećeš dobiti u pravom smislu te reči (dobićeš veći broj različitih tačaka), ali recimo za povećanje detalja na bit-map slikama ovo je sasvim upotrebljivo - oči same to ne bi umele da urade tako dobro. > Pretpostavljam da će slika postati malo "umekšana". Evo uz ovu poruku primera, pa sam proceni. Zumiran je detalj jedne slike, sa i bez uključene interpolacije piksela. interpol.rar
algoritmi.251 tomislavr,
Ima li neko program/funkciju (na bilo kom pr. jeziku) za prevođenje brojeva iz rimskog u arapski sistem?
algoritmi.252 firus, -> #251, tomislavr
> Ima li neko program/funkciju (na bilo kom pr. jeziku) za > prevođenje brojeva iz rimskog u arapski sistem? Uz poruku je zakačena arhiva sa datotekama RIM2ARAP.C i RIM2ARAP.PAS koje rešavaju problem. Problem ispravnosti unetog rimskog broja (u smislu da je ispravan i npr. MIXC) nije rešen. Jednostavno me je mrzelo da sada prepravljam sors i ubacujem to parče. BTW, da nisi možda student FON-a? ;) Ovo je bio prvi zadatak iz PP-a u poslednjem ispitnom roku. rim2arap.zip
algoritmi.253 tomislavr, -> #252, firus
> Uz poruku je zakačena arhiva sa datotekama RIM2ARAP.C i > RIM2ARAP.PAS koje rešavaju problem. Problem ispravnosti unetog Dankešen :) > BTW, da nisi možda student FON-a? ;) > Ovo je bio prvi zadatak iz PP-a u poslednjem ispitnom roku. Nisam na FON-u, ali zadatak je za seminarski na jednom drugom fax-u.
algoritmi.255 mmilosh, -> #253, tomislavr
> Nisam na FON-u, ali zadatak je za seminarski na jednom drugom > fax-u. Matematički, jel da?
algoritmi.256 ratman,
Kopka me jedan problem.. Na koliko nacina se iz npr., skupa od 30 elemenata (svi razliciti) mogu formirati 3 grupe od po 10 elemenata (redosled unutar grupa nije bitan, samo sastav)? Posto je za samo jednu grupu N=C(30,10), rekao bih da je taj broj: C (30,10) x C (20,10) C oznacava, naravno, broj kombinacija, odn binomni koef,... itd. Da li sam u pravu? Osnova kombinatorike se slabo secam, a interesuje me ovaj proracun zbog nekakvih eksperimenata (bioloskih) i algoritama za stratifikaciju, itd. I, naravno, mnogo sam bolji u izmisljanju problema nego resavanju.... :) Pozdrav, Dejanű▀ű▀řÚřÚřÚ
algoritmi.257 dule.n, -> #256, ratman
=> C (30,10) x C (20,10) => => C oznacava, naravno, broj kombinacija, odn binomni koef,... itd. => => Da li sam u pravu? Osnova kombinatorike se slabo secam, a U pravu si.
algoritmi.258 dzakic, -> #256, ratman
> Posto je za samo jednu grupu N=C(30,10), rekao bih > da je taj broj: > > C (30,10) x C (20,10) Ukoliko je svaka grupa na neki način numerisana i zna se koja je prva, koja druga a koja treća, onda si u pravu. C(30,10) - biraš prvo 10 komada od 30, nakon toga ostaje 20 elemenata od kojih ponovo biraš 10 - C(20,10). To je ok. Međutim, imaćeš slučaj da su elementi u drugoj grupi, identični elementima iz prve grupe iz nekog prethodnog izvlačenja. Dakle, same grupe 1 i 2 jesu neki novi raspored, ali posmatrano globalno, to je opet isto 'cepanje'. Ukoliko ti treba ovakav drugi slučaj, tada rezultat treba da podeliš brojem ovakvih situacija. A on je.. hm :), 3! ?
algoritmi.259 mcar,
Kako izracunati broj godina, meseci i dana izmedju dva proizvoljna datuma? Da li neko zna nesto o ovom algoritmu, ili o tome gde je isti opisan? Unapred zhavalan Marko
algoritmi.260 obren, -> #259, mcar
> Kako izracunati broj godina, meseci i dana izmedju dva proizvoljna datuma? Za početak, postoji stanradna (ANSI) funkcija za određivanje razlike u sekundama između dva datuma (pogledaj difftime i sve o tome). Ta razlika u sekundama se može aproksimativno (deljenjem) prevesti u dane, mesece godine itd. Problem je ako hoćeš da odrediš razliku tačno, u "pravim" mesecima. Recimo ako je u pitanju 30 dana razlike, to može biti i jedan mesec i 2 dana (ako je negde oko februara), a može biti i nula meseci i 30 dana ako je recimo mart i sl.
algoritmi.261 mcar,
Upravo je problem u tome sto mi ne odgovara aproksimativno reenje pomocu broja sekundi ili dana. Takodje problem prave i pretupne godine. Mislio sam da negde postoji vec gotov algoritam, ako ne moracu da se maltretiram. Marko
algoritmi.262 vule.,
Da li neko zna kako da napisem program koji sortira linije teksta po abecedi ?
algoritmi.263 ognjen, -> #262, vule.
)-> Da li neko zna kako da napisem program koji sortira linije )-> teksta po abecedi ? Šta je tu komplikovano? for i:=1 to broj_linija-1 do for j:=i to broj_linija do if (linija[i]>linija[j]) then razmeni_linije(i,j);
algoritmi.264 vule., -> #263, ognjen
Cini mi se da je to PASCAL, a ja nisam napomenuo da mi treba za BASIC.... Nema veze, pojasni mi malo program...
algoritmi.265 ognjen, -> #264, vule.
)-> Nema veze, pojasni mi malo program... for i:=1 to broj_linija-1 do for j:=i+1 to broj_linija do if (linija[i]>linija[j]) then razmeni_linije(i,j); Davno beše basic, ali da pojasnim. Ovo je inače najlakši (svakako nije najbrži, ali je dovoljno efikasan za ono što ti treba) algoritam za sortiranje. Uslov IF proverava koja je linija pre koje u abecedi. Dakle "PAJA">"PERA" nije tačno, jer je 'A'<'E'. Takođe "MIKA">"NESA" je tačno, jer je 'M'>'N'. Dakle, gleda se prvo slovo koje se ne poklapa. Nisam siguran da ovo radi ovako u basicu, pa napravi sam proceduru za proveru. Ovaj, gore opisani IF uslov radi po sledećem redosledu: upoređuje 1,2 i zameni ako 2 treba da bude pre jedan. Pa 1,3, pa 1,4 do 1,n, i na kraju imaš na prvom mestu string koji treba da bude prvi. Onda ide 2,3; 2,4... 2,n - uradio je i drugo mesto... i tako dalje dok ne sredi ceo niz. Nadam se da je malo jasnije. PS: pređi na pascal.
algoritmi.266 vule.,
Treba mi algoritam za simulaciju gadjanja u igricama, kao u DEZINTEGRATORS, SCORCH, WORMS, itd, znaci 2D(jacina,ugao,vetar) Unapred zahvalan...
algoritmi.267 kenza,
Hi! Jel pisao neko algoritam za iks-oks? :) Za pocetak, standardni teren - 3x3 polja, za kasnije moze i onaj 'padajuci' ;) Poz.
algoritmi.268 mihailod, -> #267, kenza
> Jel pisao neko algoritam za iks-oks? :) Za pocetak, standardni > teren - 3x3 polja Krstic-kruzic ili tic-tac-toe (u teoriji igara Connect-3) je dosta proucavana igra. Najjednostavniji je heuristicki algoritam koji igra nemastovito, ali zato nikad ne gubi, lako ga je isprogramirati itd. Ogromna mana je u tome sto ga je nemoguce uopstiti za vece dimenzije. Nabacicu ovde osnovnu ideju: if(igras prvi) {igraj u sredinu (dalje je lako)} else { if(protivnik igrao u sredinu) igraj u ugao (i dalje je lako...) else igraj u sredinu (dalje je lako) } Na ovaj nacin broj strategija se smanjuje na smesnu cifru tako da ih je moguce rucno iskodirati. Takodje, korisno je upotrebiti i informaciju da su neke pozicije simetricne. Malo ozbiljniji pristup se dobija upotrebom nekih rezultata iz teorije igara. Pre svega, kako se radi o igri sa potpunom informacijom (dakle, tabla i figure su na raspolaganju obojici igraca - npr. poker je igra sa nepotpunom informacijom) i kako je igra konacna (jer je polje konacno, a igra se do njegovog popunjenja ili do zavrsetka igre (tzv. "sudden death" - npr. sah je sudden death igra (sudden death je mat pozicija) dok neke igre nisu - igra se do popunjenja table i onda broje poeni), to po teoremi o antagonistickim igrama ta igra ima ravnoteznu situaciju. Dakle, uvek se moze igrati na nereseno. To je sto se suve teorije tice, a ozbiljan algoritam bi, recimo, koristio minimax strategiju (uz opciono alfa-beta odesacanje). Uz ovu poruku zakacen je fajl koji predstavlja jedan kompletan program koji uz pomoc pomenutih tehnika igra Connect-3. Prouci ga i iz njega ces saznati neke osnovne tehnologije programiranja strateskih igara ovog tipa. Inace, program je skinut iz news konferencije comp.ai.games . > za kasnije moze i onaj 'padajuci' ;) Ovo je tzv. ograniceni Connect-4. Algoritam je dosta slozeniji. Nedavno je jedan holandjanin potpuno resio ovu igru. Tj., napisao je program koji sigurno dobija kao beli a sigurno igra nereseno kao crni. Nemam taj program niti sors, ali imam njegovu magistarsku tezu koja je zapravo cela posvecena toj igri. Imam je u .ps formatu, oko 120 strana A4, podugacka je (oko 700K .ps, to bi trebalo da se sabije na oko 200k .zip). Ako te stvarno zanima, poslacu ti na mail... Ako jos nekog ovo zanima, mogu i u temu. Inace, ako nameravas da pises program koji igra Connect-4, toplo preporucujem citanje te teze. sc_ttt.txt
algoritmi.269 mipedja, -> #268, mihailod
>.. Ako te stvarno zanima, poslacu ti na mail... Ako jos nekog >.. ovo zanima, mogu i u temu. Inace, ako nameravas da pises Ovo mi zvuci interesantno, shalji to ovde.
algoritmi.270 morkin, -> #268, mihailod
> njegovu magistarsku tezu koja je zapravo cela posvecena toj > igri. Imam je u .ps formatu, oko 120 strana A4, podugacka je > (oko 700K .ps, to bi trebalo da se sabije na oko 200k .zip). > Ako te stvarno zanima, poslacu ti na mail... Ako jos nekog ovo > zanima, mogu i u temu. Inace, ako nameravas da pises program Šalji ovde, molim te.
algoritmi.271 embe, -> #267, kenza
>>Jel pisao neko algoritam za iks-oks? :) Za pocetak, standardni >>teren - 3x3 polja, za kasnije moze i onaj 'padajuci' ;) Svojevremeno je ovde, u ovoj konferenciji bio organizovan turnir programa za iks-oks. (Vidi poruku 1.62). Na tom takmicenju sam slucajno ja pobedio :). Pobednicka verzija programa nalazi se zakacena uz poruku 1.76. Njen source je u poruci 1.90. Napomena, zadatak takmicenja je bio da program ne sme nikako da izgubi, i MORA UVEK DA IGRA NAJJACE (svaku gresku protivnika mora da kazni). Takodje, program i protivnik naizmenicno igraju prvi potez. S obzirom na drugi uslov, da se uvek igra najjace, univerzalni algoritam koji bi ovo ispunjavao za table vece od 3x3 polja je jak tesko (da ne kazem nemoguce - odmah ce mi neko skociti u usta :)))) Source je tu i jako je komplikovan, ali to je posledica samog takmicenja koje je bilo tipa KO-PRE.
algoritmi.272 mihailod,
Evo, na zahtev zainteresovanih, ide magistarska teza Victor Allis-a (Holandija). ---------------------------------------------------- A Knowledge-based Approach of Connect-Four The Game is Solved: White Wins Victor Allis Department of Mathematics and Computer Science Vrije University Amsterdam, The Netherlands Master Thesis, October 1988. ---------------------------------------------------- reply for embe: > tesko (da ne kazem nemoguce - odmah ce mi neko skociti u usta :)))) Da, teorija lepo zvuci, ali, nazalost, dokazi teorema o ravnteznoj situaciji i teoreme o minimaksu spadaju u tzv. dokaze egzistencije. Drugim recima, tvrdi se da nesto postoji ali se ne navodi nacin za konstrukciju toga.
algoritmi.273 mihailod,
da probam opet ul... ako ne uspe bice ovih dana... connect4.arj
algoritmi.274 kajko, -> #269, mipedja
Šta mislite o jednom turniru PROGRAMA Sezamovih korisnika u IKS-OKS samo na većoj tabli. Ajd' da čujem mišljenja... O pravilima i načinu igre bi smo se dogovorili. NPR: Mogli bi da igramo na tabli 21x21 i da se ide na 5 u nizu. Potez bi bio ograničen na 20 sekundi, etc... KAJKO
algoritmi.275 mipedja, -> #274, kajko
>.. Sta mislite o jednom turniru PROGRAMA Sezamovih korisnika u >.. IKS-OKS samo na vecoj tabli. Meni se svidja ideja ( jeste da ne bih bash najslavnije prosao jer se nikad nisam bavio teorijom igara ali...), glasam ZA :). Sto se toga tice, glasam za bilo kakav oblik takmicenja.
algoritmi.276 vasic, -> #274, kajko
> Šta mislite o jednom turniru PROGRAMA Sezamovih korisnika u IKS-OKS samo > na većoj tabli. > NPR: Mogli bi da igramo na tabli 21x21 i da se ide na 5 u nizu. Potez > bi bio ograničen na 20 sekundi, etc... k00l! :) Time se zabavljalo moje društvo pred kraj trećeg srednje, tamo negde '89. Eh, kad se samo setim... Dok štreberi štrebaju nas nekoliko punom parom pravi XOX v1042.56. Završio sam godinu sa prosekom od celih 4.50000. :) Mislim da je ograničenje od 20 sec. više nego velikodušno. Moj tadašnji program je razmišljao manje od sekunde a radio je na CPC-464. (8-bitni Z80A, 4MHz - info za one koji su tad još bili mali :)) Trebalo bi smisliti neki način da programi razmenjuju poteze bez ljudskog posredovanja - tadašnje igranje preko telefona bilo je prilično naporno i podložno greškama. U najgorem slučaju, svaki program _mora_ imati funkciju za poništavanje poslednjeg odigranog poteza. Anyway, ako budem imao vremena rado ću učestvovati na ovom takmičenju a ako ne, pratiću ga sa zanimanjem.
algoritmi.277 mipedja, -> #276, vasic
>.. Trebalo bi smisliti neki nacin da programi razmenjuju poteze >.. bez ljudskog posredovanja - tadasnje igranje preko telefona >.. bilo je prilicno naporno i podlozno greskama. U najgorem >.. slucaju, svaki program _mora_ imati funkciju za ponistavanje >.. poslednjeg odigranog poteza. Ma ne, pogledaj fajl uz poruku 9.399, tamo je neko poslao zadatak i propozicije slicnog takmicenja. Moglo bi lepo da se prepravi za nas. Znaci islo bi otprilike ovako : Svaki program igra po jedan potez za jedno startovanje i sve podatke koji ce mu trebati za sledeci put snima u fajl sa prosledjenim mu imenom (svako ima svoj i tu moze da pishe sta hoce). Svi podaci o igri ( ko prvi igra, potez koji je odigrao protivnik itd.) se pishu u fajl koji koriste oba programa. Sve sto ostaje je da moderator ( ili ko je vec nadlezan za ovu temu) napishe programce ( ili batch fajl) koji ce da startuje naizmenicno programe dok partija ne bude gotova ( to ce da se oznaci nekom recju u fajlu ili kreiranjem nekog novog fajla ...). E, a necemo valjda da ostanemo samo na XOX-u ? To nek nam bude samo pocetak ( razigravanje). Samo, nisam video da se ijedno sluzbeno lice javilo da nas podrzi (ili im ja samo ne znam imena:) BTW: Sorry ako sam se mnogo raspisao :)
algoritmi.278 vasic, -> #277, mipedja
> Svaki program igra po jedan potez za jedno startovanje i sve podatke > koji ce mu trebati za sledeci put snima u fajl sa prosledjenim mu imenom Moglo bi, ali ako već pravim XOX onda hoću da mogu i ja da se igram. :) A i nekako mi je sve to ružno i glomazno. Voleo bih da može elgantnije. Recimo - Win32 named pipe i par semafora, mada mi je jasno da to nema šanse da prođe jer će sigurno biti ljudi koji bi hteli da rade u DOS-u ili pod Win16 ili na ZX-81.
algoritmi.279 hadzi, -> #266, vule.
█ Treba mi algoritam za simulaciju gadjanja u igricama, kao u █ DEZINTEGRATORS, SCORCH, WORMS, itd, znaci 2D(jacina,ugao,vetar) ▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀ Moj drug je imao nesto u pascalu, pa ako treba, javi mi na mail.
algoritmi.280 drejk, -> #279, hadzi
Zasto na mail da ti javi?? Baci u conf.
algoritmi.281 mipedja, -> #278, vasic
>.. Moglo bi, ali ako vec pravim XOX onda hocu da mogu i ja da se >.. igram. :) A i nekako mi je sve to ruzno i glomazno. Voleo >.. bih da moze elgantnije. Recimo - Win32 named pipe i par >.. semafora, mada mi je jasno da to nema sanse da prode jer ce >.. sigurno biti ljudi koji bi hteli da rade u DOS-u ili pod >.. Win16 ili na ZX-81. OK, ja sam samo predlozio metod koji se vec uspesno upotrebljava. Iskreno, ja nemam druge ideje ( a usput i ne znam da programiram pod windows-ima) pa ako neko ima valjan predlog, neka pozuri, nemam jos mnogo slobodnog vremena. :( BTW: Programi ce definitivno morati da rade na svim sistemima ( i sa svim standardnim kompajlerima)
algoritmi.282 kajko,
>> Svaki program igra po jedan potez za jedno startovanje i sve podatke >> koji ce mu trebati za sledeci put snima u fajl sa prosledjenim mu imenom >> (svako ima svoj i tu moze da pishe sta hoce). >> Svi podaci o igri ( ko prvi igra, potez koji je odigrao protivnik itd.) >> se pishu u fajl koji koriste oba programa. Ljudi, ja se sasvim slažem sa ovim. Trenutno nemam neki pametniji predlog, osim, ukoliko neko nema dva računara kod kuće i stolicu sa točkićima. >> E, a necemo valjda da ostanemo samo na XOX-u ? Ja se nadam da nećemo !!! Neko je ponudio (mrzi me da ganjam sad ko) da se igra 10x10 padajući. Nije loša ideja. Šta ostatak populacije kaže na to ? Inace, ko će da pude organizator, koja su pravila, kada počinjemo, etc... I ja se slažem da malo požurimo... KAJKO
algoritmi.283 obren,
Pošto se zapodenula ideja oko turnira u XOX programima, evo jednog prastarog XOX programa (Turbo Gomoku) koji mi stoji na disku ko zna otkad. xox.com
algoritmi.284 embe, -> #274, kajko
>> Sta mislite o jednom turniru PROGRAMA Sezamovih korisnika u >>IKS-OKS samo na vecoj tabli. >> Ajd' da cujem misljenja... >> O pravilima i nacinu igre bi smo se dogovorili. Odlicna ideja. Ko se javlja da bude organizator? Ko hoce neka izlozi kostur pravila, pa cemo ih za cas posla usaglasiti . Sto se tice table sasvim je ok 21x21 sa 5 u nizu. Komunikacija (prenosenje poteza) preko fajlova, stim sto bi neko morao da napravi MASTER program za kontrolu poteza, proglasenje pobednika i dodeljivanje poteza (citaj: pozivanje programa-takmicara).
algoritmi.285 qpele, -> #282, kajko
Ka> Neko je ponudio (mrzi me da ganjam sad ko) da se igra 10x10 Ka> padajuci. Nije losa ideja. Sta ostatak populacije kaze na to ? Mislim da je ovo daleko interesantnija ideja nego obican XOX. Sto se nacina odigravanja tice, mislim da je najefikasnije da programi kao ulazni parametar dobijaju prethodni potez protivnika, a da kao izlaz salju svoj naredni potez, a da se programima ostavi sloboda da organizuju datoteke u kojima ce se pamtiti svi potezi, trenutna situacija i sl. Ovim ce se obezbediti da svako radi u kojem zeli programskom jeziku . Samo jos treba napraviti program koji se koordinisati rad dva protivnicka programa, sto nije veci problem.
algoritmi.286 embe, -> #285, qpele
>> Ka> Neko je ponudio (mrzi me da ganjam sad ko) da se igra 10x10 >> Ka> padajuci. Nije losa ideja. Sta ostatak populacije kaze na to ? >> Mislim da je ovo daleko interesantnija ideja nego obican XOX. Kakav je to "padajuci" XoX ?
algoritmi.287 kenza, -> #286, embe
>> Kakav je to "padajuci" XoX ? Znaci mogu da se dodaju iskljucivo jedan na drugi. Dakle, moras prvo da igras na recimo A1 da bi mogao da odigras A2, pa onda A3 itd. Npr.: 5 X 4 O 3 X 2 O 1 X (Sa leve strane su redni brojevi poteza) Nadam se da si shvatio... Nije bas zgodno ovako za objasnjavanje :) Poz.
algoritmi.288 kajko, -> #284, embe
>> Odlicna ideja. Ko se javlja da bude organizator? Ko hoce neka >> izlozi kostur pravila, pa cemo ih za cas posla usaglasiti . >> Sto se tice table sasvim je ok 21x21 sa 5 u nizu. >> Komunikacija (prenosenje poteza) preko fajlova, stim sto bi neko >> morao da napravi MASTER program za kontrolu poteza, proglasenje >> pobednika i dodeljivanje poteza (citaj: pozivanje programa-takmicara). >> Što bi reka N°1: 'Mačka je moja i ja ću je pojesti !'. JA ću da budem organizator, so, slede pravila: 1° Igra se na polju 21x21 sa 5 u nizu. 2° Redovi i kolone moraju biti markirani brojevima i to: gornji levi ugao je (1,1), a donji desni (21,21). Kako bi inače programi razmenjivali poteze ? 3° Programi razmenjuju poteze preko datoteke 'POTEZ.XOX'. Ukoliko je datoteka prazna ili ne postoji, to znači da program igra prvi. Kad odigra potez, briše sadržaj datoteke 'POTEZ.XOX' i u njega smešta svoj potez. Koliko još datoteka treba samom programu, nije bitno. To je njegova interna stvar gde će on u međuvremenu držati podatke o partiji. 4° Ukoliko je potez pobedonosni u datoteku se, pored koordinata stavlja i kod 255. 5° Datoteka je organizovana ovako: prva dva bajta su red, a druga dva bajta su vrsta. To znači da datoteka ima samo 4 (četiri) bajta. U skladu sa prethodnom tačkom, ukoliko je odigrani potez doneo pobedu, datoteka ima 5 (pet) bajtova. 6° Koordinate u datoteci moraju izgledati ovako: '0512' ili '2004', etc. 7° Program koji proglasi pobedu, a do nje nije došlo, automatski će biti diskvalifikovan iz daljeg toka takmičenja. Poeni koje je skupio do tada će ostati njegovi (neće se brisati iz tabele). Za program koji je 'izgubio' piše se rezultat 3:0 u njegovu korist. 8° Vremensko ograničenje za potez je maksimalno 15 sekundi (Intel 166). 9° Vizuelni prikaz toka partije je obavezan ! Kako bi inače ja video da li je do pobede došlo ili ne. Program, kada odigra potez koji nije pobedonosni, snima koordinate i izlazi bez pauze. Ukoliko je potez pobedonosni, zvučni signal bi bio poželjan, kao i poruka i pauza. 10° Dok program razmišlja, na ekranu mora da stoje i koordinate poteza protivnika. Kad se potez 'smisli' koordinate moraju biti prikazane na ekranu. 11° Igra se po principu svaki sa svakim i na 3 (tri) dobijene partije. 12° Svaki korisnik može poslati samo jedan program. 13° Na turniru učestvuju SAMO programi korisnika SEZAM-a. Ništa sa Mreže nije dobrodošlo. 14° Učestvuju SAMO programi za DOS okruženje (za početak...). Lično mislim da je tako najbolje, jer neznaju svi programiranje po WIN-om, ali, ako bude nekoliko programa i za WIN, što da ne... kasnije... 15° Rezultati će ići ovako: trenutna tabela u poruku, a podaci o svakom meču u datoteku uz poruku. 16° Program koji masteriše partije i kreira izveštaje je moja briga. Rok za slanje programa za I XOX turnir je 01.10.1997. Programe šaljete meni na MAIL. Nakon svakog turnira, svi programi koji su u njemu učestvovali, idu u conf, da ih svi mogu pogledati i bolje se spremiti za sledeći turnir. Dajte predlog kako da bodujemo programe i šta sve treba da bude na tabeli. Lično mi se sviđa tabela z PCROBOTS takmičenja. BTW: Da li da opterećujemo conf ili da formiramo grupu, pošto temu u okviru nekog conf-a ne verujem da ćemo dobiti ? KAJKO
algoritmi.289 embe, -> #288, kajko
>> >> JA cu da budem organizator, so, slede pravila: >> Uzeo bih slobodu da naglas razmisljam o pravilima Tacke 1, 2 - OK. >> 3° ... >> Koliko jos datoteka treba samom programu, nije bitno. To je njegova >> interna stvar gde ce on u meduvremenu drzati podatke o partiji. Ovo mi se cini nedovoljno korektno. Recimo zelim da istestiram jedan program u partiji sa samim sobom. Nastaje haos jer oba programa koriste iste pomocne fajlove za svoj rad. Obavezno se mora predvideti da program-koordinator odredjuje imena fajlova koje ce programi-takmicari koristiti. Njihova imena ce prosledjivati kao parametar komandne linije. Sto se tice broja fajlova koji su potrebni jednom programu za cuvanje svoje pozicije itd. apsolutno je dovoljan jedan fajl. Tacke 4,5,6 - Ne svidja mi se koncepcija >> 4° Ukoliko je potez pobedonosni u datoteku se, pored koordinata stavlja >> i kod 255. Pobedonosni potez ne treba da proglasava takmicar vec program-koordinator. Ovo je ocigledno jer program-koordinator mora biti sposoban da prepozna kraj partije posle svakog odigranog poteza - prema tome izlisno je da se takav potez posebno obelezava. Shodno ovome tacka 7 (o samoproglasenju pobede) je izlisna. Tacka 6. - OK >> 8° Vremensko ogranicenje za potez je maksimalno 15 sekundi (Intel 166). Merenje vremena ? Kako ? Ako pricamo o DOS programima (a pricamo) dok se neki takmicarski program "premislja" o potezu, program koji bi bio zaduzen za mrenje vremena stoji. Tek kada takmicar zavrsi i "iznedri" potez moze se utvrditi koliko dugo je on razmisljao ali onda, po meni, sasvim je bez veze ponistiti mu potez jer je prekoracio vreme. Znaci sustina je u tome da se proces "razmisljanja" nekog programa ne moze prekinuti silom. Kazna za spore programe je usmena kritika :)) a za one koji se "zaglavljuju" - gubitak partije. >> 9° Vizuelni prikaz toka partije je obavezan ! Kako bi inace ja video da li >> je do pobede doslo ili ne. Program, kada odigra potez koji nije Mislim da je bespotrebno da takmicarski program radi vizuelizaciju partije. Prvo - cemu sluzi program-koordinator a drugo, mnogo grubo izgleda "paljenje" grafike naizmenicno jednog i drugog programa. Tacke 11,12,13,14 - OK. ZAKLJUCAK: E sad, nemoj da mislis da sam "ispljuvao" tvoje predloge. Prvo, da ti se zahvalim sto si se zalozio i zalegao za ovo takmicenje. Hteo sam samo da ukazem na neke nedostatke i ako smem, da uticem na samu tehnologiju turnira. Evo mojih predloga: 1. Mora se napraviti takav koordinatorski program koji ce voditi racuna o svemu. (Pravio si robote za PCROBOTS pa znas o cemu pricam). Naime, ovaj program ce kao ulazne parametre imati samo imena takmicarskih programa, izvodice takmicenje pozivajuci naizmenicno takmicare, prikazivati trenutnu situaciju, proglasavati pobednika itd. 2. Programi takmicari bice pozivani od programa koordinatora (spolja nevidljivo) i kao rezultat davace svoj potez. Naravno, imena fajlova (za svoj rad i za slanje rezultata) kao i poslednji potez protivnika dobijace kao parametar sa komandne linije. I to je sve sto oni treba da rade. Takav koordinatorski program sam gotovo doveo do kraja. Jos mi je ostalo da doradim samo neke sitnice pa cu ti ga predati. Prvo cu ga poslati da se istestira a onda moze i postati koristan onima koji prave takmicare - da ih mogu istestirati pre slanja na takmicenje. Vazna opcija ovog programa je sto pored igre PROGRAM-PROGRAM, omogucava i igru COVEK-PROGRAM i PROGRAM-COVEK (naravno i COVEK-COVEK :))) Program stize najkasnije sutra (18.09) i pratice ga uputsvo za upotrebu. Pozdrav, Milan.
algoritmi.290 space.ace, -> #288, kajko
Malih komentara povodom pravila: ║ 3° Programi razmenjuju poteze preko datoteke 'POTEZ.XOX'. Ukoliko ║ je datoteka prazna ili ne postoji, to znači da program igra prvi. ║ Kad odigra potez, briše sadržaj datoteke 'POTEZ.XOX' i u njega smešta ║ svoj potez. ╚════ Mislim da je bolje ovako: program u stdin prima podatke o potezu protivnika (ekvivalentno čitanju potez.xox), zatim na stdout piše svoj potez (takođe ekvivalentno pisanju u potez.xox). Sad, postojao bi program (mediator), koji bi sređivao sve ove podatke između dva programa u meču i snabdevao ih podacima (ispis na stdout -> programski stdin). Valjda neko razume ovo? Samim tim, mediator program bi i iscrtavao status partije i poteze, takođe i proglašavao pobednika... ║ 4° Ukoliko je potez pobedonosni u datoteku se, pored koordinata stavlja ║ i kod 255. ╚════ ...čime je nepotrebna stavka 4. Razumete li me? ║ 9° Vizuelni prikaz toka partije je obavezan ! Kako bi inače ja video da li ║ je do pobede došlo ili ne. Program, kada odigra potez koji nije ╚════ Ne znam na šta misliš, da li da program prikazuje tok partije ili nešto drugo. Ako se napravi mediator, on će vršiti vizuelni prikaz na ekranu. ║ 13° Na turniru učestvuju SAMO programi korisnika SEZAM-a. Ništa sa Mreže ║ nije dobrodošlo. ╚════ Shvatite ovo kako hoćete, ali mene neće biti na sistemu za desetak dana, pa se nadam da ću, kao "bivši" Sezamovac imati pravo da pošaljem svoj program, valjda sam zaslužio? ;))
algoritmi.291 kenza, -> #288, kajko
>> BTW: Da li da opterecujemo conf ili da formiramo grupu, posto temu Ma, u conf. Ne verujem da je grupa dovoljno velika da primi sve zainteresovane.
algoritmi.292 embe, -> #288, kajko
Da ne citiram poruku, ovo je u vezi sa turnirom programa u iksoksu. Kao sto sam najavio u poruci 1.289 zavrsio sam "beta" verziju programa-kontrolora (odn.moderatora meceva) Uz program saljem i takmicara (uslovno receno jer ovaj moze da pobedi samo sebe) ali moze da posluzi za testiranje i kao sablon za pravljenje vasih takmicara. Sve sugestije su dobrodosle i voleo bih da cujem vase misljenje. Pozdrav, Milan. xox2121.zip
algoritmi.293 nenad, -> #288, kajko
> 3° Programi razmenjuju poteze preko datoteke 'POTEZ.XOX'. Ukoliko > je datoteka prazna ili ne postoji, to znači da program igra prvi. > Kad odigra potez, briše sadržaj datoteke 'POTEZ.XOX' i u njega > smešta svoj potez. > Koliko još datoteka treba samom programu, nije bitno. To je njegova > interna stvar gde će on u međuvremenu držati podatke o partiji. Predlažem ti da uvedeš obavezu da oba programa prave log partije u svoj fajl kao bi posle mogao da uporediš logove i na lak način preduprediš bilo kakva varanja, samim tim i automatizuješ potpuno celo takmičenje. > BTW: Da li da opterećujemo conf ili da formiramo grupu, pošto temu > u okviru nekog conf-a ne verujem da ćemo dobiti ? Nema razloga da se priča ne nastavi ovde. Lepo bi bilo kada bi se uveo i uslov da se nakon turnira prezentiraju sors-ovi, i kao potvrda autentičnosti programa, i kao mogućnost da jedni od drugih nešto naučimo.
algoritmi.294 kajko, -> #289, embe
>> >> 3° ... >> Obavezno se mora predvideti da program-koordinator odredjuje imena >> fajlova koje ce programi-takmicari koristiti. Njihova imena ce Apsolutno se slažem. >> >> 4° Ukoliko je potez pobedonosni u datoteku se, pored koordinata stavlja Do tog zaključka sam i sam došao dok sam razmišljao o masterisanju. Moraće biti gadnih tumbanja po onim pravilima :) >> >> 8° Vremensko ogranicenje za potez je maksimalno 15 sekundi (Intel 166). Vremensko ograničenje neće da bude... >> >> 9° Vizuelni prikaz toka partije je obavezan ! Kako bi inace ja video da li Ispravno. >> Takav koordinatorski program sam gotovo doveo do kraja. Jos mi je Pošto ga ti već radiš, ja se neću bakćati s njim. Kad ga pogledam, javiću... ===== Moram da priznam da su mi u trenutku pisanja pravila, ona izgledala sasvim logično, ali kad je na red došlo i pisanje programa, kako takmičara, tako i mastera, uvideo sam velike omaške moje male mane, brzopletosti. Sugestije su više nego opravdane, so, hvala... KAJKO
algoritmi.295 kajko, -> #290, space.ace
>> Shvatite ovo kako hoćete, ali mene neće biti na sistemu za desetak dana, >> pa se nadam da ću, kao "bivši" Sezamovac imati pravo da pošaljem svoj >> program, valjda sam zaslužio? ;)) Opet moja brzopletost... Naravno da je svim dobronamernicima dozvoljeno da učestvuju. Samo sam hteo da predupredim neke, nama znane, malverzacije... I na kraju... Dobrodošao si i ti i tvoj program... KAJKO
algoritmi.296 kajko, -> #292, embe
>> Sve sugestije su dobrodosle i voleo bih da cujem vase misljenje. Program je 'boli glava' kao i pravila koja nameće. Ja ga predlažem za standard. Hvala... PS. Takmičenje će se izvoditi na njemu i po pravilima koja on nameće. KAJKO
algoritmi.297 kajko, -> #292, embe
>> Sve sugestije su dobrodosle i voleo bih da cujem vase misljenje. >> Prilagodio sam svog takmičara (naravno, ako sme da učestvuje u turniru) prema pravilima Master-programa, i radi super... Imam par sugestija za master program: 1° Pored naziva igrač X i O uvesti nazive programa. Na primer 'Igrac X: XOX.EXE' i 'Igrac O: KAJKO.EXE' 2° Nisam primetio neki LOG fajl. Mislim, pošto master vodi računa o igri (proglašava pobednika, detektuje remi, ...) bilo bi lepo da on snimi ceo tok partije u datoteku. Na primer: XOX.EXE KAJKO.EXE ==================================== 001: 10 07 09 07 002: 09 08 08 07 ¨¨¨¨¨¨¨¨¨¨¨¨¨¨¨¨¨¨¨¨¨¨¨¨¨¨¨¨¨¨¨¨¨ XXX: 10 10 ==================================== Pobeda igraca X: XOX.EXE 3° Pošto se potezi oba igrača vide na ekranu, uvesti neke prekidače u sam master kojim se može reći da odigrava poteze bez pauze (osim kad objavi pobednika) ili, bar, sa pauzama posle odigranog poteza oba programa. Nadam se da će moje sugestije biti uzete u razmatranje. Vrlo mi je bitan izgled LOG fajla, jer ću na osnovu njega da završim program koji će biti Registrator takmičara. Naime, program će registrovati takmičare, samim tim i potreban broj kola za sistem svako_sa_svakim, izvlačiti parove, pozivati Master za odigravanje partija, deliti bodove, praviti tabelu, generisati izveštaje koji će biti slati ovamo, ... i td. Kad budem znao izgled LOG fajla, završiću program i šutnuti ga ovde na razmatranje i sugestije. KAJKO
algoritmi.298 kajko, -> #293, nenad
>> uveo i uslov da se nakon turnira prezentiraju sors-ovi, i kao >> potvrda autentičnosti programa, i kao mogućnost da jedni od >> drugih nešto naučimo. >> Programi takmičari će sigurno iši u conf, ali što se tiče sors-a, to je LIČNA stvar samog autora programa, i ja tu ne mogu ništa. Sors mog programa će, svakako, ići uz moj program. KAJKO
algoritmi.299 obren, -> #220, isekulovic
> Dve za opstinu, 0 za muske 5 (!) za zenske, dve cifre redni broj i > jedna kontrolna cifra. Moj matični broj je xxxxxxx782848, dakle nema nigde te nule koju pominješ?
algoritmi.300 embe, -> #297, kajko
>> Imam par sugestija za master program: >> >> 1° Pored naziva igrac X i O uvesti nazive programa. >> Na primer 'Igrac X: XOX.EXE' i 'Igrac O: KAJKO.EXE' Uradjeno. >> 2° Nisam primetio neki LOG fajl. Mislim, posto master vodi racuna >> o igri (proglasava pobednika, detektuje remi, ...) bilo bi >> lepo da on snimi ceo tok partije u datoteku. Na primer: >> >> XOX.EXE KAJKO.EXE >> ==================================== >> 001: 10 07 09 07 >> ¨¨¨¨¨¨¨¨¨¨¨¨¨¨¨¨¨¨¨¨¨¨¨¨¨¨¨¨¨¨¨¨¨ >> XXX: 10 10 >> ==================================== >> Pobeda igraca X: XOX.EXE LOG fajl nisam stigao da zavrsim za prvu verziju , jer sam zurio da dovedem u red funkcionalnost programa. LOG fajl je sada uradjen. LOG faj sadrzi sledece informacije: ko je na potezu, kako se poziva (sa kojim argumentima) program takmicar, sta je procitano iz fajla za razmenu poteza i koji potez je odigran. Naravno tu su i poruke ishodu meca i o greskama (i o vrsti greske) jer pored pracenja toka partije LOG fajl treba da sluzi i za "debug", pa sam tu "nakrkao" sve sto je meni bilo od pomoci pri pravljenju mog programa-takmicara. Naravno izmene su moguce >> 3° Posto se potezi oba igraca vide na ekranu, uvesti neke prekidace >> u sam master kojim se moze reci da odigrava poteze bez pauze >> (osim kad objavi pobednika) ili, bar, sa pauzama posle odigranog >> poteza oba programa. Pravo je cudo kako mislimo o istim stvarima. Uradjeno i ovo. Sada postoje tri brzine : spora - zahteva pritisak na tastaturu posle svakog poteza (default), srednja - odigrava bez prekida sa pauzama od oko 1 sec, i brza brzina - nesto brza od srednje. >> Nadam se da ce moje sugestije biti uzete u razmatranje. Mnogo hvala. Sve je usvojeno. >> Vrlo mi je bitan izgled LOG fajla, jer cu na osnovu njega da zavrsim >> program koji ce biti Registrator takmicara. Naime, program ce >> registrovati takmicare, samim tim i potreban broj kola za sistem >> svako_sa_svakim, izvlaciti parove, pozivati Master za odigravanje >> partija, deliti bodove, praviti tabelu, generisati izvestaje >> koji ce biti slati ovamo, ... i td. ... i da kuva, pere ves, pegla ::))) Pa sta ces onda ti da radis? Samo da stisnes dugme ? :))))) Sto se tice LOG fajla i svih gore navdenih izmena, sve je ugradjeno, ostala mi je nezavrsena samo sitna kozmetika. Program saljem do otvaranja birackih mesta :) Sto se tice toga da li moze tvoj program da ucestvuje - naravno da moze. Jednostavan postupak za legalizaciju celog takmicenja je sledeci: PRE pocetka takmicenja, sve programe takmicare ubacis u jednu sifrovanu ZIP arhivu (dobro je sifruj - ovde su veliki hakeri :)) - sa puno malih i velikih slova), koju posaljes ovde u konferenciju. Kada se takmicenje zavrsi, u konferenciji objavis sifru. (Sifruje se zato da takmicenje ne izgubi neizvesnost.) Ovime se pruza mogucnost naknadne provere rezultata meceva - prema tome nece biti nikakvih nepravilnosti.
algoritmi.301 embe,
Evo master programa (programa-kontrolora) XOX2121 v.2.1b Sve sugestije od strane KAJKA sam uvazio. U arhivi se osim glavnog programa XOX2121.EXE i fajlova neophodnih za njegov rad, nalazi i jedan program takmicar (XOX.EXE) skromnih mogucnosti, koji je tu samo radi testiranja. Obavezno procitati uputstvo koje se nalazi u fajlu README.1ST a takodje prvi put startovati XOX2121 /? ,da bi se pogledao spisak novododatih opcija. Sve sugestije su dobrodosle, a takodje i ako ima nekih problema u radu ovog programa ili u radu ovog programa sa vasim programima- -takmicarima tu sam. Evo XOX2121 v.2.1b i neka vam je sa srecom. xox2121.zip
algoritmi.302 snemcev, -> #299, obren
>> Moj matični broj je xxxxxxx782848, dakle nema nigde te nule koju >> pominješ? Izvini što idem preko tvoje poruke, al' mi je dobro poslužila za ilustraciju. Redni broj upisa, koji je u matičnom broju posle dvocifrene šifre opštine (ono 284 u tvom matičnom broju), je trocifren i za mušku decu počinje od 001, a za žensku decu počinje od 501. Ako je taj redni broj manji od 500, dete je muško, a ako je veći od 500, dete je žensko. Simple as that.
algoritmi.303 kajko,
Nakon dugotrajne razmene mišljenja i sugestija došlo je do značajnog pomaka na bolje u vezi turnira XOX. Pravila za učešće na I XOX turniru su znatno izmenjena, so, čitajte: 1° Igra se na polju 21x21 sa 5 u nizu. 2° Redovi i kolone moraju biti markirani brojevima i to: gornji levi ugao je (1,1), a donji desni (21,21). 3° Program mora biti DOS EXE ili COM program. Što se tiče veličine, ne bi trebalo da prelaze veličinu od 300Kb !! Programski jezik nije bitan. 4° Mora da se obezbedi prenošenje argumenata sa komandne linije. Argumenata ima ukupno četiri (4) - Prvi argument je ime fajla koji se koristi za smeštanje odigranog poteza. Taj fajl treba da bude tekstualni (ASCII) fajl. Potez se zapisuje u obliku dva cela broja razdvojena najmanje jednim spejsom (blankom). Fajl treba da sadrzi samo jedan jedini potez. Jos jedan uslov za taj fajl je da se zatvori kada se u njega upiše potez (da bi master program (XOX2121) mogao da ga otvori i procita njegov sadrzaj). Potez se označava sa dva broja koji (svaki od njih) mogu biti od 1 do 21. Šta je vrsta a šta kolona, odlučuje sam program. - Drugi argument je ime fajla koji sam program-takmičar koristi za svoje interne potrebe (da pamti poslednju poziciju na tabli, svoje i tuđe poteze i šta god joć). - Treći i četvrti argument predstavlja poslednji odigrani potez protivnika. To su dva cela broja opsega od 1 do 21. Takođe, šta je vrsta a šta kolona određuje sam program-takmičar. Bitno je da je to usvojeno isto i za ulaz i za izlaz. Ukoliko je u pitanju prvi potez u partiji treći i četvrti argument (poslednji odigrani potez protivnika) izostaju, tj. program-takmičar se poziva samo sa prva dva argumenta: Recimo da se program takmičar zove XOX.EXE Program-kontrolor ce ga u slucaju da je u pitanju prvi potez u partiji pozvati otprilike ovako: XOX OUT.TXT TMP001 a zadatak XOX.EXE programa je da prepozna da je u pitanju prvi potez, odluči gde će da igra, zapamti novonastalu poziciju, snimi je u fajl TMP001 i taj potez snimi u ASCII fajl OUT.TXT i naravno zatvori ga. Svako sledece pozivanje ovog programa vršiće se sa joć dva argumenta, npr. ovako: XOX OUT.TXT TMP001 12 9 Naravno da ime fajla za cuvanje pozicije ostaje isto tokom cele partije. Brojevi 12 odnosno 9, predstavljaju poslednje odigrani potez protivnika. Oni su iskontrolisani i ispravni. Zadatak XOX.EXE je da prvo učita staro stanje na tabli, registruje potez protivnika, odluči se za svoj potez, snimi novo stanje na tabli, a svoj potez odstampa u fajl OUT.TXT Napomena: program-takmicar moze da otvara i zatvara samo fajlove sa menima koje je dobio od programa-kontrolora. 5° Vremensko ograničenje za odigravanje poteza ne postoji. Ukoliko se program zaglavljuje, automatski gubi meč. 6° Vizuelni prikaz toka partije 'nesme da bude'. 7° Igra se po principu svako sa svakim i to 6 (šest) partija. Prvobitna ideja je bila da se igra na tri dobijene partije, ali bi tada program koji igra prvi, bio u prednosti. Ovako će svaki program imati podjednake šanse, jer 3 (tri) puta igra prvi i 3 (tri) puta igra drugi. 8° Svaki korisnik može poslati samo jedan program. 9° Rezultati će ići ovako: trenutna tabela u poruku, a podaci o svakom meču u datoteku uz poruku. Rok za slanje programa za I XOX turnir je 01.10.1997. Programe šaljete meni na MAIL. Pre početka turnira, svi programi koji će u njemu učestvovati će ići u conf spakovani pod šifrom. Nakon turnira, zajedno sa zaključnom tabelom ići će i ključ arhive, tako da svako može da proveri rezultate na svom računaru. Takmičenje će se izvoditi na EMBE-ovom programu za masterisanje (poruka 300) te predlažem da ga svi zainterosovani za učešće na turniru skinu. Uz njega dolazi i dokumentacija koje je i više nego dovoljna. Neke delove iz dokumentacije sam prekucao (COPY-PASTE) ovde za slučaj da nisu svi skinuli program. Samim tim, izvinjavam se EMBE-u za citiranje bez pitanja. Ostaje otvoreno pitanje bodovanja programa. Ukoliko nemate zamerki, usvoio (nadam se da se tako piše !?) bih način bodovanja iz takmičenja PCROBOTS. I tabela bi bila identična. >> >> partija, deliti bodove, praviti tabelu, generisati izvestaje >> >> koji ce biti slati ovamo, ... i td. >> >> ... i da kuva, pere ves, pegla ::))) >> Pa sta ces onda ti da radis? Samo da stisnes dugme ? :))))) Ja ću da se skoncentrišem na same programe i igru koju pružaju. Komentari o svakom programu i odigranoj partiji će biti obimni. Bilo bi vrlo mukotrpno ispuštati olovku i pritiskati dugme za sledeći potez (u drugoj ruci mi je obično cigareta). Verujem (a vi me razuverite) da će se tokom turnira iskristalisati programi koji zavređuju pažnju, dok še drugi tu biti samo za gaženje i prepuštanje bodova :). Takve mečeve ću vrlo malo komentarisati :>. PS: Poruka je malo duža, ali vredi... KAJKO
algoritmi.304 embe, -> #303, kajko
>> Takmicenje ce se izvoditi na EMBE-ovom programu za masterisanje >> (poruka 300) te predlazem da ga svi zainterosovani za ucesce na >> turniru skinu. Uz njega dolazi i dokumentacija koje je i vise nego Mala ispravka, program se nalazi u poruci 301. >> Rok za slanje programa za I XOX turnir je 01.10.1997. >> Programe saljete meni na MAIL. Pre pocetka turnira, svi programi koji Moj takmicar je vec gotov ali sacekacu malo do njegovog slanja (da ne budem bas prvi). Jedna me stvar interesuje, a to je koliko ljudi stvarno namerava da napravi svog takmicara? Ne bih da baksuziram ali nisam bas veliki optimista. Najgore bi bilo da nas dvojica odigramo privatni turnir u javnoj konferenciji. Mozda bi trbalo da se ovaj turnir malo izreklamira u konferenciji IGRE ? Na kraju krajeva ovo i jeste igra.
algoritmi.305 kajko, -> #304, embe
>> Jedna me stvar interesuje, a to je koliko ljudi stvarno namerava >> da napravi svog takmicara? Ne bih da baksuziram ali nisam bas >> veliki optimista. Najgore bi bilo da nas dvojica odigramo privatni >> turnir u javnoj konferenciji. Znas kako je... Na početku je ideja naišla na veliki odjek, kao i mnoge druge. Ali, kad dođe na red slanje takmičara onda bude ono: "Nisam stigao, ali...", "...imam ispit, ali...", "...sa zanimanjem ću pratiti...", ... Nadam se da neće biti tako... >> Mozda bi trbalo da se ovaj turnir malo izreklamira u konferenciji >> IGRE ? Na kraju krajeva ovo i jeste igra. >> Ideja nije loša, već urađeno !!! KAJKO
algoritmi.306 embe,
Evo jednog takmicara za igru XOX2121. Ovo nije prijava za takmicenje. Pravi takmicar ceka zadati rok da bude poslat. U medjuvremenu, igrajte XOX2121 sa ovim programom i testirajte svoje programe u borbi sa njim. karpov.arj
algoritmi.307 tomcat, -> #304, embe
> Jedna me stvar interesuje, a to je koliko ljudi stvarno namerava > da napravi svog takmicara? Ne bih da baksuziram ali nisam bas > veliki optimista. Najgore bi bilo da nas dvojica odigramo privatni Ja sam uveliko zainteresovan :) Sto se propozicija tice, predlazem da se dozvoli programima interno koriscenje dodatnog fajla. Ja na umu imam ideju da program uci na greskama i za to je potrebno da snima analize odigranih partija kako bi ih mogao koristiti. Pozdrav, ................................. tomcat@galeb.etf.bg.ac.yu http://galeb.etf.bg.ac.yu/~tomcat
algoritmi.308 embe, -> #307, tomcat
>Ja sam uveliko zainteresovan :) >Sto se propozicija tice, predlazem da se dozvoli programima interno koriscenje >dodatnog fajla. Ja na umu imam ideju da program uci na greskama i za to je >potrebno da snima analize odigranih partija kako bi ih mogao koristiti. U principu (ali samo u principu) nemam nista protiv ovoga, ali mislim da neces imati ama nikakve vajde od "ucenja na greskama". Razlog je sledeci: Mec izmedju dva takmicara traje 6 partija. Za to vreme tvoj takmicar (bez uvrede :)) nece nista "nauciti" (kako ovo blesavo zvuci) jer je to isuvise malo partija da bi se osetio "napredak" na osnovu "iskustva". Sledecem takmicaru moraju se dati isti uslovi kao i prethodnom, sto znaci da tvoj takmicar opet ulazi u mec "bez iskustva". Znaci fajl sa "iskustvom" mora da se obrise. Znaci, tvoja ideja je neprimenljiva za turnir. Druga je stvar da tvoj takmicar stigne na turnir sa "iskustvenim fajlom" ali taj fajl se ne ne sme menjati u toku turnira zbog principa ravnopravnosti svakog takmicara. To znaci da taj fajl moses samo da citas a ne da pises u njega. A ako stvari tako stoje, onda se taj fajl sa "zapecacenim iskustvom" moze ugraditi u EXE i onda prestaje potreba za nekim drugim fajlovima.
algoritmi.309 kajko, -> #308, embe
>> U principu (ali samo u principu) nemam nista protiv ovoga, ali mislim >> da neces imati ama nikakve vajde od "ucenja na greskama". Razlog je Što se tiče 'učenja na greškama' ideja nije loša. Voleo bih da vidim taj program, ali kao što reče EMBE, taj program je neupotrebljiv za turnir. Svi programi na turniru su u jednom košu, stoga, moraju biti ravnopravni. Ako možeš nešto da ga 'naučiš' do početka turnira, možeš. Na turniru može da bude samo program, bez pratećih datoteka. To implicira ugradnju 'pameti' u sam EXE (ili COM) fajl. Bliži se krajnji rok za slanje programa koji je 01.10.1997. godine. Požurite... KAJKO