Szorgalmi feladatok

A feladatok megoldásai az admin portálon adhatók be. A szorgalmi feladatokkal egy pontversenyben is részt lehet venni. Alapbeállítás szerint anonim módon jelensz meg a táblázatban. Ha szeretnél névvel megjelenni vagy teljesen eltűnni, az admin portálon beállíthatod.

A verseny állásának megtekintéséhez is be kell jelentkezni.

1. Sakktábla (255 megoldás)

Adott az alábbi, sakktáblát kirajzoló program:

#include <stdio.h>

int main() {
    printf("XX..XX..XX..XX..\n");
    printf("XX..XX..XX..XX..\n");
    printf("..XX..XX..XX..XX\n");
    printf("..XX..XX..XX..XX\n");
    printf("XX..XX..XX..XX..\n");
    printf("XX..XX..XX..XX..\n");
    printf("..XX..XX..XX..XX\n");
    printf("..XX..XX..XX..XX\n");
    printf("XX..XX..XX..XX..\n");
    printf("XX..XX..XX..XX..\n");
    printf("..XX..XX..XX..XX\n");
    printf("..XX..XX..XX..XX\n");
    printf("XX..XX..XX..XX..\n");
    printf("XX..XX..XX..XX..\n");
    printf("..XX..XX..XX..XX\n");
    printf("..XX..XX..XX..XX\n");
    return 0;
}

Végezz el ezen két módosítást!

  • Szüntesd meg a sormintát! Ahol látsz bármilyen ismétlést, azt mind tüntesd el a programból!
  • Jelenleg minden mező 2 egység széles: két darab X és . van vízszintesen és függőlegesen is. Oldd meg, hogy a felhasználó adhassa meg ezt a számot, vagyis hogy beállítható legyen a sakktábla mérete!

Elfogadott megoldások: 255 darab.
Szerezhető: 1 pont. Leadási határidő: 2018-09-10 04:00:00.

2. Kismutató, nagymutató (137 megoldás)

Kismutató, nagymutató

Az SVG (scalable vector graphics) egy szöveges fájlformátum, amellyel vektorgrafikus rajzok adhatók meg. Ez azt jelenti, hogy a fájlban geometriai formák, körök, egyenesek stb. leírása van. Elterjedten használják weboldalakon (mi is az InfoC-n), mert a böngészőprogramok is meg tudják nyitni.

Egy SVG fájl a következőképpen néz ki:

<svg width="200" height="200" xmlns="http://www.w3.org/2000/svg" version="1.1">
  <circle cx="100" cy="50" r="20" stroke="black" fill="yellow" />
  <line x1="100" y1="70" x2="100" y2="90" stroke="black" />
  <circle cx="90" cy="45" r="3" stroke="black" fill="blue" />
  <circle cx="110" cy="45" r="3" stroke="black" fill="blue" />
  <rect x="80" y="80" width="40" height="70" stroke="black" fill="blue" />
  <line x1="90" y1="150" x2="60" y2="190" stroke="black" />
  <line x1="110" y1="150" x2="140" y2="190" stroke="black" />
  <line x1="80" y1="90" x2="40" y2="70" stroke="black" />
  <line x1="120" y1="90" x2="160" y2="70" stroke="black" />
</svg>

Vagyis a kezdő svg és lezáró /svg között különféle formákat lehet megadni:

  • circle = kör cx,cy középponttal, r sugárral és stroke, fill színnel,
  • rect = téglalap, x,y bal felső sarokkal, width,height méretekkel,
  • line = szakasz, x1,y1 ponttól x2,y2 pontig,
  • és még egy csomó egyéb dolgot.

Az SVG-ről itt olvashatsz még: Basic shapes. A fenti fájlból egyébként az alábbi kép lesz.

Példa SVG képe

A feladat egy C program írása, amely három számot vár a szabványos bemenetén, szóközzel elválasztva. Ezek egy időpontot mutatnak: óra, perc és másodperc. A program az ora.svg nevű SVG fájlt hozza létre kimenetként, amelyben minden koordinátát a program maga számolt ki (sin, cos). Az órán legyen meg mindhárom mutató! A mutatók ne mindig pontosan az egész órára és percekre mutassanak! (Ha pl. fél kilenc van, a kismutató a nyolcas és a kilences között van középen. De ilyet a percmutató is csinál.) A számlapról ne hiányozzanak a percenkénti osztások sem, sőt az egész órákhoz tartozó osztások legyenek különbözőek, mint a többi!

