Fórum: Algoritmusok

Szeretnél hozzászólni? Jelentkezz be.

2005-07-22 02:21:48

Egy-két apróságot hadd szóljak hozzá.

Egy összeeresztő programot én valamilyen szkript nyelven írnék (tcl, perl stb.), úgy sokkal egyszerűbb külső processzeket futtatni. Pl. az S. 8. feladatban az amőba programokat egy TCL szkripttel eresztettem össze.

Linuxban a chroot parancs használatával elérheted, hogy a program egy könyvtáron kívül ne lásson semmit.

Kliens-szerver konstrukcióról nem beszélnék. A program egy ciklusban kiírja ki a saját lépését, majd beolvassa az ellenfél lépését. Mindez megy a standard be- és kimeneten is.

Az informatika pontverseny tapasztalatai szerint a többség Pascalban vagy Delphiben írja a programjait, egy kisebbség C-ben vagy C++-ban. Így hát nem nagy megszorítás, ha azt mondod, hogy a programokat Pascal és C/C++ nyelveken lehet írni, Linuxon FreePascal-lal és GCC-vel fordítod. Amire oda kell figyelni, hogy a protokolt pontosan elő kell írni, mert lesznek, akik vicces karakterek kiírásával letörlik a képernyőt vagy más szövegeket is kiírnak. (Nézd meg az S-jelű feladatok szövegét...)

Előzmény: [20] 2501, 2005-07-21 22:49:48

[22] Atosz	2005-07-22 00:11:11
Én az ilyen programot nem "ravasznak" hanem csalónak nevezném... Az időlimitet én úgy oldanám meg, hogy minden programot lefuttatnék egy teszt 1000 darabos számötösön, és ha nem tudja generálni 1000 adat átvizsgálása után a lépését max. t időn belül, akkor nem indulhat. Egyébként ha minden program egy az aréna által kiosztott fájlban dolgozik, akkor nem kezelhetik egymásét lépés előtt (hiszen nem tudják a fmásik fájl nevét és helyét), illetve ha a fájlrendszer különböző pontjain vannak, akkor nem tudják egymást futtatni sem. Ebben az esetben természetesen az aréna pakolgatja a számötösöket egyik fájlból a másikba. Azt nem tudom megítélni hogy indítás-fájlolvasás-döntés-fájlírás...aréna műveletek...(másik progi ugyanez) és mindez ezerszer egymás után mennyi idő lehet. Én úgy gondolom, hogy egy ilyen program döntési része nagyon gyors lesz (hiszen nem kell szerteágazó struktúrákat nagy mélységben elemeznie mint egy sakkprogramnak), a fájlműveleteket pedig nem tudom megítélni. Én igazából amellett kardoskodnék, hogy a csataprogik írása legyen minél egyszerűbb - már olyan értelemben, hogy ne kelljen különböző op.rendszereknek, programnyelveknek, kommunikációs protokolloknak megfelelni (különben én kiesek...) Lehet, hogy kipróbálok egy olyat, hogy elkészítek egy egyszerű programot, ami véletlenszerűen generálja a számötösöket, beírja egy fájlba, illetve induláskor meg kiolvassa a már ottlévőket, illetve egy másikat, ami mindezt lefuttatja 1000-szer egymás után. Várom a tovább gondolatokat... Minden jót, Atosz!
Előzmény: [20] 2501, 2005-07-21 22:49:48

[21] 2501

2005-07-21 23:00:23

A kliens-szerver dolgot még átgondolom, hátha megoldható szabványos ki-/bemenettel (úgy rémlik, a streamek win alatt is egész normálisan működnek).

Az előzőben TCP/UDP-t írtam UDP/IP helyett - fáradok...

Előzmény: [20] 2501, 2005-07-21 22:49:48

[20] 2501

2005-07-21 22:49:48

Egyelőre a specifikáció elkészítésében próbálok segédkezni, és amikor már teljesen tiszta, majd eldöntöm, hogy vállalom-e.

Néhány gondolat:

Időlimit szükséges.

