A programozás alapjai 1. BMEVIHIAA01
Nagy HF ké szı́té si ú tmutató Analízis és Specifikáció (Nyelv független) 0. 1. 2. 3. 4. 5. 6. 7. 8.
A Házi feladat témája A Házi feladat téma szöveges leírása A feladat résztvevőinek azonosítása A résztvevők közti kapcsolatok elemzése A résztvevők alapvető tulajdonságai Alapvető feladatok A fájlok tartalma Minta Specifikáció Adatszerkezetek leírása
Tervezés (C nyelv) 9. 10. 11. 12.
Szükséges tulajdonságok és adattípusok összerendelése Adatszerkezetek megvalósítása Alap funkciók ismertetése További funkciók és számítások
Implementálás (C nyelv) 13. 14. 15. 16.
Adattípusok elkészítése Függvények megírása Adatok mentése/visszatöltése fájlból. A konkrét feladat megoldása függvényként
Nagy HF pé lda Analízis (Nyelv független)
0.
A Házi feladat témája
Formula-1 1.
A Házi feladat téma szöveges leírása •
•
•
•
Mindenképpen tartalmazza, hogy a programot Ki és elsősorban Mire fogja használni? A Forma-1-es program esetében egyáltalán nem mindegy, hogy a nézők tájékoztatására, a Forma-1es pilótáknak, vagy éppen a mérnökök számára készítjük a programot. o A példában a nézők tájékoztatására írjuk, a programot elsősorban a kommentátorok használják majd. Tisztázzuk, hogy miből mennyi adatot szeretnénk nyilvántartani. Egy futam vagy több futam eredményei? Egy futam Időmérő eredmények vagy a verseny eredmények, esetleg mind a kettő? a verseny eredményei Versenyzők száma? több Csapatok kezelése? Nem Kiállások kezelése? Igen Szektoridők kezelése? Nem Írjunk fel néhány kérdést, amelynek megválaszolására a programot szeretnénk felkészíteni. Kezdjük a legalapvetőbb kérdésekkel, utána mutassunk összetettebb példákat is. o Ki nyerte a futamot? o Mennyi idővel nyert a nyertes? o Ki futotta a leggyorsabb kört? o Kinél tartott legrövidebb ideig a kerékcsere? o Ki lett az első három helyezett? o Kik estek ki a futamon? o Ki vesztette a legtöbb helyezést a rajtpozíciójához képest? o … Ezután válasszunk ki 1-2 bonyolult kérdést, amivel a program képességei szeretnénk megmutatni o Ki volt az a versenyző, aki a x. körben a leggyorsabb kört futotta? o Melyik pilótának volt a legtöbb előzése a futamon?
2.
A feladat résztvevőinek azonosítása A feladat szempontjából lényeges résztvevőket kell azonosítani, nem biztos, hogy élőlény, lehet például Tantárgy, Szoba, Nyeremény stb. Ehhez célszerű a feladatban szereplő főneveket elemezni. Ha valamelyik felesleges, vagy pedig hiányzik valami, az később úgyis ki fog derülni. A feladat szövegéből a következő résztvevőket azonosítottam (3-4 résztvevőnél több ne legyen): • Verseny • Versenyző • Időeredmény
3.
A résztvevők közti kapcsolatok elemzése Kapcsolat típusa lehet: 1:1, 1:több, több:több i. Verseny – Versenyző (a versenyen több versenyző versenyez) → 1:több ii. Versenyző – Időeredmény (egy versenyzőhöz több időeredmény tartozik) → 1:több Ha a résztvevőket jól azonosítjuk, akkor a kapcsolatok feltérképezése is egyszerű feladat. Vesszük az összes lehetséges résztvevőt, és megnézzük, hogy közöttük értelmezhető-e valamilyen kapcsolat, ha igen, akkor felvesszük a listára. Amennyiben tévedünk, akkor a feladathoz feltett kérdéseinkkel próbáljunk rájönni a hibára. Hiba: az időeredmény helyett csak annyit írunk fel, hogy eredmény a résztvevőkhöz. Ekkor a verseny – eredmény (1:1) kapcsolat is értelmezhetőnek tűnik, hiszen a versenynek is van eredménye. Ellenben, ha megnézzük, a kérdéseinket, akkor abból világosan látszik, hogy szükségünk van a részeredményekre is. A verseny eredménye pedig a részeredményekből adódik majd össze. Probléma0: Mi az eredmény? Megoldás0: Hát az attól függ, hogy milyen versenyről van szó. A Formula-1-ben a futamon az nyer, aki először halad át a célvonalon, tehát, aki a legrövidebb idő alatt teljesíti a versenyt. A verseny - időeredmény kapcsolat pedig már nem értelmezhető, csak versenyzőnként ezért a versenyző – időeredmény kapcsolatot vettük fel. Amennyiben a mindkét irányban értelmezett kapcsolatok közül (Pl: Versenyző – Időeredmény 1:T / Időeredmény – Versenyző 1:1) az egyik egyértelmű (1:1), akkor ez szintén elhagyható.
4.
A résztvevők alapvető tulajdonságai Verseny: Helyszín: szöveg Körök száma: egész szám Versenyző: Rajtszám: egész szám Név: szöveg Rajtpozíció: egész szám Időeredmény: Idő: Idő, ezred másodperc pontossággal Típus: köridő / boksz kiállás ideje
5.
Alapvető feladatok Itt kell meggondolni, hogy milyen alapvető feladatokra lesz szükségünk az adatok kezeléséhez, amit résztvevőnként célszerű felsorolni. • • • •
6.
Verseny adatok felvétele. Versenyző felvétele a versenyhez Versenyző törlése a versenyből (például nem minden versenyző indul végül a futamon) Időeredmény felvétele a versenyzőhöz
A fájlok tartalma A verseny és a versenyzők adatait egy szöveges fájlban tároljuk el, míg a versenyzők időeredményeit bináris fájlból olvassuk be. A fájlok a következőképpen néznek ki:
„Verseny.txt” 1. sor: Verseny helyszín: szöveg
Monaco
2. sor: Körök száma: egész szám
78
3. sor: Üres sor 4. sortól: Rajtpozíció
Rajtszám
1 7 MSC
Versenyző neve (3 karakter)
2 2 WEB 3 8 ROS 4 4 HAM 5 10 GRO 6 5 ALO 7 6 MAS 8 9 RAI 9 18 MAL 10 1 VET …
„Ido.dat” Rajtszám: előjel nélküli egész Idő: tört szám Típus: 1 karakter (’K’=köridő, vagy ’B’=boxkiállás ideje)
Házi Feladathoz Specifikációt kell készíteni és beadni!!! A Specifikáció az Analízis rész eredményének leírását tartalmazza!
7.
Specifikáció
Formula-1 A feladat egy Formula-1-es verseny adatait rögzítő program készítése. A program a nézők számára szolgáltat hasznos információkat egy Formula-1-es futamról. A program csak a versenyben szereplő adatokat dolgoz fel, az időmérő edzésen elért időeredményekkel nem foglalkozik. A program a versenyen résztvevő összes versenyző eredményeit képes kezelni. A versenyzők csapataival a program nem foglalkozik. A program képes versenyen elért köridőket és a kiállások idejét is kezelni, a szektoridőket viszont külön nem tartja nyílván. A program az kérdéseket a pilótákhoz rendelt köridők, illetve a bokszkiállások ideje alapján képes megválaszolni. A versenyen több versenyző is indulhat, továbbá minden versenyző összes bokszkiállását, illetve köridejét a program nyilvántartja. A program a kérdés megválaszolásához a szükséges adatokat 2 adatállományban tárolja. Az egyik szöveges és a következő adatokat tartalmazza: Az első sorban a Verseny helyszínét szöveges formátumban, majd a következő sorban a verseny köreinek számát egész számként ábrázolva, a következő sor üres, a további sorokban a versenyen induló versenyzők Rajtpozíciója (egész szám), Rajtszáma (egész szám), valamint a Versenyző 3 betűs kódja szerepel tabulátorral elválasztva egymástól. A másik állomány bináris, melyben az időeredményeket tároljuk. Az állomány minden tagja egy-egy időeredmény bejegyzésnek felel meg, amely a következőket tartalmazza rendre: Rajtszám(egész szám), Időeredmény(törtszám), Típus (’K’ vagy ’B’ karakter) A program konkrét feladata, hogy a következő kérdésre tudjon válaszolni:
„Ki volt az a versenyző, aki a 23. körben futotta a leggyorsabb körét?”
8.
Adatszerkezetek leírása Itt a feladatban szereplő résztvevők közti kapcsolatokból érdemes kiindulni. A résztvevők természetes kapcsolatait célszerű az adatszerkezetnek is követnie. A végeredménynek tartalmaznia kell: •
•
•
•
A feladat részvevőinek darabszámát a feladat specifikációja szerint: o biztosan csak van o több darab, de előre tudható, hogy pontosan mennyi o több darab, de számuk előre nem ismert A résztvevők közt milyen kapcsolat van o 1:1 o 1:több A kapcsolatot milyen egyedi azonosító biztosítja, amennyiben nem találunk ilyet, akkor vegyünk fel valamilyen egyedi azonosítót. Amennyiben egyértelmű a kapcsolat, akkor ez elhagyható. Ellenőrizzük, hogy a specifikációban szereplő fájlok tartalmazzák-e a kapcsolatok biztosításához szükséges azonosítókat! Adatszerkezetek ábrázolása
A végeredmény tehát az összefüggő adatokat rendszerezve mutatja be, ami a kérdések megválaszolását segíti. Az egymástól független adatok pedig külön-külön adatszerkezetet alkotnak.
A Forma-1 feladat adatszerkezete Résztvevők: Verseny, Versenyző, Időeredmény Darabszámok: Verseny: biztosan egy darab van belőle (a specifikáció szerint) Versenyző: több darab, de számuk előre nem ismert (a specifikáció nem tartalmazta, hogy biztosan 24 versenyző indul a versenyen) Időeredmény: több darab, de számuk előre nem ismert Kapcsolatok: Verseny – Versenyző (a versenyen több versenyző versenyez) → 1:több Versenyző – Időeredmény (egy versenyzőhöz több időeredmény tartozik) → 1:több Kapcsolatazonosítók: Verseny – Versenyző: nem szükséges, mert biztosan egy darab verseny van, amin a versenyzők indulnak Versenyző – Időeredmény: a kapcsolatot a Rajtszám biztosítja (mind a két fájl tartalmazza) Megjegyzés: az időeredményeket típustól függetlenül együtt tároljuk.
Adatszerkezetek ábrázolása: Az előzőek alapján egyetlen összefüggő adatszerkezet jött létre. Látható, hogy az adatszerkezet nem feltétlenül a fájlokban eltárolt adatoknak megfelelő szerkezetet követi, hanem a kérdések megválaszolását segíti az adatok rendszerezésével.
Verseny Helyszín: Monaco Körök száma: 78
Versenyző
Időeredmény Időeredmény Időeredmény Időeredmény Időeredmény Időeredmény
Rajtszám
Versenyző
Típus: köridő
Versenyző
Idő: 01:11.762
Versenyző Versenyző Versenyző Név: HAM Rajtszám: 4 Rajtpozíció: 4
Rajtszám
Időeredmény Időeredmény Időeredmény Időeredmény Időeredmény Időeredmény Típus: köridő Idő: 01:12.242
Rajtszám
Időeredmény Időeredmény Időeredmény Időeredmény Időeredmény Időeredmény Típus: Boxkiállás Idő: 00:03:335
Miért jó az adatokat rendszerezve tárolni a memóriában? A példánkban bemutatott Formula-1-es futamon a versenyzők száma 24, a köridők várható száma versenyzőnként 78 (amennyiben nem esik ki senki), a boksz kiállások száma versenyzőnként 2-3. Ez azt jelenti, hogy 24 versenyző, és versenyzőnként 81 db időeredményre számítunk, ami összesen 1944 időeredményt jelent. Kérdés: Hányadik körben futotta a leggyorsabb körét Alonso? Megoldás az adatok rendszerezésével: a) Ki kell keresni a pilóták közül Alonso-t (max.: 24 lépés, ha éppen ő az utolsó) b) Ki kell keresni a leggyorsabb köridőt, Alonso idejei közül. (81 lépés) Megoldás rendszerezés nélkül: 1. Ki kell keresni a pilóták közül Alonso-t, hogy megtudjuk a rajtszámát (max.: 24 lépés) 2. Ki kell keresni a leggyorsabb köridőt, az összes idő közül kiválogatva Alonso idejeit (1944 lépés) A rendszerezés előnye: Minden olyan kérdésre, amely egy konkrét versenyzőre vonatkozik megoldható maximum 24+81 = 105 lépésben, egyébként pedig 1968 lépés (majdnem ~20x annyi!!!)
Tervezés (C nyelv)
9.
Szükséges tulajdonságok és adattípusok összerendelése A feladat résztvevőihez mindenképpen az adott nyelven leírt (jelenleg a C nyelv) új típust fogunk létrehozni. A résztvevők tulajdonságait, pedig meg kell feleltetni az adott nyelv valamely egyszerű alap típusának, illetve ennek hiányában új egyszerű, vagy összetett típust létrehozni.
Specifikációban szereplő típus
C nyelv típus
Megjegyzés
Verseny: Helyszín: szöveg
struct verseny char helyszin[50] ,vagy char *helyszin unsigned int korok
fix, vagy változó maximum 50 karakter
Körök száma: egész szám Versenyző: Rajtszám: egész szám Név: szöveg Rajtpozíció: egész szám
struct versenyzo unsigned int rajtszam char nev[4] unsigned int rajtpoz
Időeredmény: Idő: Idő, ezred másodperc pontossággal
struct idoeredmeny double ido
Típus: köridő / boksz kiállás ideje
char tipus
3 karakter + ’\0’. Pl: VET’\0’
Ehhez nincs beépített típusunk, ezért nekünk kell készíteni, esetleg felhasználhatjuk a double-t. ’K’ vagy ’B’ karakter
10. Adatszerkezetek megvalósítása Itt lehet az adatszerkezetek konkrét megvalósítását az adott nyelven megtervezni, figyelembe véve a korábbi adatszerkezet leírást. Verseny A feladat specifikációja szerint csak egy verseny eredményeit szükséges kezelnünk, így erre külön adatszerkezetet nem szükséges létrehozni. Versenyzők Azon adataink számára, melyekből többet kell eltárolni, illetve feldolgozni választanunk kell a tároláshoz szükséges egyszerű adatszerkezetek közül. A versenyzők tárolására többféle adatszerkezet is szóba jöhet: a) Tömb b) Egyirányú láncolt lista i. rendezve / rendezetlenül ii. strázsával / strázsák nélkül c) Kétirányú láncolt lista i. rendezve / rendezetlenül ii. strázsával / strázsák nélkül d) Bináris fa i. rendezve / rendezetlenül e) Egyéb A fix méretű tömb nem jó választás, mert a specifikáció szerint nem fix az indulók száma, így ez nem elég rugalmas, ugyanakkor pazarló is lehet. Rendezve, vagy rendezetten tároljam a versenyzőket? A versenyzők rajtszám szerinti rendezése segíti a keresést, az idők beszúrásához. A verseny végeredményét viszont a helyezések sorrendjében lenne jó látni. Tehát több kulcs szerint kéne rendezni, de a második kulcs csak a futam végén lesz meg. A rajtszám szerinti rendezésre bináris fát használva a keresés átlagos lépésszáma log2(24) ~ 4,585, rendezés nélkül 12. Ez nem jelent túlzottan nagy különbséget, ezért most az egyszerűbbet választjuk. A könnyebb kezelhetőség miatt viszont a láncolt listát 2 strázsával valósítjuk meg. A helyezések szerinti rendezést pedig majd a futam vége után előállíthatjuk a listát rendezve vagy indexeléssel. Megjegyzés: Amennyiben az egy versenyen indulók száma jelentősen nagyobb lenne, akkor megfontolandó a bonyolultabb, de hatékonyabb adatszerkezet megvalósítása.
Időeredmények Az időeredmények tárolása versenyzőnként történik. Az időeredmények körről-körre sorban érkeznek, és ebben a sorrendben célszerű tárolni is őket. Rendezni tehát nem szükséges, ezért egy egyszerű egyirányú láncolt listát nyugodtan használunk, aminek mindig a végére kell majd beszúrnunk, hogy a sorrend megmaradjon. Az egyirányú láncolt lista végére történő beszúráshoz, azonban mindig végig kell menni a lista elemein, ami viszont költséges lehet. A kétirányú láncolt lista alkalmazását viszont semmi nem indokolja igazán. Ezért felveszünk versenyzőnként +1 mutatót a láncolt listához, ami az utolsó érvényes időeredményt mutatja. A beszúrást így mindig a mutatott elem után kell majd elvégezni (a lista végigjárása nélkül), és strázsákra sem lesz szükségünk. A megvalósítandó adatszerkezet A kialakult adatszerkezet tehát a következőképpen néz ki: A verseny egyetlen struktúrával leírható, melyben a verseny adatai mellett a versenyen induló versenyzők láncolt listájára mutató mutatót is elhelyezünk. A versenyzőket egy kétstrázsás rendezetlen egyszeresen láncolt listában tartjuk nyílván, amelyben a versenyzők alap adatai mellett a versenyzők időeredményeit tartalmazó egyszeres láncolt listára való mutatót is elhelyezünk, továbbá a beszúrás könnyítésére, az utolsó időeredményre való mutatót is. Az időeredmények pedig egyszerű strázsa nélküli láncolt listát alkotnak, mely eleje a versenyzőknél kezdődik. Az így kialakult adatszerkezetet nevezzük „Fésűs listának”. Melyben az egyik láncolt listából („fésű gerince” = versenyzők) egy másik láncolt lista indul ki („fésű fogai” = időeredmények) így kapcsolva össze az egymáshoz tartozó adatokat (a versenyzőket a hozzájuk tartozó időeredményekkel).
Az adatszerkezet grafikusan ábrázolva
11. Alap funkciók ismertetése Ezen funkciók közé tartoznak az adatszerkezet felépítésével, lebontásával, módosításával kapcsolatos funkciók. Új elemet létrehozó függvények Verseny* uj_verseny(char *helyszin, unsigned korok); Versenyzo* uj_versenyzo(char *nev, unsigned rajtszam, unsigned rajtpoz); Idoeredmeny* uj_idoeredmeny(char tipus, double ido);
Az adatszerkezet létrehozásához szükséges függvények Versenyzo* uj_versenyzo_lista(); void versenyzo_felvitel(Versenyzo* lista, Versenyzo* versenyzo); Versenyzo* versenyzo_keres(Versenyzo* lista, unsigned rajtszam); int ido_felvitel(Versenyzo* lista, unsigned rajtszam, Idoeredmeny* ido);
Az adatok mentésére és visszatöltésére szolgáló függvények int versenyzok_ment(char *fajlnev, Verseny* verseny); int idoeredmenyek_ment(char* fajlnev, Idoeredmeny* lista); Verseny* verseny_beolvas(char* fajlnev); int idoeredmenyek_beolvas(char* fajlnev, Versenyzo* lista);
12. További funkciók és számítások Ilyen funkciók lehetnek keresési és kiválasztási feladatok, melyek a résztvevők közül valamely alap tulajdonság alapján keresnek, választanak ki egyedeket. Ide tartoznak az egyéb számításokhoz használt függvények (távolság számítása pontok között, idő kezelésére óra/perc/másodperc/ezredmásodperc alapon, stb), valamint a teszteléshez, kiíratáshoz szükséges függvények. Példák: Mennyi idő alatt teljesítette a versenyt egy adott pilóta? double verseny_ido(Versenyzo* versenyzo);
Hányadik körben futotta a leggyorsabb kört egy adott pilóta? unsigned leggyorsabb_kor(Versenyzo* versenyzo);
Versenyzők rendezése idő szerint void rendezes_ido_szerint(Versenyzo* lista);
Másodperc alapú idő alapján az órák/percek számítása unsigned ora (double sec);
Versenyző kiíratása a képernyőre void kiir_versenyzo(Versenyzo* versenyzo);
Hányadik körben futották a leggyorsabb körüket a versenyzők? void leggyorsabb_kor_szamitasa(Versenyzo* lista); //Hol az eredmény???
Hol tároljuk a számítások eredményeit? Célszerű azokat az eredményeket, amiket minden résztvevőre szükséges kiszámítani a megfelelő résztvevő tulajdonságai között tárolni, így nem szükséges ehhez külön adatszerkezetet létrehozni, csak a már meglévő tulajdonságokat kell bővíteni az eredményekkel.
Implementálás (C nyelv)
13. Adattípusok elkészítése Készítsük el az feladatban szereplő résztvevők típusait, azok alap tulajdonságaival, az adatszerkezethez szükséges kapcsolatokkal , továbbá készítsük fel az eredmények tárolására. A versenyző típus létrehozása typedef struct Versenyzo { unsigned int rajtszam; char nev[4]; unsigned int rajtpoz; Idoeredmeny* start; Idoeredmeny* veg; struct Versenyzo* kov; double verseny_ido; unsigned leggyorsabb_kor; }Versenyzo;
14. Függvények megírása A tervezésnél meghatározott függvényeket kell implementálni. Üres versenyző lista létrehozása Versenyzo* uj_versenyzo_lista() { Versenyzo* eleje; Versenyzo* vege; eleje = uj_versenyzo(…); vege = uj_versenyzo(…); eleje->kov=vege; return eleje; }
Idő felvitele egy versenyzőhöz int ido_felvitel(Versenyzo* lista, unsigned rajtszam, Idoeredmeny* ido) { /* Elkészíteni */ return 1; }
15. Adatok mentése és visszatöltése fájlokból Az adatok mentésére és visszatöltésére készített függvényeket is tartalmaznia kell a megoldásnak. A feladatokhoz legalább két fájl feldolgozása szükséges, melyből az egyik bináris, a másik, pedig szöveges. A különböző függvények és algoritmusok dokumentálása történhet folyamatábrával, struktogrammal, vagy pszeudokóddal is.
Versenyzők beolvasása Időeredmények hozzáadása Fájl megnyitása Ha sikerült a fájl megnyitása akkor ciklus amíg(az időeredmények beolvasása sikeres) Keressük ki a most beolvasott rajtszámú versenyzőt. Ha (megtaláltuk a versenyzőt) akkor új időeredmény hozzáadása a versenyzőhöz. egyébként Hiba történt. Fájl bezárása egyébként Hiba a történt.
16. A konkrét feladat megoldása függvényként Az adatszerkezetek fájlból való felépítése, valamint az ehhez szükséges függvények megírása után már csak a konkrét feladat megválaszolása maradt hátra.
„Ki volt az a versenyző, aki a 23. körben futotta a leggyorsabb körét?” A kérdés megválaszolásához végig kell gondolni, hogy egyértelmű-e a kérdésre adható válasz, vagy pedig több lehetséges megoldás is szóba jöhet. A fenti kérdésre nem egyértelmű a válasz, mivel több versenyző is lehet, aki éppen a 23. körben tette meg a leggyorsabb saját körét. Ilyen esetben vagy kiírjuk az összes megoldást, vagy pedig egyértelműsítjük a kérdést, hogy biztosan csak egy helyes megoldás legyen.
„Ki volt a leggyorsabb versenyző, aki a 23. körben futotta a leggyorsabb körét?”
A végeredmény (egyszerűsítve, hibakezelések nélkül)
int main(void) { Verseny* verseny = verseny_beolvas("Verseny.txt"); Versenyzo* akt = verseny->versenyzok->kov; Versenyzo* keresett = NULL; idoeredmenyek_beolvas("Ido.dat", verseny->versenyzok); ossz_ido_szamitasa(verseny->versenyzok); leggyorsabb_kor_szamitasa(verseny->versenyzok); rendezes_ido_szerint(verseny->versenyzok); while(akt->kov && keresett==NULL) { if(akt->leggyorsabb_kor == 23) keresett = akt; akt = akt->kov; } if(keresett!=NULL) kiir_versenyzo(keresett); else printf("Nincs ilyen versenyzo!\n"); return 0; }