A díszes, színes órákat szeretjük (választhatsz saját színeket, vonalvastagságokat stb.), programozóként azonban legfontosabb a specifikáció pontos követése. Figyelj arra, hogy a program kimenete szabályos, szintaktikai hibától (pl. hiányzó idézőjelek) mentes SVG fájlt legyen! Ilyen szempontból is nagyon szigorú a megoldások értékelése. A helyes SVG fájlokat meg tudják nyitni a böngészők is (bár ha ez sikerül, attól még nem biztos, hogy teljesen helyesek). Legyél kritikus a neten talált írásokkal is: az M_PI konstans nincs már benne a C nyelv szabványában!

Fájlkezelésről, fájlok létrehozásáról a honlapon található segédletben olvashatsz.

Elfogadott megoldások: 137 darab.
Szerezhető: 1 pont. Leadási határidő: 2018-09-17 04:00:00.

3. Paprikás csirkék (67 megoldás)

Ebben a feladatban a ferde hajítással kell dolgozni.

Angry birds

A feladat a következő. Adott egy Angry Birds pálya, amelyen a kör alakú madarat adott szögekben és sebességekkel lehet kilőni. C programot kell írnod, amely kiszámítja és megjeleníti azokat a (szög; sebesség) kombinációkat, amelyekkel egyből el lehet találni a szintén kör alakú malacot! (Visszapattanásokkal nem kell számolni.) A program egy darab SVG rajzot kell létrehozzon az angry.svg nevű fájlban, amely a terepet és a kiszámított röppályákat ábrázolja. A rajzon szerepelhetnek díszletek is, napocska, felhő, fák, hegyek, amelyek a számítás szempontjából nem lényegesek.

A keletkező rajzon minden legyen arányos, pl. 1 méter = 20 pixel! Ha a madarat és a malacot körrel rajzolod, akkor ez azok méretére is érvényes. A programban szereplő összes adat változóval kell legyen megadva (pozíciók, méretek, sebességek, nehézségi gyorsulás). Ne szerepeltesd ugyanazt a számkonstanst rengeteg helyen a forráskódban! Legfontosabb értékelési szempont: ha az adatok (pl. malac pozíciója) a kódban változnak, a rajz nem eshet szét. Figyelj arra, hogy az SVG formátum szintaktikai szabályait pontosan betartsd. Egy alap SVG fájl:

<svg xmlns="http://www.w3.org/2000/svg" version="1.1" width="320" height="200">
  <circle cx="100" cy="50" r="40" stroke="black" stroke-width="2" fill="red" />
</svg>

Néhány SVG idom: line, circle, rect, ellipse, poly (sokszög), lásd a Basic shapes oldalt. Javasolt tesztelés közben a képnéző programban megnyitva tartani a képet: a legtöbb tudja azt, hogy érzékeli a fájl változását, és újrarajzolja a képet.

Figyelj arra, hogy milyen időlépéssel számítod a röppályát. Ha túl nagyot választasz, lehet, nem érzékeled a találatot. A röppálya kirajzolásánál viszont már lehet nagy időlépést választani, különben túl nagy lesz az SVG fájl. Használhatod a fenti terepet, de kitalálhatsz sajátot is. A fentihez további adatok lehetnek: rmadár=rmalac=10 cm, g=9,81 m/s². A kilövés szöge 10° és 60° között állítható, 5°-os lépésekben. A sebessége 10 és 30 m/s között, 1 m/s lépésközzel. Ezekkel az adatokkal három lehetséges röppálya van. Ha azonban szép rajzot szeretnél, akkor más adatokat kell választanod. A fenti rajz ugyanis nem méretarányos, igazából a madár és a malac sokkal kisebbek.

Ellenőrizd a beadás előtt:

  • A keletkező fájl nevét és a fájlkezelést.
  • Az ütközés ellenőrzésének matematikáját.
  • A röppályát számító és rajzoló vezérlési szerkezetet, mint a programkód legösszetettebb részét.
  • Nyelvi eszközök használata. Alkalmazd, amit eddig tanultál, de ne l'art pour l'art tedd!

Jó szórakozást!

Tiltott szavak: malloc; scanf; getchar

Elfogadott megoldások: 67 darab.
Szerezhető: 1 pont. Leadási határidő: 2018-09-24 04:00:00.

4. BF értelmező (75 megoldás)