Az adatrejtés egyáltalán nem triviális. Egy menetben A és B küzdenek egymás ellen. Ha A "ravasz", és lefuttatja B-t, akkor megtudhatja, hogy B mit fog "lépni", tehát könnyedén legyőzheti. Még nagyobb a baj, ha mindketten "ravaszak". Ezért valahogyan meg kell akadályozni, hogy elérhessék egymást a fájlrendszerben.

Nem csekély időveszteséget jelent a futtatós-megszakítós eljárásnál, hogy a programokat minden menethez újra be kell tölteni, újra kell indítani; újra paraméterként kell adni nekik, vagy fájlból újra be kell olvasniuk az előző menetek adatait. Ebből a szempontból előnyösebb lenne egy kliens-szerver felépítés, ahol a soron következő 2 program csatlakozik az arénához, és megszakítás nélkül nyomja végig a meneteket. Ez szükségtelenné teszi például a fileok használatát, illetve lehetetlenné teszi az egymás futtatásával történő ügyeskedést. Hátránya viszont, hogy jelentősen megnehezítheti a versenyző-programok készítését. (A kliens-szerver kommunikáció megvalósítására eszembe ötlő lehetőségek - TCP/IP, TCP/UDP, pipe-ok, memory-mappelt fájlok, közös DLL használata - ugyanis mind erősen programnyelv vagy operációs-rendszer függőek, sajnos.) Esetleg megoldást jelenthet, ha a népszerű programozási nyelvekhez a kommunikációs protokollt implementáló rutinkönyvtárakat készítünk.

Előzmény: [19] Atosz, 2005-07-21 21:48:21

[19] Atosz

2005-07-21 21:48:21

Szia!

Nagyon örülök, hogy vállalnád, de csak akkor tedd ha biztosan el tudod készíteni. Az egyik alapelv, amire gondoltam, hogy a versenyprogramok bármilyen programnyelven készülhessenek, ezért valahogy szabványosítani kell őket, vagy futtatható fájlok legyenek, vagy C forráskódok, vagy assembly kódok vagy bármi, amit az aréna-program kezelni tud. Természetesen egy program ahhoz, hogy taktikázni tudjon, szükség van az előző összes számötösre, hogy azt vizsgálhassa és az alapján hozhasson döntést a következőről. Talán az lenne a legszerencsésebb, ha ezek a sorba érkező számötösök egy fájlba kerülnének be, amit a programok bemenetként is elérnek és ez a fájl lenne a játszma jegyzőkönyve is egyben. Igazából az aréna csak ütemezi a programokat és dönt, hogy ki nyert. Egyébként bármilyen ötletet bedobhatsz (bedobhattok) mert én nem vagyok programozó, csak hobbi-szinten, de úgy gondolom, hogy egy versenyprogramot el fogok tudni készíteni. A lényeg talán az, hogy fixen le kell rögzíteni (szabványszerűen), hogy a programok hogyan adják ki az adatokat és hogyan kapják meg az ellenfélét. Szerintem egy versenyző több programmal is nevezhetne, amelyek különböző taktikával dolgoznak. Az arénának fel kellene készülnie arra, hogy van mondjuk 8-15 program és azok között egy körmérkőzést lebonyolít. Egy csata (mondjuk 1000 számötössel) néhány másodperc és akár az is lehetne, hogy ha a különbség elegendően kicsi (mondjuk 50 alatti), akkor döntetlen legyen a parti. Jöhetnek az ötletek, gondolatok...

Minden jót, Atosz!

Előzmény: [18] 2501, 2005-07-21 15:57:05

[18] 2501

2005-07-21 15:57:05

Én hajlandó lennék megírni az arénát, először GNU/Linux alá (bár a processzindításnak még utána kell néznem).

Jól értem, hogy a programok megkapnák az előző menet(ek) számötöseit (fájlban vagy szabványos bemeneten, esetleg parancssori paraméterként)? Vagy csak az előző menet számötösét?

(Esetleg azt is lehetne, hogy csak annyit tudnak meg, hogy mennyivel nyertek/vesztettek, vagy csak azt, hogy nyertek/vesztettek?)

Előzmény: [17] Atosz, 2005-07-21 15:41:17

[17] Atosz

2005-07-21 15:41:17

