Szorgalmi feladatok

Az alábbi feladatok a portálon adhatók be (ha nem járt még le a határidejük). A megoldásukhoz nem szükséges olyan C 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.

Rendes tavak a hegyes programban

Javítsd ki úgy a dec. 19-ei adventi naptáras programot, hogy ne legyen hibás a tavak kirajzolása! Legyen meg a víz szintje (ne legyen ferde, mint a hegyoldal - ehhez szintbe kell hozni az összes nagyon alacsony helyet), és ne legyenek véletlenszerűen kék pontok elszórva a tavak körül (ehhez a kis véletlenszám hozzáadását kell kicsit okosabban kezelni a négyszögek színének meghatározásánál).

Szabályos testek üveglapokból

A 18-as adventi naptár bejegyzés (drótváz testek) programját dolgozd át úgy, ahogy az írás végén a harmadik pont javasolta: tároljon az ne drótvázat, hanem a lapok adatait! (Esetleg tárolhat drótvázas ÉS a lapok adatait is). Adatfájlokat találsz a hivatkozott helyen: http://www.scienceu.com/geometry/facts/solids/.

Szabályos testek halvány élekkel

A 18-as adventi naptár bejegyzés (drótváz testek) programját dolgozd át úgy, ahogy az írás végén a második pont javasolta: az éleken legyen színátmenet! Az élek hátrább lévő részei jelenjenek meg halványan, a közelebb lévők pedig erősebben.

World of Goo – szél és lufik

Van egy olyan pálya a World of Goo-ban, ahol egy szélmalmot kell körbeépíteni úgy, hogy lufikra kell aggatni az építményünket: http://www.youtube.com/watch?v=vHA6G4v0E-Q.

Egészítsd ki úgy a dec. 17-ei adventi programot, hogy legyen benne lufi (a gravitáció hasson rá másik irányba) és szél is! A szélhez közegellenállást kell számolni, amelyhez a képlet benne van a négyjegyű függvénytáblázatban is. Mutassa a képernyő tetején megjelenő színes csík, hogy épp merre fúj a szél, és mennyire!

vprintf() és társai

A printf() függvénycsaládnak van még néhány függvénye, amelyek nem szerepeltek az előadáson. A printf(), sprintf(), fprintf() mellett van egy vprintf() nevű is: http://pubs.opengroup.org/onlinepubs/009695399/functions/vprintf.html. Ennek meg kell adni egy formátumsztringet, és egy már „megnyitott” va_list-et, amely egy változó hosszúságú argumentumlistát jelképez. Ha kicsit utánanézünk, kiderül, hogy a sima printf nem csinál mást, mint a vfprintf()-et meghívja az stdout-ra:

int
printf(const char *fmt, ...) {
    int ret;
    va_list ap;

    va_start(ap, fmt);
    ret = vfprintf(stdout, fmt, ap);
    va_end(ap);
    return (ret);
}

Mert így tudja a változó számú argumentumát továbbadni egy másik függvénynek.

A feladat: írj printf()-szerű függvényt, amely az SDL_ttf függvénykönyvtárral használható! Tudjon ez tetszőleges sztringet kiírni a képernyőre, mégpedig úgy, hogy a printf()-éhez hasonló formátumsztringet és tetszőlegesen sok paramétert fogadjon! Valahogy így:

TTF_font *font = .....;
my_ttf_printf(screen, 30, 40, font, 0x4080C0FF, "Hello %d %s!", 12, "vilag");

Az második két paramétere legyen a koordináta, a negyedik a betűtípus, ötödik a szín, és onnantól kezdve mint a printf(). Mindez pár sorban megoldható – ötletet a fenti link ad.

Síkidom területe

Adottak az alábbi síkidomok: egy parabola, egy kör, és egy szinuszfüggvény alatti terület:

Feladat: írj egy olyan programot, amely Monte Carlo-módszerrel meghatározza a három síkidom metszetének területét! A program tartalmazzon egy olyan függvényt, amely nem csak ezt a problémát tudja megoldani, hanem tetszőleges számú síkidom megadható neki oly módon, hogy függvények tömbjét veszi át. (Az egyes függvények paraméterei ehhez x, y koordináták kell legyenek, visszatérési értékük egy logikai érték: hogy a síkidom területére esik-e a pont, vagy nem.)

void*(*)(void*) vagy void (*)(void**)?

A második előadáson szerepelt a for ciklus. Azt mondtuk róla, abban három dolgot lehet megadni, egy indulási helyet, egy célt, és egy lépést:

for (innentől; idáig; következő)
  valamitcsinál();

Ez nem véletlenül van így, mindig így szervezzük a ciklusokat. Így szervezzük akkor is, ha egy tömb adatait dolgozzuk fel (első elem, utolsó utáni elem, index növelése), és akkor is, ha egy listát járunk be (első elem, utolsó utáni elem, ugrás a következő elemre).

A feladat a következő: általánosítsd a tömb és a lista bejárását! Írj egy függvényt, amelynek át lehet adni a következő adatokat:

– egy tároló (tömb, lista, ...) elejét jelképező pointert,

– egy tároló végét jelképező pointert,

– egy függvényre mutató pointert, amely léptetni tudja a tároló egyik elemére mutató pointert,

– és még egy függvényre mutató pointert, amelynek a tároló egyik elemére mutató pointert adva, feldolgozza azt az elemet.

Ezzel a függvénnyel egy tömböt így lehetne kiíratni:

int tomb[] = { 1, 2, 3, 4, 5 };
foreach(tomb, tomb+5, intkovetkezo, intkiir);