++++++++[>++++++++<-]>++.++++. – ez egy Brainfuck (BF) nyelvű program, amelyik kiírja a szabványos kimenetére, hogy „BF”. Ha még nem olvastad volna, akkor nézd meg az algoritmusokról szóló írást és a Brainfuck nyelvről szólót. Ezek kellenek a feladat megértéséhez. Ugyanis a feladat egy BF értelmező írása C-ben: egy olyan programot kell írni, amely le tud futtatni egy BF nyelven írt programot.

Az értelmezőnek mind a nyolc utasítást ismernie kell. A végtelen hosszú szalag helyett 32768 bájtosat kell venni, amely a gép indításakor nullákkal van feltöltve. A cellák egy bájtos, előjeles egész számokat tárolnak. Ezen az olvasó- és írófej bekapcsoláskori pozíciója a nulladik cella, amelytől balra egy szabályosan megírt BF programnak nem szabad lépnie. Ha ilyen pozíciót olvasna vagy írna (esetleg a szalag vége utánit), akkor a program futását meg kell szakítani. Az értelmezendő programot a C forráskódban kell eltárolni, karaktertömb formájában, amelynek a neve programkod:

char programkod[] = "hello"; /* 5+1=6 elemű karaktertömb */

A C a sztringeket karaktertömbként kezeli, azok nagyon kényelmesen használhatóak erre a célra. Azt is ki lehet használni, hogy C-ben ezek végjeles sorozatok, nulla zárja le őket. Vagyis a fenti példában programkod[0] == 'h' és programkod[5] == 0. A futtatott programnak akkor van vége, amikor az értelmező eléri a programszöveg végét. Az értelmezőnek helyesen kell tudnia kezelni az egymásba ágyazott ciklusokat is.

A BF program kapja meg a C program szabványos bemenetére érkező karaktereket, olyan módon, hogy a fájl vége jelet a −1-es értékre kell lefordítani számára. A C program szabványos kimenete legyen a BF program kimenete. Azon kívül legfeljebb hibaüzenetet írhat ki. Programozd is a képzeletbeli gépet, amelyet életre keltett az értelmeződ! A C forráskódnak beépítve tartalmaznia kell az alábbi BF programok közül valamelyiket:

  • A keresztnevedet kiíró program.
  • Program, amely beolvassa a teljes bemenetét, utána pedig kiírja azt visszafelé. (Bemenet → tenemeB.)
  • Program, amely beolvas egy szöveget, ésmindentszóköznélkülvisszaírakimenetére.
  • Egyéb, tetszőleges program, ez esetben viszont legyen hozzá magyarázat!

Megjegyzések.

  1. Az Internet tele van BF értelmezőkkel, amelyek forráskódban is elérhetőek. Ezeket ne nézd meg, mert akkor nincs semmi értelme a feladatnak. Megoldásként végképp ne küldj be ilyet! BF nyelvű programokat viszont letölthetsz, és kipróbálhatsz a saját értelmeződdel. Vigyázz, akad pár „nem szabványos”.

  2. Ha nem fut a Sierpiński-háromszög programja az értelmeződben, akkor biztos nem jól csináltál valamit. Olyan megoldást ne küldj be, amin az a program nem működik. Itt a kód:

char programkod[]="[ThisprogramprintsSierpinskitriangleon80-columndisplay.]>++++[<++++++++>-]>++++++++[>++++<-]>>++>>>+>>>+<<<<<<<<<<[-[->+<]>[-<+>>>.<<]>>>[[->++++++++[>++++<-]>.<<[->+<]+>[->++++++++++<<+>]>.[-]>]]+<<<[-[->+<]+>[-<+>>>-[->+<]++>[-<->]<<<]<<<<]++++++++++.+++.[-]<]+++++*****Made*By:*NYYRIKKI*2002*****";
  1. Ez a feladat nehéznek tűnik ELSŐRE, de a megoldás egyszerű, 30-40 sor. Egyedül a bezáró (vagy nyitó) zárójelpár megkeresésének algoritmusa nem triviális. Ötlet: Ha keressük egy [ bezáró párját, akkor addig kell menni, amíg meg nem találjuk az első ] karaktert. De ha közben újabb [ karakterrel találkozunk, akkor már a második ]-t keressük. Tehát kell egy változó, amelyik azt tárolja, hányadik ]-t keressük (vagy amikor ugrunk egy ciklus elejére, hányadik [-t).

  2. Vigyázat! Ne szálljon el a programod akkor sem, ha a BF program szintaktikai hibás! char programkod[] = "][".

  3. UTÓLAGOS MÓDOSÍTÁS: Ne használj globális változókat, legfeljebb a két szalaghoz! A feladat megoldása olyan rövid, hogy ebben globális változóra támaszkodni gyakorlatilag rosszul használt függvényeket jelent.

  4. UTÓLAGOS MAGYARÁZAT: Ne használj rekurziót sem (ha már tanultál róla régebben esetleg). Az ellentmond a feladat mondanivalójának; a rekurzió által olyan, mintha egy megjelenne egy harmadik szalag, a stack.

Jó szórakozást!

Tiltott szavak: sizeof;malloc;free;calloc;realloc;fopen;fclose;sizeof;dup2;strlen;szallag

Elfogadott megoldások: 75 darab.
Szerezhető: 1 pont. Leadási határidő: 2018-10-02 04:00:00.

5. „Cmabgidre eeygteemn vzétget ktuatás” (84 megoldás)

„A Cmabgidre eeygteemn vzétget ktuatás sernizt, tseljeen mdngiey, hgoy a lerít szvaak bsebeljeén mleyin serednbron vannak a btűek, cask az sámzít, hgoy az eslő és az ustloó bteű a hyeéln lyegen. A tböbi titsáaoln meg lehet keevvre, a sövezg akokr is osaalhtvó. Ez aézrt van, mret nem mdnien eyegs beűtt oavlnusk, hnaem tleejs svaaakzt eygben.”

Szóval még egyszer, most rendesen: „A Cambridge egyetemen végzett kutatás szerint, teljesen mindegy, hogy a leírt szavak belsejében milyen sorrendben vannak a betűk, csak az számít, hogy az első és az utolsó betű a helyén legyen. A többi totálisan meg lehet keverve, a szöveg akkor is olvasható. Ez azért van, mert nem minden egyes betűt olvasunk, hanem teljes szavakat egyben.” A kutatás egyébként nem pont erről szólt, és a pontos állítás nem ez; a történet elolvasható itt: Cmabridge.

Írj egy programot, amely szavanként beolvas egy szöveget, és kiírja azt a fenti leírás szerint megkavarva! Vedd figyelembe, ha egy szónak írásjel van a végén! Pl. „alma!”, vagy „ajtó...”. A szavak maximális hossza 50 karakter, a bemenet viszont bármilyen hosszú lehet. Ékezetes betűket nem kell kezelnie a programnak.

Tiltott szavak: malloc;realloc;calloc;free;fopen;fclose;65;97;90;122

Elfogadott megoldások: 84 darab.
Szerezhető: 1 pont. Leadási határidő: 2018-10-09 04:00:00.

6. Azon pontok mértani helye... (82 megoldás)

Ez az első grafikus szorgalmi. A megoldás előtt tanulmányozd az SDL-ről szóló írást, azon belül is az „Első program” fejezetet!

A feladat a következő. Egy olyan programot kell írnod, amely megnyit egy 640×480 pontból álló ablakot. Ezután végigpásztázza ennek összes képpontját, az alábbiak szerint színezi őket.

  • Pirosra színezi azokat, amelyek kb. 200 képpontnyira vannak a (320;240) ponttól.
  • Zöldre színezi azokat, amelyek távolságösszege a (240;200) és (400;280) pontoktól kb. 250 képpontnyi.
  • Kékre azokat, amelyeknél a (240;240) ponttól és a (400;240) ponttól vett távolságok különbségének abszolút értéke kb. 100 képpont.
  • Végül pedig fehérre azokat, amelyeknél a távolság a (320;240) ponttól, illetve az x=400 egyenestől kb. ugyanakkora.

A „kb. valahány képpont”-nál az egyenlőség határát nevezd epszilonnak, és add meg a programban egy eps nevű változóval! Az egyes alakzatoknak neve is van (középiskolában tanult alakzatok), ezeket írja ki a program az ablakban valahova!

Fontos: az SDL2_gfx egyes verziói hibásak, és rosszul kezelik a színeket. Ezért inkább a pixelColor() és a stringColor() függvények helyett használd a pixelRGBA() és stringRGBA() függvényeket! Abszolút értéket kell használni a feladatban, de nem az abs()-ot, hanem egy másikat. Járj ennek utána, miért!

Tiltott szavak: abs;TTF_OpenFont;pixelColor;stringColor;malloc

Elfogadott megoldások: 82 darab.
Szerezhető: 1 pont. Leadási határidő: 2018-10-16 04:00:00.

7. Egri csillagok (60 megoldás)

Az alábbi feladat megoldásával az algoritmusokat és a sztringeket lehet gyakorolni. Jogi közlemény: ez egy gyakorlófeladat, semmiféle következtetést nem lehet belőle levonni a NZH feladataira nézve.

Adott a következő fájl: egri.txt. Ez az Egri Csillagok szavainak egy részét tartalmazza, az egyszerűség kedvéért kisbetűsítve és ékezettelenítve. A leghosszabb szavak 15 betűsek.

Illeszd be a szavakat egy C forráskódba! Definiálj sztringek tömbjét (egy olyan tömb, amit ha megindexelünk előbb egy sorszámmal, akkor sztringet kapunk, amely még tovább indexelhető, egy karaktert kapva), és inicializáld úgy, hogy a szavakat tartalmazza! Figyeld meg: az utolsó szó után egy üres sztring van, ami végjelnek használható. Így a sztringek számát nem kell tudnod, és ne is írd azt be a programba! Ez a tömb lehet globális változó is (függvényeken kívül definiált).

  1. Kérj egy fél szót a felhasználótól, és keresd ki a listából azokat a szavakat, amelyek tartalmazzák azt! Pl. „alma”, „alma almagyaron irgalmazzanak jutalmad oltalmazza tilalmas”.

  2. Kérj a felhasználótól egy szót, és írd ki a képernyőre, hogy a beírt szó a) nem tartalmaz magánhangzókat b) csak egyforma magánhangzókat tartalmaz c) különféle magánhangzókat tartalmaz! A magánhangzók: a, e, i, o, u.

  3. Írj függvényt, amely paraméterként átvesz egy szót, és visszatér egy felsorolt típussal, amelynek lehetséges értékei: magas, mély, vegyes. A függvény használatával számold meg, a szavak tömbjében hány magas, mély, vegyes hangrendű szó található! Írd ki ezeket a számokat, és melléjük azt is, hogy hány százalékot jelentenek az összes szóhoz képest! Mély hangrendű az, amely csak a, o, u magánhangzót tartalmaz, magas, amelyik csak e, i magánhangzót. (Az ö, ü hangokat tartalmazó szavak nincsenek a listában.) A felsorolt típus használata:

typedef enum Lampa { piros, sarga, zold } Lampa;
Lampa l = piros;
  1. Írj függvényt, amely egy szót kap paraméterként, és igaz vagy hamis értékkel tér vissza attól függően, hogy a szó betűi ábécé szerint növekvő sorban vannak-e! A „bot, hit, most” szavak például ilyenek. A függvény használatával írj programrészt, amellyel a szavak tömbjéből kiválogatod és kiírod az ilyeneket!

  2. Keresd ki azokat a szavakat, amelyek első és utolsó betűjét elhagyva is értelmes, a tömbben szereplő szó jön ki, pl. „lennie”, „enni”. Írd ki az eredeti és a rövidített szavakból képzett párokat!

Az egyes részfeladatok által generált kimenetet válaszd el a képernyőn, írd ki, melyik részlet hányadik részfeladathoz tartozik! Ahol lehet, használj beépített függvényt (string.h)!

Tiltott szavak: getch;getchar;void main;sizeof;1565;1566;1567;fopen;open;system;goto;malloc

Elfogadott megoldások: 60 darab.
Szerezhető: 1 pont. Leadási határidő: 2018-10-25 04:00:00.

8. Rekurzió – stílusgyakorlat 👔 (60 megoldás)

Tetszőlegesen hosszú szöveget beolvasni: ez nem könnyű feladat. Amíg nem láttuk az egész szöveget, nem tudjuk, mennyi memóriát kell foglalni. Amíg nem foglaltuk le a memóriaterületet a sztring számára, addig viszont nem olvashatjuk a szöveget, mert nem tudjuk eltárolni a karaktereket.

Vagy mégis? Tudjuk, hogy a függvények lokális változóiból minden függvényhíváskor létrejön egy új példány. Így ha egy rekurzív függvénynek egy karakter a lokális változója, akkor egy rekurzív hívással létrehozunk egy újabb karaktert, meg még egyet és még egyet, amíg a szöveg végére nem értünk. Ha ez megtörtént, akkor pedig lefoglalhatjuk a memóriaterületet, mert addigra látjuk, hány karakter volt.