Az számötösök első, második,... ötödik számait hasonlítjuk össze és ez alapján nyer valaki.(első az elsővel, második a másodikkal, stb...) A 25,0,0,0,0 legyőzhető akár egy 21,1,1,1,1 -el is 4:1-es gólkülönbséggel. Persze ez csak akkor lenne könnyű, ha tudnánk előre...

1000 partival a véletlen hatásokat lehet valamennyire kiküszöbölni, mert bármely számötös legyőzhető. Itt egyedül az vezethet eredményre ha kifigyeljük a már generált ötösökből, hogy milyen taktika alapján készíted el a számaidat.

Előzmény: [16] Hajba Károly, 2005-07-21 14:37:12

[16] Hajba Károly

2005-07-21 14:37:12

Ha jól érzem, akkor a sorrend is lényeges, azaz ugyanazon számokkal, de más sorrendben, akár más eredmény is lehetséges.

Példáidban csak egyjegyű számok vannak, de elvileg lehetne akár 25-0-0-0-0 a leosztás is? Természetesen tisztában vagyok vele, hogy ez biztos vesztő sor. :o)

Előzmény: [15] Atosz, 2005-07-20 13:05:31

[15] Atosz

2005-07-20 13:05:31

Sziasztok!

Egy pici versenyre szeretnék invitálni mindenkit, aki amatőr szinten tud programozni és kedveli a matekot! Olyan programot kellene készíteni, mely előállít 5, 0 vagy annál nagyobb egész számot úgy, hogy összegük 25 legyen. Ez a számötös mérkőzik a másik program számötösével, és az nyer akinek több helyen van nagyobb száma. Pl. a 3,4,11,0,7 számötös és a 6,6,6,1,6 közül az utóbbi nyert és kap 1 pontot. Nyerő ötös nincs! Bármelyik számötösnél van jobb, körbeverések is igen könnyen lehetségesek. (pl.: 7,1,8,8,1 9,3,7,2,4 1,6,6,6,6) Két program 1000-szer csap össze (mindig újabb számokat generálva) és ez alapján dőlne el, hogy melyikük az erősebb. A nyerő taktika az ellenfél taktikájának kifigyelése lehet! Keresnék valakit, aki leprogramozza az "arénát" azaz készítene egy olyan programot, ami két .exe kiterjesztésű, bármilyen nyelven megírt programot összecsapat egymással 1000-szer és eldönti melyik program győzött. Ha megvan az "aréna" írója, akkor kifinomítjuk a pontos részleteket és kiírunk egy elkészítési határidőt, illetve a verseny napját. Várom a jelentkezéseket, illetve az egyéb ötleteket, hozzászólásokat! Minden jót, Atosz!

[14] lgdt	2005-06-23 16:37:19
ne is gondolkozzatok tovább, NP-teljes. :-D

[13] lgdt	2004-12-31 17:34:13
kezdőpont - ahova nem mutat nyíl. az a kérdés, hogy a kezdőpontok milyen színűek. végpont - ahonnan nem mutat nyíl.

[12] Csimby	2004-12-30 22:33:14
Ha valahova nem mutat nyíl, akkor az milyen színű? És mit nevezel végpontnak, olyan pontokat ahonnan nem indul nyíl?
Előzmény: [11] lgdt, 2004-12-30 20:54:50

[11] lgdt

2004-12-30 20:54:50

Egy irányított gráf pontja akkor és csak akkor piros, ha csak kék pontból mutat rá nyíl. Más színt nem használunk. Csak a végpontok színét ismerjük. Egy hatékony algo kéne a kezdőpontok beszínezéséhez (elég, ha egy megoldást talál).