Ahol tomb a tároló elejére mutató pointer, tomb+5 az utolsó utáni elem (mivel tomb+4 az utolsó), az intkovetkezo egy alkalmasan megírt léptető függvény, az intkiir pedig egy alkalmasan megírt kiíró függvény.

Definiálj a programodban egy tömböt, aminek kiírod a számait a foreach() függvénnyel! Írd ki a tömb elemeit visszafelé is, ugyanezzel a foreach() függvénnyel! Hozz létre egy láncolt listát valós számokból, és írasd ki annak az elemeit is!

Mutasd meg, hogy a foreach() függvényed mennyire generikus: definiáld azt a beadott forráskód legtetején, az összes többi függvény deklarációja előtt! Figyelj a feladat pontos értelmezésére! Vajon mit jelent a feladat címe?

C milliomos hekkelő programok

Aki írt javascriptes megoldó programot a C milliomos játékhoz, ide töltheti fel (ugyanúgy pont jár érte, mint a többi szorgalmiért).

E feladat határidejének lejárta után javascriptből pörgetni a játékot szigorúan tilos, a megajánlott jegy elvesztésének kockázata mellett. :D (Házi leadás hete van, kéretik a portált nem terhelni!)

Bináris fa - az SVG visszatér

Írj programot, amely felépít egy bináris keresőfát 50-100 véletlenszerűen választott, legfeljebb háromjegyű számból, és aztán kirajzolja azt a fát egy SVG fájlba!

A kimenet a lenti ábrához hasonló legyen, de ízlésed szerint tetszőlegesen formázhatod, színezheted is.

A kimeneti képfájl mérete legyen 640×480 pixel, és a kirajzoló függvényed vegye figyelembe a fa szélességét és magasságát! Vagyis a fa ne lógjon ki a képről se vízszintesen, se függőlegesen, de ne is legyen a kép szélein túl sok felesleges hely. A csomópontok mérete lehet fix: túl sűrű fa esetén a csomópontok egymásra lógása megengedett.

Fontos: a programban ne használj globális változót, az SVG szintaktikai szabályait pedig szigorúan tartsd be! (Az attribútumokat kötelező idézőjelbe tenni, és az összes SVG csomópontot le kell zárni.)

(Ha megcsináltad a morze dekódolós szorgalmit, kirajzolhatod azt a fát is – de a programnak általánosan, bármilyen felépítésű fára kell működnie. Nem „drótozhatod bele” a fa szélességét és magasságát.)

Morze dekódoló sorminta

Az alábbi függvény a legfeljebb két jelből (ti/tából, azaz pontból és mínuszból) álló morzekódokat képes dekódolni:

void dekod(char *de) {
    if (de[0]=='-')
        if (de[1]=='-')
            printf("M");
        else if (de[1]=='.')
            printf("N");
        else
            printf("T");
    else if (de[0]=='.')
        if (de[1]=='-')
            printf("A");
        else if (de[1]=='.')
            printf("I");
        else
            printf("E");
    else
        printf("érvénytelen");
}

Így dekódolhatnánk a morze ábécé összes betűjét, csak hosszabb lenne a dekódoló függvény. A matiné szó viszont a mostani, egyszerűsített változattal is már kiírható:

dekod("--"); dekod(".-"); dekod("-");
dekod(".."); dekod("-."); dekod(".");

A dekódoló függvény ilyen formában egy nagy sorminta. Mint tudjuk, a morze dekódolás bináris fáért kiált. A feladat tehát a következő: mutasd meg, hogy a sormintát kézzel leírni felesleges volt! Írj egy olyan programot, amely felépít egy morzekódot dekódoló fát, de azt használva nem morze dekódolást végez, hanem létrehoz egy morzedekoder.c nevű fájlt, egy C forráskódot, amelyben a fentihez hasonló elven végzed el a sztringben kapott morzekód dekódolását! A kiírt forráskód, és az azt gyártó forráskód is forduljon warning nélkül, a codeblocks/gcc -Wall -pedantic beállításai mellett! Dekódold a keresztneved az előállított programban!

Egyiptomi törtek

Minden pozitív racionális szám felírható egész számok reciprokainak összegeként, ún. egyiptomi törtként (ők így jelölték ezeket). Például:

 5     1   1   1
 -  =  - + - + -
 7     2   6   21

Azt gondolhatnánk, hogy a mohó algoritmus, azaz mindig a lehető legnagyobb reciprok kiválasztása, kivonása, majd a maradékkal való további műveletvégzés előállítja a legegyszerűbb felbontást, de ez nincs így. Pl. 5/121 esetén ez az alábbi megoldást adja, amelyben „irreálisan nagyra” nőnek a nevezők:

 5     1    1       1          1                     1
--- = -- + --- + ------ + ------------ + -------------------------
121 = 25   757   763309   873960180912   1527612795642093418846225

Ehelyett jobb ötlet a p/q törtet egy 1/q + 1/q + ... összegre bontani, és utána az egyenlő nevezőket megszüntetni egy összevonási lépésben. Ha q páros, akkor

1   1     1
- + -  = ---,
q   q    q/2

ha páratlan, akkor pedig

1   1      1         1
- + - = ------- + --------
q   q   (q+1)/2   q(q+1)/2

módon lehet elvégezni az összevonást. Láthatóan mindként esetben reciprok egészek maradnak, viszont a nevezők csökkennek, mivel q/2 < q. A kifejezés pedig nem bonyolódik, mert az első esetben csökken a tagok száma, a második esetben változatlan.