A feladatod egy ilyen függvényt írni:

/* A függvény beolvas egy teljes sort (enterig vagy fájl vége jelig) a szabványos
 * bemenetről, és visszaadja egy dinamikusan foglalt sztringben. A sztring
 * nullával van lezárva, az entert nem tartalmazza. A hívó felelőssége
 * a free()-t meghívni a kapott pointerre. */
char* sort_beolvas(void);

A szöveg beolvasását a fenti módszerrel kell megvalósítanod. Amit használhatsz:

  • tetszőleges saját segédfüggvény,
  • egyetlen egy malloc hívás.

Amit pedig nem:

  • statikus élettartamú változó (azaz globális és függvénybeli statikus),
  • tömb átméretezés, bármilyen egyéb tároló.

Figyelem: ennek a feladatnak elméleti jelentősége van csak! A gyakorlatban az okos átméretezés (pl. a méret duplázása) célravezetőbb, hatékonyabb.

Tiltott szavak: realloc;calloc;10

Elfogadott megoldások: 60 darab.
Szerezhető: 1 pont. Leadási határidő: 2018-10-30 04:00:00.

9. Világtérkép (45 megoldás)

Adott az alábbihoz hasonló formátumban két tömb: vilag.c és tavak.c.

float vilag[] = {
    -59.6, -80.0, -62.3, -80.9, -64.5, -80.9, -61.9, -80.4, -59.6, -80.0, 0, 0, 
    -159.2, -79.5, -162.4, -79.3, -160.2, -78.7, -159.2, -79.5, 0, 0, -45.2, 
    ..............
    -48.0, 82.1, -44.5, 81.7, -46.9, 82.2, -43.4, 83.2, -39.9, 83.2, -35.1, 83.6,
    -27.1, 83.5, 0, 0, -1, -1
};

Ezek a világtérképet tartalmazzák nem túl strukturált formában. Igazából struktúrák tömbjei lehetnének, mert minden számpárjuk egy GPS pozíciót ad meg. A párok első tagja a hosszúsági érték (longitude; -180...+180 fok nyugatról keletre), második tagja pedig egy szélességi érték (latitude; -90...+90 fok délről északra). A számpárok sora sokszögeket ír le, a kontinensek és nagyobb szigetek, illetve tavak körvonalaival. Minden sokszöget egy 0 0 számpár követ, végül az utolsó 0 0 számpár után egy -1 -1 zárja a tömböt. A 0 0 GPS pozíció az egyenlítőn, Közép-Afrika nyugati partjától nyugatabbra található, az Atlanti-óceánon, tehát ott nincs semmi, és ezért lehet végjel.

világtérkép

A feladatod egy olyan SDL2-es programot írni, amely kirajzolja a világtérképet. Ehhez jól használható az SDL_gfx filledPolygonRGBA() és aapolygonRGBA() függvénye, amelyek tetszőlegesen bonyolult, akár konkáv sokszögeket is tudnak rajzolni. A paraméterezéséhez a koordinátákat előbb át kell másolnod egy másik tömbpárba: a függvény két külön tömbben, a Sint16 vx[]-ben és a Sint16 vy[]-ban várja az x és y koordinátapárokat, ahol Sint16 az SDL által definiált egész szám típus, az int16_t-vel egyenértékű.

Tehát: rajzold ki a programban a világtérképet, az általad választott színekkel egy 1080×540-es vagy 720×360 méretű ablakban! A területek ne csak kitöltve legyenek, hanem körberajzolva is! A programot ne írd tele képletekkel, mágikus számokkal: kell egy függvény, amely GPS koordináta → képernyőkoordináta számítást végez, és természetesen kell egy függvény, amely egy ilyen tömb alapján rajzolni tud. A világtérképre rajzolj halványan koordinátarácsot is, 15 vagy 30 fokonként! Jelöld be a BME-t a térképen! A program az ablak bezárására vagy a rajzra kattintásra fejeződjön be.

Ne duplikálj kódot, és ne legyen pazarló a memóriakezelésed!

Tiltott szavak: realloc

Elfogadott megoldások: 45 darab.
Szerezhető: 1 pont. Leadási határidő: 2018-11-06 04:00:00.

10. Palacsintarendezés (39 megoldás)

Nem csak helyben rendezések léteznek, mint amilyenek előadáson szerepeltek – amelyekben az elemi lépés két elem cseréje.

