Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

Fórum: Informatika kömal

  [1]    [2]    [3]    [4]    [5]    [6]    [7]    [8]    [9]    [10]    [11]    [12]    [13]    [14]  

Szeretnél hozzászólni? Jelentkezz be.
[64] Róbert Gida2008-09-21 23:50:11

2 napja indult középiskolásoknak kiírt maratoni programozói verseny: http://hs.spoj.pl/ Középiskolásként indulókat akkor ismerik el, ha az iskola egyik tanára hitelesíti ezt a lapon.

Idősebbek versenyen kívül indulhatnak.

[63] Róbert Gida2008-06-14 16:17:25

Nem sokan neveztek be S-re, mindössze nyolcan.

Előzmény: [53] Zippo, 2008-05-08 22:01:06
[62] Engedy Balázs2008-05-31 21:31:43

Az előbbi, azaz egy billentyű egyszeri megnyomására hajtson végre egyetlen szimulációs lépést, majd jelenítse meg a változást grafikusan.

Előzmény: [61] moneo, 2008-05-31 13:59:05
[61] moneo2008-05-31 13:59:05

Van egy kérdésem a az I187-es feladathoz: lépésenkénti megjelenítés azt jelenti, hogy egy billentyű megnyomására lép tovább a program, vagy azt hogy vár két lépés közt valamennyi időt?

[59] Róbert Gida2008-05-10 23:51:48

Most találtam a Hírek rovatban: Bolyai Pályázat

Matematikai problémák megoldását várják, müködő programmal az élet nagy problémáira, Lovász László Bolyai és Wolf díjas matematikus téma javaslatai többek között:

Hogyan jutok el leggyorsabban vagy legolcsóbban az iskolába?

Hogyan lehet jó SUDOKU rejtvényt csinálni?

Hova helyezzem el a kertben a locsolófejeket?

Nem volna-e érdemes a büfében az egyik eladónak a pénzt kezelni, a másiknak az árut kiadni?

"A pályázat beküldésének határideje: 2008. szeptember 15."

Sudoku speciel példa volt az S jelűek között.

[58] Zippo2008-05-09 09:37:44

Most fejeztem be, és beadom, nyugi:)

Előzmény: [55] Róbert Gida, 2008-05-09 09:01:09
[57] Zippo2008-05-09 09:36:56

Igen, tudok róla, de azért kösz a figyelmeztetést.

Előzmény: [56] Engedy Balázs, 2008-05-09 09:31:09
[56] Engedy Balázs2008-05-09 09:31:09

Egyelőre nemhivatalosan tudok csak válaszolni, de véleményem szerint emiatt nem lesz érvénytelenítve a feladat.

Emellett szeretném felhívni a figyelmeteket, hogy ebben a hónapban két S-jelű feladatra is lehet megoldást küldeni, az ehavi S.35. mellett újból kitűztük a korábban túlságosan nehéznek bizonyult S.31. egyszerűbb változatát.

Előzmény: [54] Zippo, 2008-05-09 08:25:32
[55] Róbert Gida2008-05-09 09:01:09

Szerintem add be, ha már egyszer megoldod/megoldottad.

Előzmény: [54] Zippo, 2008-05-09 08:25:32
[54] Zippo2008-05-09 08:25:32

Ettől még pontozva lesznek a programok, nem nyílvánítják érvénytelenné a feladatot, ugye?

Előzmény: [51] Engedy Balázs, 2008-05-08 21:04:29
[53] Zippo2008-05-08 22:01:06

én még az vagyok, és pont ezt teszem:)

Előzmény: [52] Róbert Gida, 2008-05-08 21:13:24
[52] Róbert Gida2008-05-08 21:13:24

Hihetetlen, hogy milyen kevesen csinálják az S jelű példákat, mindössze nyolcan. Ha én most lennék gimnazista biztosan indulnék ebben a versenyben.

[51] Engedy Balázs2008-05-08 21:04:29

Sziasztok!

Az S.35. feladatban a példaként megadott bemenetre a helyes kimenet:

-1 1

Köszönjük az észrevételt, és elnézést kérünk a kellemetlenségekért.