Írj programot, amelyben a nevezőket láncolt listában tárolod! A listát érdemes a nevezők szerint rendezve tartani, mert akkor az egyforma nevezők könnyen megtalálhatóak. Hogy írták az ókori egyiptomiak az 5/7-et és az 5/121-et?

Csevegőprogram

A feladat egy platformfüggetlen csevegőprogram elkészítése, amely megjelenítéshez SDL-t használ, a hálózatkezeléshez pedig az SDL_net-et.

A csevegőprogram felhasználói felülete három részre oszlik. A képernyő jobb oldalán, egy sávban a bejelentkezett felhasználók kell látszódjanak. Az alsó sorba a program használója gépelhet, a képernyő többi részét pedig a felhasználó saját maga által beírt üzenetei, és mások üzenetei foglalják el. Az üzenetek a szervertől folyamatosan érkezhetnek, ugyanakkor a programnak biztosítania kell azt is, hogy a használója bármikor gépelhessen.

A csevegéshez a programod az infoc.eet.bme.hu szerverre, annak is a 8888-as portjára kell csatlakozzon TCP-vel. A szerver minden beírt szöveges üzenetet elküld az összes többi bejelentkezett kliensnek (akik legfeljebb 128-an lehetnek), továbbá értesíti a klienseket a többiek ki- és belépéseiről.

A szerver és a kliens azonos nyelvet (protokollt) kell beszéljenek. Ebben a küldött és a fogadott adatfolyamok üzenetekre tagolódnak. Minden üzenet egy egybájtos paranccsal kezdődik, utána folytatódik egy opcionális paraméterrel (tartalommal), végül pedig egy 127-es terminátor bájt zárja le. Az üzenetek maximális hossza 256 bájt, beleértve a parancs- és a terminátor bájtot is. A tartalom kódolása kötelezően UTF-8. Ha egyéb, nem ASCII kódolású karaktereket, vagy a parancson kívül vezérlőkaraktereket (<32) talál a szerver, megszakítja a kapcsolatot. Túl gyakran sem szabad üzeneteket (parancsokat) küldeni; ha 10 másodpercnél rövidebb időn belül 5-nél több üzenetet kap a szerver, megszakítja a kapcsolatot.

Az üzenetek típusai, azaz a parancsok a következőek (zárójelben a bájt értéke):

- HELLO (1). Ezzel az üzenettel köszön a szerver közvetlenül a csatlakozás után (közölve a verziószámát is), és a kliens számára is kötelező, hogy köszönjön a szervernek.

- NEPTUN (2). A kliensnek közölnie kell a NEPTUN kódját a szerverrel az üzenet tartalmában. A szerver ilyet nem küld, a kliens számára viszont kötelező, rögtön az általa küldött HELLO után.

- JELSZÓ (3). A kliensnek igazolnia kell a csatlakozásra való jogosultságát a jelszó közlésével, közvetlenül a NEPTUN kódja után. Ha ez is megtörtént, akkor a kapcsolata el van fogadva.

- SZERVER ÜZENET (4). A szerver megjegyzéseket, üzeneteket, iránymutatásokat küldhet. Ilyen üzenet csak a szervertől származhat, kliensek nem küldhetnek ilyet. A tartalmuk a felhasználó számára megjeleníthető.

- ÜZENET (5). Ezek a csevegés üzenetei. Amikor a kliens küldi a szervernek, akkor a teljes tartalom a csevegés egy sora, amelyet a szerver az összes többi kliensnek elküld. Amikor a szerver küld ilyet egy kliensnek, az egy másik kliens szövege; ilyen esetben a másik kliens NEPTUN kódból kikövetkeztetett neve, egy kettőspont, és a csevegés sora a tartalom. (Ebből következően az üzenet szövegének rövidebbnek kell lennie, mint egy protokollüzenetnek. A nevek legfeljebb 32 bájtosak.)

- PING (6). Ha túl sokáig inaktív egy kliens, a szerver ilyen üzenetet küld neki. A kliens is küldhet ilyet a szervernek, amely válaszolni fog rá.

- PONG (7). A kliensnek ezzel kell válaszolnia a szerver PING kérésére, vagy a szervernek a kliens kérésére.

- KIJELENTKEZÉS (8). A kliens ilyet kell küldjön a szervernek, mielőtt kijelentkezik.

- BELÉPÉS (9). Ha más felhasználó jelentkezik be a szerverre, akkor a szerver mindenkit értesít erről. Az üzenet tartalma a felhasználó neve. (A szerverre bejelentkezéskor BELÉPÉS üzenetek sorozatában kapja meg a kliens az éppen aktív felhasználók listáját.)

- KILÉPÉS (10). Más felhasználó kijelentkezése. A tartalma a felhasználó neve.

Egy példa párbeszéd a következőképpen néz ki, ahol az első oszlopban az üzenet küldője (kliens vagy szerver), a kacsacsőrök közötti szavak pedig a fenti bájtok értékeit jelentik:

Szerver: <HELLO>Helló, én a szerver vagyok.<TERM>
Kliens: <HELLO><TERM>
Szerver: <SZERVER ÜZENET>Add meg a NEPTUN kódodat!<TERM>
Kliens: <NEPTUN>MZPERX<TERM>
Szerver: <SZERVER ÜZENET>Add meg a jelszavad!<TERM>
Kliens: <JELSZÓ>99<TERM>
Szerver: <SZERVER ÜZENET>Üdvözöllek, Köb Üki, belépétél.<TERM>
Szerver: <BELÉPÉS>Dia Dóra<TERM>
Szerver: <BELÉPÉS>Makk Marci<TERM>
Kliens: <ÜZENET>Sziasztok!<TERM>
Szerver: <ÜZENET>Dia Dóra:Szia!<TERM>
Szerver: <ÜZENET>Makk Marci:hello<TERM>
Szerver: <PING><TERM>
Kliens: <PONG><TERM>
Szerver: <KILÉPÉS>Makk Marci<TERM>
Kliens: <KIJELENTKEZÉS><TERM>
Szerver: <SZERVER ÜZENET>Byez.<TERM>