Ha egy palacsintatornyot szeretnénk rendezni (felülre a kicsik, alulra a nagyok), akkor nagyon nehéz lenne két palacsintát megcserélni benne. Egyszerű művelet viszont a torony egy részének átfordítása: csak benyúlunk egy lapáttal valamelyik két palacsinta közé, és egy ügyes mozdulattal átfordítjuk az egészet.

palacsintarendezés

A programozásban az ilyen elven működő rendezést, mily meglepő, palacsintarendezésnek nevezik (pancake sorting). Külön elmélete van, különféle algoritmusokat találtak ki hozzá. A legkevesebb szükséges átfordítások számát meghatározó képlet (n függvényében, ahol n a torony mérete), máig ismeretlen.

A legegyszerűbb algoritmus a közvetlen kiválasztásos rendezéshez hasonlít. Ebben megkeressük a legnagyobb palacsintát, aztán a fölötte lévő résszel együtt átfordítjuk. Így a legnagyobb felülre kerül, és a teljes tornyot átfordítva betehetjük azt alulra. A feladat: írd meg a palacsintarendezést láncolt listára, alkalmazva a gyakorlaton tanult listamegfordító algoritmust! A palacsintatorony alja a lista eleje, így fordítható át könnyen a vége.

A lista álljon 10 egész számból, és minden megfordítási lépés után írd ki a listát, hogy látszódjon a rendezés! Ügyelj arra, hogy az algoritmus lépésenként két megfordítást használ; mindkettő után meg kell jeleníteni a számsort.

Elfogadott megoldások: 39 darab.
Szerezhető: 1 pont. Leadási határidő: 2018-11-13 04:00:00.

11. Bináris fa kirajzolása (32 megoldás)

Gyakran hasznos egy program tesztelése közben, ha ki tudjuk rajzolni annak adatszerkezeteit – különösen ha nem szimpla tömbökről van szó, hanem például bináris fákról. Ebben a feladatban egy olyan programot kell csinálnod, amely egy bináris fát rajzol ki.

bináris fa

A feladat tehát:

  • Hozzon létre a program 10-20 kétjegyű véletlenszámból egy bináris keresőfát.

  • Rajzolja ki, a szokásos megjelenési módján: gyökér fent, levelek lent, pointerek helyén a csúcspontok összekötve, a választásod szerint a) SDL-es grafikával, vagy b) egy SVG fájlba, vagy c) konzolablakban (az összekötések valamennyire itt is látszódjanak).

Elfogadott megoldások: 32 darab.
Szerezhető: 1 pont. Leadási határidő: 2018-11-20 04:00:00.

12. Bináris fa szélességi bejárása (28 megoldás)

Az előadáson megismert, bináris fát bejáró algoritmus egy ún. mélységi bejárás (DFS – depth-first search). Azért nevezik így, mert a rekurzióban nagyon hamar távolra kerül az algoritmus a gyökértől: meghívja magát a függvény a gyökérelem gyerekére, az megint a gyerekre, az megint a gyerekre stb. Így az algoritmus lényegében a gyökértől távoli elemekkel foglalkozik először, és emiatt pl. a jobb oldali részfa feldolgozása el sem kezdődik, amíg a bal oldali részfa feldolgozása be nem fejeződött.

bináris fa mélységi bejárása

A mélységi bejárás „ellentéte” a szélességi bejárás (BFS – breadth-first search), amikor is a gyökérhez közeli elemeket dolgozzuk fel előbb. Legelőször magát a gyökeret, aztán a második szinten lévő elemeket, aztán a harmadik szinten lévőeket és így tovább.

bináris fa szélességi bejárása

Ez egy iteratív algoritmussal is könnyen megvalósítható:

sor = { gyökérelem }
AMÍG a sor nem üres:
    csomópont = elem a sor elejéről
    gyerekek beszúrása a sor végére
    csomópont feldolgozása

Az algoritmus egy várakozási sort alkalmaz. A sor végére mindig bekerülnek az új elemek, és a feldolgozandó elemet mindig a sor elejéről veszi. Mivel a gyerekeket mindig a sor végére tesszük be, a sor elején olyan elemek lesznek, amelyek azok szülei voltak – tehát közelebb voltak a gyökérhez.

Valósítsd meg ezt az algoritmust! Építs várakozási sort láncolt listával az előadáson tanult módon, és járj be segítségével egy bináris fát, amelyet felépít a programod! Figyelj arra, hogy a várakozási sor lényege éppen az, hogy O(1) az elejéről elvétel és a végére beszúrás is. Ezt tudnia kell az implementációnak.