Nagyon sokat gondolkodtam már rajta, de csak exponenciális futásidejű algo-t találtam. NP-teljes lenne? De ha nem az, akkor meg hogy a 111110100101001010111010 kell? :(

Nem mondom, hogy 101110100101010100101010tok el vele annyi időt, mint én, de legalább bebizonyíthatnátok, hogy nincs jobb, mint a brute force.

Tkp elég lenne egy lassú módszer, amivel egy adott gráfhoz lehet gyors algot találni (és azzal az algoval megetetni a színeket).

[10] Csimby	2004-12-01 18:24:19


Előzmény: [8] Aerdna, 2004-12-01 17:40:42

[9] SAMBUCA

2004-12-01 18:16:01

Hi Aerdna!

y⁶=x⁴-x⁶-t csak [-1,1]-en kell abrazolmi, mert ekkor lesz x⁴-x⁶ nagyobb, mint 0. Legyen a=x⁴-x⁶, ekkor a=y⁶, igy $y=\pm \root6\of{a}$ . Igy minden x $\in$ [-1,1]-hez megvannak az y-ok mar csak abrazolni kell. Tenyleg pillango lesz.

ui. Maple: plot({(x^4-x^6)^(1/6),-(x^4-x^6)^(1/6)},x=-1..1);

SAMBUCA

Előzmény: [8] Aerdna, 2004-12-01 17:40:42

[8] Aerdna

2004-12-01 17:40:42

Ti milyen algoritmust irnátok ennek a függvényenek az ábrázolásához? (y)6=(x)4-(x)6 Ezek a 6,4,6-dik hatványon vannak

Pillangónek kell elvileg a képének lenni :) Nekem nem jött össze :(

[7] jonas

2004-11-26 20:37:40

(lehet ezzel a TeX-el értelmesen forráskódot formázni?)

Szerintem nem. Nekem legalabbis nem sikerult tobb szokozt berakni egymas utan, csak akkor, ha nemelyik nemtoro szokoz (\xa0).

Előzmény: [6] lgdt, 2004-11-26 20:08:35

[6] lgdt	2004-11-26 20:08:35
az 1. feladathoz. a legnagyobb növekvő rész kezdetének a címe az EDI-ben lesz, a mérete pedig az EDX-ben. (lehet ezzel a TeX-el értelmesen forráskódot formázni?)

Előzmény: [1] V. Dávid, 2004-10-03 23:39:32

[5] Edgar	2004-10-17 17:29:52
Hogy írhatunk hatékony algoritmust az n-edrendű körosztási polinom kiszámítására? És ha az összes legfeljebb n-edrendűre szükség van?

[4] Hajba Károly

2004-10-12 16:21:56

Igen. De ugyanez vonatkozik A-ra is, így ha A-ra kifejezem, akkor $D=\big(\frac{10^n}{2}\big)^2-B^2+B \ge0$ , s innen $10^{n-1}-1<B\le\frac{10^n}{2}$ . Azaz fele annyit esetet sem kel megvizsgálni.

Előzmény: [3] Sirpi, 2004-10-12 15:03:10

[3] Sirpi	2004-10-12 15:03:10
Mivel n éppen A jegyeinek számát jelenti, így az általad írt képlet éppen egy másodfokú egyenlet B-re. Emiatt elég sorban nézni az A-kat, pár másodperc alatt szerintem 8+8 jegyig is végig lehet rágni az összes esetet.
Előzmény: [2] Hajba Károly, 2004-10-12 14:54:28

[2] Hajba Károly

2004-10-12 14:54:28

3. feladat:

Segítsünk Sambucának! Vajon milyen algoritmussal oldhatta meg az "Érdekes matekfeladatok" topik 104. feladatát? Azaz írjunk egy hatékony eljárást a A²+B²=A*10ⁿ+B egyenlet megoldásainak megkeresésére, ahol (A,B) $\in$ N⁺ és 10^n-1-1<(A,B)<10ⁿ.

[1] V. Dávid

2004-10-03 23:39:32

Szintén ága a logikus problémamegoldásnak. A jó algoritmus kifejlesztése hasonlít egy matematikai feladat megoldásához, mégis más egy kicsit.

1. feladat: Írj hatékony algoritmust egy tömb leghosszabb növekvő részsorozatának megtalálásához.

2. feladat: Egy kör alakú asztal körül n db ember ül. Körbejárva minden m-ediket kizárjuk, és a későbbi számlálásba nem számítjuk bele. Az kizárt emberek sorszámából alkotott sorozatot (n,m)-Jozefusz-permutációnak hívjuk. (Pl. (7,3)->(3,6,2,7,5,1,4).) Tervezz O(n lg n) idejű algoritmust (n,m) meghatározására!

[1] [2] [3] [4]

Már regisztráltál?
Új vendég vagy?