A szerveren folyamatosan bent tartózkodik egy robot is, amely a tesztelést segíti. Neki kérdést lehet feltenni: a "?vicc" üzenetre egy béna viccet mond. A "?kilep" üzenetre kilép, aztán újra belép. Könnyen előfordulhat, hogy a tesztelés közben nem csak vele, hanem a szorgalmi más készítőivel is összefutsz! (A NEPTUN mindenkinek a saját NEPTUN kódja csupa nagybetűvel, a jelszó pedig a NZH pontszáma sztringként; aki nem írt, annak -1. Felsőbbévesek és oktatók is igényelhetnek hozzáférést. ☺)

Ez egy összetett, integráló jellegű feladat. Érteni kell hozzá az SDL-t, az eseménykezelést, a hálózatkezelést és a karakterkódolásokat; továbbá ki kell találni pár algoritmust is. De a honlapon szereplő anyagokból (és a lentebb SDL említett függvényeinek dokumentációjából) megcsinálható. A határidő után az elfogadott megoldások tulajdonosainak lesz egy buli, amelynek idejét és helyét (IP cím, port szám) később hirdetem ki. Ide mindenki a saját kliensével fog tudni csatlakozni!

A fejlesztés közben figyelj az alábbiakra. 1) Az SDL_Net az SDL eseménysorába nem illeszt be eseményeket, a kapcsolatot külön kell kezelni. Ugyanakkor az SDLNet_TCP_Recv() blokkol, mint a scanf(), ha nincs olvasható adat. 2) Ezért a kapcsolatot be kell tenni egy SDLNet_SocketSet-be, és SDLNet_CheckSockets() hívással figyelni, hogy érkezett-e adat. Közben foglalkozni kellhet a felhasználó billentyűlenyomásaival is! 3) A bejövő adatnál nem tudhatod előre, hányadik bájton lesz az üzenet végét jelző terminátor. Lehet, hogy egy Recv() alatt nem jön meg a teljes üzenet, vagy egy Recv() több üzenetet tartalmaz. Túl hosszú üzenetet viszont a szerver garantáltan nem fog küldeni. 4) Az üzeneteket esetleg tördelni kellhet a képernyőn, ha hosszabbak lennének, mint amennyi az ablakba fér. Javasolt fix szélességű betűkészlet használata, pl. http://infoc.eet.bme.hu/sdl/LiberationMono-Regular.ttf. 5) Extraként az üzeneteket a képernyőn időbélyeggel együtt jelenítheted meg, és/vagy színezheted azokat.

Halmaz típus bináris kereséssel

A feladat egy double számokat tároló halmaz típust létrehozni, amely a gyakon kidolgozott halmazhoz hasonlóan támogatja az elemek betevését, kiszedését, eleme-e vizsgálatát, továbbá a metszet és az unió képzését is. A használata az alábbi módon kell történjen:

Halmaz *h1, *h2, *metszet, *unio;

h1 = halmaz_uj();
halmaz_betesz(h1, 3.14);
halmaz_betesz(h1, 3.14);
halmaz_betesz(h1, 2.8);
printf("%s\n", halmaz_benne_van_e(h1, 3.14) ? "benne van" : "nincs benne");
printf("%s\n", halmaz_benne_van_e(h1, 8) ? "benne van" : "nincs benne");
h2 = halmaz_masolat(h1);
halmaz_kivesz(h1, 3.14);
halmaz_betesz(h1, 4);
halmaz_betesz(h2, 2.9);
metszet = halmaz_metszet(h1, h2);
unio = halmaz_unio(h1, h2);
halmaz_kiir(h1); /* 2.8 4 */
halmaz_kiir(h2); /* 2.8 2.9 3.14 */
halmaz_kiir(metszet); /* 2.8 */
halmaz_kiir(unio);  /* 2.8 2.9 3.14 4 */
halmaz_felszabadit(h1); halmaz_felszabadit(h2);
halmaz_felszabadit(metszet); halmaz_felszabadit(unio);

A halmaz legyen okos abban, hogy a tárolt elemeket a dinamikusan foglalt tömbjében rendezve tárolja! Ilyenkor a keresés O(log n) időben megoldható bináris kereséssel (O(n) helyett), a metszet és az unió képzése pedig O(n) időben összefésüléssel (O(n*n) helyett). Figyelj arra, hogy ne duplikálj kódot feleslegesen; ahol indokolt, használj segédfüggvényt!

Ez egy végiggondolós, de nem nehéz feladat. Az egyes részei akár vizsgafeladatok is lehetnének.

Várakozási sor

Várakozási sornak (puffernek, buffer) nevezzük azt a tárolót, amelynél az elemek sorrendjét megtartjuk, és amelynél új elemet mindig a tároló végére teszünk, elvenni pedig mindig a tároló elejéről veszünk el. Más néven FIFO-nak is nevezik ezeket (First In, First Out), mivel a tárolóból kivett elem mindig az, amelyiket a legelőször tettük be.