Elfogadott megoldások: 28 darab.
Szerezhető: 1 pont. Leadási határidő: 2018-11-20 04:00:00.

13. Az ellipszis (3 megoldás)

A feladat egy olyan programot írni, amely ellipszist rajzol ki annak matematikai definíciója alapján.

A régebbi feladathoz hasonlóan: az ellipszis azon pontok mértani helye, ahol a pontok két rögzített ponttól mért távolságának összege állandó. A programodnak sorban meg kell vizsgálnia az ablak összes képpontját, hogy azok megfelelnek-e ennek a definíciónak. Az egyenlőséget egy adott tartományon belüli közelségként kell értelmezni (epszilon). Az egész szám koordinátákkal rendelkező képpontok amúgy nem lesznek pontosan rajta a görbén, mert az matematikailag nulla vastagságú.

A programban a felhasználónak mozgatnia kell tudni az ellipszis fókuszpontjait az egérrel („fogd és vidd”, rákattint, mozgat, elenged). Ezen felül, ha az ellipszis valamely pontjára kattint és azt húzza el, azzal a távolságösszeget kell tudnia módosítani. Mindeközben az ablak aljára legyen kiírva a két fókuszpont pozíciója és a távolságösszeg!

Az SDL-ről szóló írásban (Extrák/Grafika menüpont) találsz útmutatót az egérkattintás és egérmozdulat események kezelésével kapcsolatban. Alkalmazd a Prog1-ben eddig megtanult módszereket – ez a megoldás fő értékelési szempontja lesz! Használj függvényeket (pl. távolság), struktúrákat (pont), egyetlen állapotváltozóval rendelkező állapotgépet (egér mozgatás mit csinál attól függően, hogy (hova?) volt kattintás előtte?)! Figyelj arra, hogy ne terheld fölöslegesen a gépet; a képet csak akkor kell újrarajzolni, ha az változott.

Tiltott szavak: TTF_Init

Elfogadott megoldások: 3 darab.
Szerezhető: 1 pont. Leadási határidő: 2018-11-27 04:00:00.

14. NHF szépségverseny (0 megoldás)

Ha szeretnéd a nagy házidat beküldeni a szépségversenyre, azt itt teheted meg. A formai követelmények:

  • Egy maximum 800x600-as, igényesen kivágott képernyőkép PNG formátumban.
  • Feladat címe és rövid leírás, helyesírási hibáktól és elgépelésektől mentesen, TXT formátumban.
  • Hozzájárulás, hogy megjelenhetsz névvel a honlapon.
  • Mindezek egy ZIP fájlba csomagolva.

Elfogadott megoldások: 0 darab.
Szerezhető: 1 pont. Leadási határidő: 2018-12-02 23:59:00.




A feladatok megoldásához nem szükséges olyan nyelvi elem, amely nem volt még az előadáson. Ha igen, akkor az magyarázattal együtt szerepel a feladat szövegében.

A szorgalmik javítása szigorúbb, mint a számonkéréseké általában. Trehány megjelenésű forráskód, indokolatlan vezérlési szerkezet, hatékonytalanság stb. a visszautasítás okai lehetnek még akkor is, ha a programod működik. Figyelem! Határidő utáni javításra nincs lehetőség. Ha elég hamar leadod a megoldást, lesz lehetőséged javítani is. Ha az utolsó pillanatban, akkor elsőre jónak kell lennie.

Kérjük vedd figyelembe, hogy akár 100 beküldött megoldást javítunk, és ezért hibás megoldások esetén nem feltétlenül keressük meg az összes hibát. Ha csak egy hibát jelzünk, az nem jelenti azt, hogy nincs több. (Különösen igaz ez egy olyan hibára, amihez egyértelműen a feladatkiírás valamelyik mondata társítható.) Ha kérdésed van, inkább tedd fel!

A konkrét feladat megoldására koncentrálj! Ha általánosítasz, esetleg bonyolultabb feladatot oldasz meg, azzal a pontod elveszítését kockáztatod. Ha megtetszik a feladat, és továbbfejlesztenéd, a saját verzióddal ezt bátran megteheted, de beadni csak olyat adj be, amit a feladatkiírás kért.

A szorgalmiknál sem megengedett a plágium. Ha más megoldását adod be, akár meg is bukhatsz emiatt. Mérlegelj!