[50] Zippo2008-05-08 17:39:05

a feladat nem egyenesről, hanem szakaszról beszél, de akkor is rossz, így van

[49] i2008-05-08 17:20:51

Ha az egyenesen nem szabad másik pontnak lennie, akkor viszont a példamegoldás is rossz.

[48] Zippo2008-05-08 16:59:00

na de akkor döntsék már el mit kell csinálni

Előzmény: [47] Róbert Gida, 2008-05-08 16:54:54
[47] Róbert Gida2008-05-08 16:54:54

Jogos. Lehet, hogy a feladatkitűző másra gondolt, mert viszont az igaz, hogy a szakasz által meghatározott egyenesen van egy másik nem kiválasztott pont, mert (-4,0);(-1,1);(2,2) egy egyenesre esnek, az y=(x+4)/3 egyenesen.

Előzmény: [46] Zippo, 2008-05-08 16:07:03
[46] Zippo2008-05-08 16:07:03

Lenne egy kérdésem az S35-ös feladat példájával kapcsolatban. A -1;1 pontból minden másik ponthoz húzható olyan szakasz, amin más pont nincs rajta. Akkor mért nem ez a megoldás?

[45] Róbert Gida2008-04-18 00:50:52

Érdekes, N=4-re ez már lassú, most próbáltam ki, egy perc alatt sem futott le egyetlen gridre, több, mint 1 millió cserét végrehajtva. Már az elején volt jobb választás is. Így teljesen elment a málnásba. Holott szvsz N=4-re még egy ember is meg tudja oldani.

Tényleg azt kell szimulálni, ahogy az ember lassan, de módszeresen megold egy ilyet. Azt is nézem, hogy minden sorra, oszlopra, kis négyzetre és minden betűre azt is megnézem, hogy hány helyre írhatom be oda a betűt. Ha ez adja a minimumot, akkor egy ilyet választok (és persze ezen lépek vissza a backtrackkel).

Előzmény: [44] Róbert Gida, 2008-03-29 21:44:56
[44] Róbert Gida2008-03-29 21:44:56

Valószínűleg megértenék az algoritmust: a javítás annyiban áll, hogy mindig azt az eddigi üres mezőt próbálom ki (írok be egy számot arra a mezőre), ahol a legkevesebb lehetőségem van, ezt úgy értem, hogy az adott sor, oszlop, illetve kis négyzet a lehető legtöbb számot blokkolja a mezőn, illetve, ha minden számot blokkolna, akkor visszalépek.

A leggyorsabb Sudoku megoldók egyéként ahogy emlékszem kb. 1000 feladványt oldanak meg 1 másodperc alatt 1 GHz-es gépen, régebben voltak is ilyen versenyek, hogy minél gyorsabbat írjanak.

Azért sem érdektelen a probléma, mivel ez 1 millió dolláros probléma: az nxnxnxn-es Sudoku (hagyományos: n=3) ugyanis NP teljes probléma, így egy polinomiális algoritmus rá 1 millió dollárt érne (Milleniumi probléma).

Előzmény: [43] Schmieder László, 2008-03-29 09:51:03
[43] Schmieder László2008-03-29 09:51:03

Az S.29. feladat egyik mintamegoldása valóban olyan programozási szerkezeteket és stílust tartalmazott, amit manapság nem szerencsés terjeszteni - ezt a megoldást levettük a honlapról.

A feladat visszalépéses kereséssel történő megoldását azért fogadtuk el 10 pontosnak, mert ez egy középiskolásoknak szóló tanulmányi verseny. A megoldást írók feltehetően azért nem foglalkoztak a hatékonyság kérdésével, mert az általuk írt programok egy "átlagos" sudoku feladatot másodpercek alatt megoldottak.

Annak végiggondolása, hogy melyik algoritmus kb. mennyi idő alatt végez egy bizonyos sudoku táblával - úgy gondoljuk - már egyetemi szint.

A hozzászólással tehát olyan szempontból egyetértek, hogy nem a visszalépéses keresés a "végső" megoldás, tehát a KöMaL S verseny megoldóinak is lesz majd mit tanulni egyetemen. De a hozzászólás azon részével (stílusával) nem értek egyet, hogy emiatt a versenyzők nem érdemelnék meg a maximális pontszámot.

