máj 2017

Tic-Tac-Toe v Baltíku

Väčšina z vás sa na počítačoch najradšej hrá. Aj ja sa na počítačoch a mobiloch zvyknem hrať, ale najväčšou zábavou pre mňa je niečo naprogramovať. Kedysi som sa naučil programovať  hlavne tým, že som programoval rôzne počítačové hry. Prvý počítač som si kúpil v roku 1985, bol to osembitový japonský počítač Sord, mal 8 kilobajtov pamäte a programy sa doň nahrávali pomocou kazetového magnetofónu. Do ôsmich KB sa toho veľa nezmestilo, preto som sa snažil programovať efektívne s čo najmenšími pamäťovými nárokmi a programujem tak doteraz. Vtedajšie počítače boli mnohotisíckrát pomalšie, ako dnešné, takže, ak hra mala byť hrateľná, bolo potrebné optimalizovať aj rýchlosť programu. Programovacím jazykom bol Basic a kritické časti som programoval v asemblery.

Na tento počítač takmer žiadne hry neexistovali a tak, keď som na iných počítačoch videl nejakú hru, naprogramoval som ju aj na mojom počítači.

Začneme jednoduchou logickou hrou Tic-Tac-Toe. Hrá sa na hracom pláne 3×3. Do plánu hráči striedavo zapisujú svoje symboly – krížik a krúžok. Kto uloží svoje symboly tak, že sú vedľa seba, pod sebou alebo po diagonále tri, vyhral. Ak sú všetky políčka obsadené a nik nemá tri rovnaké symboly v rade, hra skončila remízou. Na obrázku vpravo vyhral hráč, ktorý kreslil krúžky. Continue reading

Projekt Sudoku

 

1. etapa

Na prvej hodine ste takmer všetci zvládli nakresliť hrací plán Sudoku (obrázok vpravo). Mnohí postupovali extenzívne, niektorí zvládli aj efektívnosť riešenia. Počet použitých príkazov sa pohyboval od 21 do 93 (mne sa to podarilo na 18 príkazov, svoje riešenie sprístupním, keď všetky triedy dokončia prvú etapu a sprístupním tiež najefektívnejšie riešenia žiakov a jedno či viac riešení, ktoré budú niečim originálne.   Continue reading

Súťaž v programovaní Imagine

Vašou úlohou je naprogramovať prázdny hrací plán hry Sudoku na čo najmenší počet príkazov. Riešenie musí byť vytvorením procedúry, ktorá tento hrací plán nakreslí a nemožno použiť už predkreslený obrázok.

Vzor, ako by mal hrací plán vyzerať:

Do počtu príkazov nepočítame viem názov_procedúry a koniec a číselné parametre či už vo forme čísla alebo premennej.

Celkové poradie

  1. Čajka 9. A 18
  2. Petróc 7.A 21
  3.  Micheĺ 9.A 22
  4.  Varinský 7.A 29
  5. Richnavský 31

Poradie podľa jednotlivých tried

9.A

  1. Čajka 18
  2. Micheľ 22
  3. Richnavský 31
  4. Krajňáková 39
  5. Sabovčíková a Genčiová 91
  6. Kalina 98

7. A

  • Petróc 21
  • Varinský 29
  • Melicherová 31
  • Gbúrová 32
  • Lukáč, Orosz 75
  • Bucher 85

7. B

  • Sremaňák 40 (Patrikove riešenie zverejním, ako jediný použil parameter, ktorý určuje, aký veľký bude hrací plán)
  • Jakubčák 56
  • Šašala – veľa 🙂

Učiteľ TM 17. Pôvodne som mal 21, keď Petróc dosiahol rovnaký počet, ešte som to zredukoval.

 

Genetické algoritmy

Čo je sudoku, takmer všetci vedia, väčšina nevie, čo je genetický algoritmus alebo genetické programovanie.

Genetický algoritmus je nedeterministická metóda riešenia problému, vychádzajúca z princípov Darwinovej evolučnej teórie. 

Každé riešenie úlohy (aj “zlé”) sa nazýva chromozóm, je tvorené binárnym reťazcom danej dĺžky, ktorá je rovnaká pre všetky chromozómy populácie. Populácia je konečná množina chomozómov. Základná populácia resp. nultá generácia populácie je začiatočný stav riešenia. Vývoj k optimálnemu riešeniu prebieha prirodzeným vývojom populácií. Nultá generácia je vygenerovaná náhodne, vygenerované chromozómy, musia byť riešením problému.

Proces reprodukcie:

  • Výber chromozómov na kríženie či mutáciu (pseudonáhodný výber podľa pravdepodobnosti úmernej jeho fitness)
  • Kríženie chromozómov (výmena podreťazcov, kde môže prebiehať kríženie jednobodovo, či viacbodovo)
  • Mutácia, náhodne zmutujú niektoré gény, mutuje sa s malou pravdepodobnosťou, aby zostala zachovaná genetická informácia

Náhodnosť sa zaisťuje pomocou generovania pseudonáhodných čísel.
Continue reading