Így működnek a boltokban a kasszák: aki legelőször érkezett, ő kerül először sorra, az újonnan érkezők pedig a sor végére állnak. Jó esetben. ☺ Várakozási sort szokás alkalmazni akkor, amikor egy program vagy eszköz által feldolgozandó adatok időnként gyorsabban érkeznek, mint ahogyan fel lehetne őket dolgozni. Az SDL-ben az események (egér mozdulatok, billentyűzet) egy sorba kerülnek, arra várva, hogy a program feldolgozza őket. Itt fontos a sorrend megtartása: szép is lenne, ha a lenyomott billentyűk kódjait összekeverve kapnánk!

Puffert használnak az Interneten az útválasztókban is (router), amelyek a bejövő adatcsomagokat küldik tovább a céljaik felé. Ezekben egy ügyes implementációja van a várakozási sornak, ugyanis a csomagok érkezésének gyakorisága akár 10000/másodperc körül is lehet. Amikor túl nagy a forgalom, jobb híján ezek az eszközök a várakozási sorba be nem férő új adatokat egyszerűen eldobják.

A feladatod egy olyan várakozási sor modult készíteni, amelynek a maximális mérete véges, de tetszőlegesen nagy lehet: az adatszerkezet inicializálásakor adott. A cél az, hogy a várakozási sorba beszúrás és a sorból kivétel is a lehető leggyorsabb legyen; ezeknél a műveleteknél memóriafoglalásra várni, az adatokat ide-oda tologatni nincs idő. A sor használata az alábbi módon történjen:

IntSor sor1;
int i, j;

sor_inicializal(&sor1, 50);    /* 50 elemű lesz */
for (i=1; i<=60; ++i)
   printf("%d: %s\n", i, sor_beszur(&sor1, i) ? "sikerult":"nem sikerult");
for (i=1; i<=10; ++i)
   if (sor_kivesz(&sor1, &j))
      printf("kivettem: %d\n", j);  /* 1-10 */
printf("elemszam most: %d\n", sor_elemszam(&sor1)); /* 40 */
for (i=51; i<=55; ++i)
   printf("%d: %s\n", i, sor_beszur(&sor1, i) ? "sikerult":"nem sikerult");
printf("elemszam most: %d\n", sor_elemszam(&sor1)); /* 45 */
while (!sor_ures(&sor1)) {
   sor_kivesz(&sor1, &j);
   printf("kivettem: %d\n", j);  /* 11-55 */
}
sor_felszabadit(&sor1);

A beadott megoldásban nem kell több forrásfájlnak lennie (elég egy teljes program copypaste), de legyenek elválasztva benne a sor modulhoz és a főprogramhoz tartozó részek.

Bankautomata III.

A 6. heti gyakorlaton szerepelt egy bankautomatás feladat: http://infoc.eet.bme.hu/gy06.php#4, amelyben a bankautomata a rendelkezésre álló címleteket figyelembe véve, a legkisebb számú bankjeggyel próbált kiadni egy összeget.

Az algoritmus nem volt tökéletes. A hozzá tartozó megjegyzés így szól: „Pl. ha 6000-t kérünk, és van 5000-es és 2000-es, de nincs 1000-es, akkor [a bankautomata] ki akar adni egy 5000-est, és utána megáll – nem veszi észre, hogy 3 darab 2000-essel megoldható. A tökéletes megoldáshoz az ún. visszalépéses keresést kellene alkalmazni, amelyhez a tudnivalók majd később szerepelnek az előadáson.”

Oldd meg a feladatot visszalépéses kereséssel (backtrack)! Ennek a rekurzív módszernek a lényege az, hogy részmegoldásokat „építve” próbál haladni a teljes megoldás felé. Ha kiderül egy részmegoldásról, hogy helytelen, akkor mással próbálkozik. A bankautomatánál valahogy így néz ki a gondolatmenet: megoldásra vezet az, ha kiadunk egy 5000-est? Ha igen, adjuk ki! Ha nem, akkor ne adjuk ki, hanem próbálkozzunk anélkül.

A beküldött programod tartalmazzon egy struktúrákból álló tömböt a gyakorlaton megbeszélthez hasonlóan, címletekkel és darabszámokkal. Töltsd fel úgy a tömböt, hogy a 6000 forintot először 1000+5000 formában ki lehessen adni, másodjára már csak 2000+2000+2000 formában, harmadjára meg már sehogy sem! Hívd meg úgy a kiad() függvényedet, hogy ezek az eredmények látszódjanak a képernyőn!

Lissajous-görbék

Az előadás függvényrajzolójának szellemiségében készíts SDL-es vagy OpenGL-es grafikát használó programot, amely Lissajous-görbéket jelenít meg, és animál folyamatosan!

Olvasd el az erről szóló Wikipedia szócikket, vagy más írást! Röviden: ezek olyan görbék, amelyek pontjainak x, y koordinátáit is a szinusz függvény határozza meg; a két koordinátát meghatározó szinusz frekvenciája és fázisa viszont eltérő lehet. Ha f1=f2, és a két fázis között 90 fok a különbség, akkor pont egy kör alakul ki: x=sin(t+pi/2), y=sin(t) pont ugyanaz, mint x=cos(t), y=sin(t).

A program az animációhoz vegye figyelembe az idő múlását! Ehhez a koordináták képlete legyen sin(wt+f) alakú, ahol w a (kör)frekvencia, f a fázis, t pedig az időpont, amely folyamatosan növekszik. Válassz egy időintervallumot, ameddig visszamenőleg a görbe ki van rajzolva!

Vezérelhesse a felhasználó a rajzolást: a felfelé nyíl nyomva tartásával növelhesse a frekvenciák arányát (nem feltétlenül egész szám). A lefelé nyíl nyomva tartással pedig folyamatosan csökkenjen az arány. A fázis eltolását ugyanígy lehessen állítani a balra-jobbra nyilakkal.