Ha Róbert Gida tud olyan megoldást mutatni, amelyik egy "tetszőleges" sudoku táblával gyorsan végez, és az algoritmust egy informatika szakkörön elmeséli középiskolásoknak, akik azt meg is értik, akkor lehet szó arról, hogy többet várjunk el az S versenyzőktől.

Előzmény: [41] Róbert Gida, 2008-03-11 01:28:56
[42] Róbert Gida2008-03-18 21:37:02

I.180. backtrack, klasszikus alkalmazás ebben a 8 bástyás feladatban.

S.33. bfs, azaz szélességi kereséssel megtalálható a legrövidebb út ebben a feladatban, kb. 4*S*M állapot van (minden pont foka legfeljebb 4). A szélességi kereséssel optimális O(S*M) időben és tárban megoldható a feladat.

[41] Róbert Gida2008-03-11 01:28:56

A következő Sudoku feladatnak ti mennyi idő alatt találnátok meg legalább egy megoldását, és egy számítógépes program, és egy olyan program ami történetesen maximális 10 pontot kapott rá? Pontok hiányzó számot jelentenek. Ennek minden szabályos Sudoku megfejtés a megoldása (permutációval) és sor-oszlopcserékkel is még több, mint 5 milliárd megoldása van, mégsem találta meg az adott 10 pontos program egyetlen megoldását sem a gépem 1 óra alatt, de valószínűleg 1 év sem lenne neki elég. Az ok borzasztó egyszerű: gagyi a backtracking, ha valaki úgy csinálja, mint a beküldő, és sorrendben megy végig a mezőkőn. Én erre a programra 1 árva pontot nem adtam volna, már az elején is gyanús volt, hogyan lehet ilyen rövid a kód, az acm.uva-n kb 3-szor hosszabb kódot írtam a Sudoku-ra, persze nem ilyen gagyit. A Sudoku:

.........

.........

.........

.........

.........

.........

789......

456......

.23......

Az adott program az utolsó sorig elmegy, amikor felfedezi, hogy oda 1-es került, így a mátrix (1,1) helyébe beírt 1-es rossz lesz. Csak ugye ez backtracking, így a Nap is kihűl mire a program az (1,1) pozicióba visszalépteti. Sőt az utolsó előtti sorig terjedő összes olyan elhelyezkedést megvizsgálja, ami helyes és (1,1)-ben 1 van, ami rohadt sok eset. Hiszen ezek az elrendezések mind jók, csak az utolsó sor első egyese rontja el.

Előzmény: [40] Róbert Gida, 2008-03-10 23:56:54
[40] Róbert Gida2008-03-10 23:56:54

http://www.komal.hu/kep/abra/9e/1f/59/3c09e9df1cae1d41516331fe0/s29.c

Ez lenne egy feltett mintamegoldás egy versenyzőtől a Sudoku problémára. Ilyenek vannak benne:

"if(tabla[i][j] == 0) goto kezd;"

Rossz programozási gyakorlatra vall a goto utasítás

"else tabla[i][j] = temp - 48;"

Nem mindenhol egyértelmű az ascii karaktertábla, még a 128 alatti értékekre sem, így helyesebb azt írni:

else tabla[i][j] = temp - '0';

Az exit()-hez az stdlib.h include-olása nélkül warningot ad a fordító (nálam).

Továbbá, ha ezt egy online judge-nak próbálta volna elküldeni, akkor biztos rossz válasszal küldte volna vissza, mert ma már mindegyik megköveteli, hogy az int main-ből return 0-val térjen vissza.

Más hiba nem volt benne.

[39] Tibixe2008-02-05 20:22:11

Nem a pontozás részére gondoltam, hanem arra, hogy ha egy C-vel éppen ismerkedő látogató megnézi, még azt hiheti, hogy ezt lehet így is csinálni.

  [1]    [2]    [3]    [4]    [5]    [6]    [7]    [8]    [9]    [10]    [11]    [12]    [13]    [14]