Az ablak mérete legyen 480×480 pixel, amit töltsön ki majdnem teljesen a görbe! A kép tetején írja ki a program a frekvenciák arányát és a fázisok különbségét (fokban). Ezt a stringRGBA() függvénnyel tedd, hogy ne kelljen adatfájlt használni. Minden, ami nincs specifikálva, szabadon megválasztható (pl. színek).

Spacetelenítő – verseny

A gyakorlat anyagában szerepel egy sztringes feladat: egy függvényt kell írni, amely a paramétereként átvett sztringet úgy módosítja, hogy a benne lévő szóközöket kitörli. Ha a bemenet ez: " Ez egy sztring tele szóközökkel . " Akkor a kimenet: "Ezegysztringteleszóközökkel."

A feladat most ugyanez, azzal a kitétellel, hogy a függvény minél rövidebb kell legyen, vagyis a forráskódja minél kevesebb karakterből kell álljon.

A játékszabályok: 1) helyesen kell működnie minden C fordítóval, 2) pontosan egy paramétere kell legyen: a sztring, 3) ha könyvtári függvényt használ, az #include sor beleszámít a karakterek számába. A beadott forráskódnak tartalmaznia kell a rövidítés lépéseit is, vagyis a kitalált (és helyesnek ítélt) változatokat, továbbá egy rövid programrészt, amely teszteli a függvényt különféle sztringekre. (Legyen több szóköz egymás mellett, elején szóköz, végén szóköz stb.)

A legrövidebb függvényt beküldők csokit kapnak!

Titkos üzenet

A Bitturmix c. írás egy ideje elérhető a honlapon: http://infoc.eet.bme.hu/bitturmix.php. Ez egy egyszerű titkosítási eljárásról is szól, amiben a titkosítandó szöveg bitjeit véletlenszerűen invertáljuk. Ha még nem olvastad el, tedd meg.

Aztán képzeld el a következőt. Órára menet találsz egy pendrive-ot az út szélén. Ezen egy titok.txt nevű fájl van, amelynek tartalma a következő:

8d31a853092df982d20a410ff4fca091ac78819b2d9e2798
dad685fbf62b6adbc73f4b000d0a59508dc4383f6642c81c
92d19ba4a3340eb3fe90e3641a737937eee66495bc7272e9
11755bedb240bfc57b184e84469cb54fa526edc89f7436bb
e8445111a21737826c0318cb36115321d364d16611b2052f
390e771046ce9d3e59e97bb3ad86674f0d28549fc7a1fae6
4bb3d90ea1d22ee41992e0d2ac1167c275b7055ca784dab3
16926228534160acefd6db37b46b341ae2b6c59c5ac30c80
0488fbc0d3a57665ec3b012c90ffe0a515bd8465cf82c2c0
5ac5b8f553068e9c6608eafc96d5aad79dde8355f9b60ef4
61b7b92c7fb8e0ca913f2c7973cb37e9932d1c5704f5bb8a
135ecd4258356d597b24da31d521ec855c8d078894f0ec0d
0c2c717eb700345677f7b3ed8ec11ff83c5efedde225d3fd
399afb9d8d342eaa060dc06fe7d33f0b43bfef142eb502c3
fa29df81cfc992f35eb342cdfd1e83b62b00ebdf24e5336a
fe221dcd18d1ac15a2c8a11ab4ca5dbd163d13f5c4f012fb
e207505b16477fc2cb32c49d9ff313d982eec1c849e6933e
8fc8d3e291d5de88438982664cf31f7a8ca780e411c64186
8edae648c0edf26f7d21063dc41b038b95adce2acfc18015
098ec02a9b60aef443447f2ca05df846eccfa14a8240f353
1d13f7c25e94b1798be83216064639a7

Ezek a hexadecimális számjegyek valamiféle üzenetet tartalmazhatnak, csak a szöveg titkosítva van. Pár lépéssel arrébb a pendrive szórakozott tulajdonosa elhagyott egy papírfecnit is. Ezen meg az 1103515245 és a 12345 számokat látod.

A feladatok a következők.

– Derítsd ki, mik ezek a számok. Ha rájöttél, tudni fogod, mit kell velük csinálni.

– Írj egy programot, amelynek a forráskódjába be van építve a fenti üzenet. (Ha kell, előfeldolgozhatod.) Keresse meg a program próbálgatással a titkosítás kulcsát! Ha megvan, írja ki a képernyőre a kulcsot és a dekódolt üzenetet! Légy türelemmel, ez eltarthat jó 5-10-20 másodpercig.

Töltsd fel az így kapott programot, mint megoldást!

Mare Tranquillitatis

1969. július 20. Neil Armstrong és Edwin Aldrin sikeresen leszálltak a Holdon a Sas (Eagle) nevű holdkomppal a Nyugalom tengerén (Mare Tranquillitatis).

Ez nem volt egyszerű feladat. Találniuk kellett egy olyan helyet, ahol a terep teljesen sík, és oda letenni a Sast. Mindezt egy nagyon szűkös üzemanyagkerettel. Mindent elsőre kellett jól csinálni. Neil Armstrong, eredeti foglalkozása szerint berepülőpilóta, ügyesen csinálta ezt: amikor meglátta, hogy az eredetileg kijelölt leszállóhely sziklákkal van tele, oldalirányú sodródásba kormányozta a kompot, hogy új helyet keressen. Így mire sikerült a leszállás, az extra manőver miatt a komp tankjában már csak 20 másodpercre elegendő üzemanyag maradt.

Teljesen a talajig nem is volt szabad leereszkednie a komppal, ugyanis ha túlzottan megközelítették azt a bekapcsolt hajtóművel, akkor a kiáramló gázcsóva felborította volna a kompot. Ezért annak lábain kb. másfél méter hosszú érintőpálcák voltak, amelyek érzékelték a talajt. Érintéskor kigyulladt a „contact light” lámpa, és ki kellett kapcsolni a hajtóművet. A maradék másfél métert szabadesésben tették meg. Ez nem volt akkora probléma, mint a Földön lett volna, hiszen a Holdon jóval kisebb a gravitáció.

Az allegrós (esetleg OpenGL-es vagy SDL-es, más ne legyen!) programodban a pilóta feladata a következő. A program kirajzol oldalnézetben (2D grafika) egy hepehupás felszínt, amelyen van valahol egy leszállásra alkalmas, sík terület. Ide kell navigálnia a holdkompot a balra, jobbra (oldalirányú gyorsítás), felfelé (hajtómű erősebben visz felfelé), szóköz (hajtómű kikapcsolása) billentyűkkel. A pilóta az alábbi visszajelzéseket kapja a műszerfalon: magasság, x és y irányú sebesség, kontakt fény.

A sikeres leszállás feltételei a következők:

– Nem szabad ferde terepre leszállni.

– Bekapcsolt hajtóművel nem szabad túl közel kerülni a talajhoz.

– A leérkezés pillanatában nem lehet túl nagy a vízszintes irányú sebesség (mert a komp felborul).

– A leérkezés pillanatában nem lehet túl nagy a függőleges irányú sebesség sem (mert akkor a komp lábai összecsuklanak).

– Ha elfogy az üzemanyag, a holdkomp lezuhan.

Figyelj arra, hogy a billentyűkkel nem közvetlenül a komp helyzetét, de még csak nem is a sebességét lehet irányítani, hanem a gyorsulását.

A programkód legyen szép! Használd az eddig megtanult nyelvi eszközöket, ahol alkalmasak. Enélkül a megoldás nem elfogadható (pl. egy darab main() függvény kismillió változóval, rengeteg sorral).

(Nehezített változat a játékban és a programozásban is: a jobbra-balra gombokkal nem a vízszintes gyorsulást lehet szabályozni, hanem a holdkomp elfordulását. A gravitáció mindig a felszín felé hat, a felfelé gombra a hajtómű mindig a holdkomp aljának irányába bocsájtja ki a gázcsóvát – ami viszont az elfordulás miatt nem feltétlenül a felszín felé mutat.)

BF fordító

Ha még nem nem olvastad volna, nézd meg az algoritmusokról szóló írást: http://infoc.eet.bme.hu/turing.php és a Brainfuck nyelvről szóló írást http://infoc.eet.bme.hu/bf.php.

A feladat egy BF fordítóprogram írása. A fordítóprogram a szabványos bemenetén átvesz egy tetszőlegesen hosszú, BF nyelvű programot, amely legfeljebb 32768 utasítást (nem komment karaktert) tartalmaz. A szabványos kimenete pedig egy C nyelvű forráskód, amelyik pontosan ugyanazt csinálja, mint az átvett BF program.

A fordítóprogram nem fogadhat el szintaktikai hibás programot. Mivel a ciklusokon kívül semmi másra nézve nincsen megkötés a BF nyelvben, ez azt jelenti, hogy a ciklusok helyes egymásba ágyazottságát kell ellenőrizni (pl. "][" egy helytelen BF program.) A lefordított program ugyanúgy kell működjön, mint az interpretált. A szalag cellái előjeles bájt típusúak, és indításkor mindegyiknek nulla az értéke. A szabványos bemenet vége esetén a BF programnak a -1 értéket kell adni. (A szalag túltekerését most nem kell ellenőrizni.)

Eddig könnyű lenne, úgyhogy vannak nehezítések. Az első nehezítés az, hogy a fordítónak mikrooptimalizációkat kell elvégeznie a programon:

1. Az egymás melletti +- és -+ utasítások hatástalanok, kiejtik egymást. Ugyanez a helyzet a <> és >< párosokkal. Ezeket ki kell hagyni.

2. Egymás utáni ++++ és ---- karakterek a C kódban összevonandóak. Itt például olyan C utasítást kell használni, amely 4-gyel növeli vagy csökkenti a számot, ahelyett, hogy négy egymás utáni utasítás (egyesével növelés) jelenne meg a kódban. Ugyanez a > és < utasításoknál.

3. A nullázó ciklust "[-]" ki kell cserélni egy konkrét értékadásra: nullázásra.

A második nehezítés pedig: a C programban nem szabad sem while, sem for ciklust használni, hanem goto utasításokkal kell megoldani a ciklusszervezést. Ennek szintaktikája az alábbi:

cimke1:       /* tetszőlegesen sok címke lehet a kódban, kettőspont van utána */
  ...         /* utasítások */
goto cimke1;  /* ugrás cimke1-hez */

Annak ellenére, hogy ciklusok már nincsenek az előállított C kódban, annak külalakja legyen szép! A behúzások mutassák a vezérlési szerkezeteket: a ciklusok belseje kezdődjön annyiszor három szóközzel beljebb, ahányszorosan egymásba vannak azok ágyazva.

Megjegyzések.

1. Ha esetleg úgy tesztelsz, hogy a programod fájlokat nyit meg, és azokkal dolgozik, a beadott programban ezt töröld, de legalább kommenteld ki. Szabványos bemenetről szabványos kimenetre kell dolgoznia a programnak, minden egyéb kiírás és beolvasás nélkül.

2. A szokásos módon a feladat megoldható az eddig tanult C nyelvi elemekkel. Dinamikus memóriakezelésre nincsen szükség. A BF programot érdemes egy saját, belső jelölésűre átalakítani: pl. úgy, hogy minden utasításhoz tartozik egy lépésszám is. Úgy könnyebb az optimalizálás, és olvashatóbb a program!

3. A goto utasítást ciklusszervezésre csak ebben a feladatban szabad használni, mindenhol máshol a Prog1 tárgyban tilos. :D

++++++++[>++++++++<-]>++.++++.

A címben szereplő karakterek – ez nem a portál hibája, hanem 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: http://infoc.eet.bme.hu/turing.php és a Brainfuck nyelvről szólót http://infoc.eet.bme.hu/bf.php. Ezek kellenek a feladat megértéséhez.

Ugyanis a feladat egy BF értelmező írása C-ben. Vagyis 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:

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. (Vigyázat! Nem triviális algoritmus. Haladóknak: ehhez nem kell rekurzió.)

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 szabványos kimenete, egyéb dolgot pedig ne írjon 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. 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”.)

Jó szórakozást!

Angry Birds

A laboron jó sokat gyúrtuk a ferde hajítás iskolapéldát – most jön azoknak a feladatoknak a folytatása.

A feladat a következő. Adott egy Angry Birds pálya, amelyen a madarat adott szögekben és sebességekkel lehet kilőni. Írnod kell egy programot, amely kiszámítja és megjeleníti azokat a (szög, sebesség) kombinációkat, amelyekkel el lehet találni a malacot! Csak a telitalálatok érnek, a terep nem. (Ütközéseket nem kell számolni.) A program szabványos kimenetén egy darab SVG rajznak kell megjelennie, 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.

Az SVG minden síkidomát neked kell kiszámítanod, rajzolóprogramot ne használj! (A koordináták amúgy is ismertek kell legyenek, hiszen ezek az egyenletek megoldásához is szükségesek.) 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 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! 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">
  <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 http://www.w3schools.com/svg/svg_example.asp oldalt. Javasolt tesztelés közben a képnéző programban megnyitva tartani a képet: a legtöbb tudja azt, hogy érzékeli, ha a fájl megváltozott, és újrarajzolja.

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 rajz viszont ronda lesz, az SVG fájl pedig irreálisan nagy, ha ott túl kicsi az időlépés.

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/s2. A kilövés szöge 10° és 80° 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.

Jó szórakozást!

Fizz buzz puzzle

Az előadás fizzbuzz programja alapján írj olyan C programot, amelyik soronként írja ki a számokat egymás után 1-től 1155-ig. 3-mal oszthatók helyett a fizz, 5-tel a buzz, 7-tel a banana, 11-gyel oszthatók helyett pedig a bumm szó jelenjen meg. 15-tel oszthatók helyett fizzbuzz, 21-gyel oszthatók helyett fizzbanana, 33-mal oszthatók helyett fizzbumm, és így tovább. A kiírás azért tartson 1155-ig, mert ez a szám az első fizzbuzzbananabumm.

A puzzle rész: a programnak rövidnek kell lennie. Olyan vezérlési szerkezetet kell találnod, amellyel a program nem hosszabb 20 sornál, miközben minden definíciós, vezérlési és kifejezés utasítás külön sorban van!

Kismutató a kettesen…

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), és a rendes, mai böngészők 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: http://www.w3schools.com/svg/svg_rect.asp. A fenti fájlból egyébként az alábbi kép lesz.

A feladat egy program írása, amely három számot vár a szabványos bemenetén (scanf), szóközzel elválasztva. Ezek egy időpontot mutatnak: óra, perc, másodperc. Beolvasásuk után kiír a szabványos kimenetére (printf) egy órát ábrázoló SVG fájlt, amelyben minden koordinátát maga számolt ki. Az órán legyen meg mindhárom mutató! A mutatók ne mindig pontosan az egész órára mutassanak! (Ha pl. fél kilenc van, a kismutató a nyolcas és a kilences között van középen.) A számlapról ne hiányozzanak a percenkénti osztások sem, sőt az egész órákhoz tartozó osztásokat lehessen megkülönböztetni a többitől!

A díszes, színes órákat szeretjük (választhatsz saját színeket, vonalvastagságokat stb.), de programozóként legfontosabb a specifikáció pontos követése! Figyelj arra, hogy a program kimenetét átirányítva szabályos SVG fájlt kapj! A feladat megoldása nem rövid, de az összes szükséges tudás szerepelt már az előadáson. A beadás módja: a szövegablakba bemásolt C forráskód.

Gyököt számoló masina

Az előadáson bemutatott faktoriálist számoló gép mintájára: http://infoc.eet.bme.hu/ea01.php#13 rajzolj egy olyan gépet, és készíts hozzá használati utasítást, amely egy szám gyökét tudja meghatározni. A megvalósítandó algoritmus Hérón módszere, a 11. dián jobb oldalt: http://infoc.eet.bme.hu/ea01.php#11. Vagyis egy kezdeti tipp (ami lehet 1) után a gép javítsa a tippet a (tipp+szám/tipp)/2 átlagolással, egészen addig, amíg 0,001 pontossággal meg nem közelíti a gyököt.

Lefényképezett/szkennelt kézi rajznak is örülök, csak legyen lekicsinyítve: a fájl mérete ne legyen nagyobb fél megabájtnál!