Programozási alapismeretek Tananyag: Problémamegoldási stratégiák, az informatikai problémamegoldás alapjai. A problémák megoldásához szükséges informatikai eszközök és módszerek. Programkészítési elvek. Algoritmikus struktúrák és adattípusok. Konstans, változó, típus fogalma. Elemi algoritmusok típusfeladatokra. Összegzés, eldöntés, keresés, számlálás, maximum-kiválasztás, kiválogatás, rendezések. A C++ programozási nyelv alapvető elemei. A Code::Blocks programfejlesztői környezet, szerkesztés, fordítás, futtatás. A programkészítés, mint termék előállítási folyamat. Alapvető tesztelési, hibakeresési módszerek. Vizsgajegyek: 1) csoport ZH: algoritmizálás (specifikáció, algoritmus) 2) csoport ZH: kódolás (specifikáció, algoritmus, kód, számítógép mellett) 3) évfolyam ZH: komplex feladat megoldása számítógép mellett 4) beadandó feladat 5) gyakorlati röpdolgozatok ≥10 darab
Bevezető A programkészítés folyamata: 1. Specifikálás (miből? mit?) specifikáció 2. Tervezés (mivel? hogyan?) adat + algoritmusleírás 3. Kódolás (a gép hogyan?) kód (reprezentáció + implementáció) 4. Tesztelés (hibás-e?) hibalista (diagnózis) 5. Hibakeresés (hol a hiba?) hibahely, ok 6. Hibajavítás (hogyan jó?) helyes program 7. Minőségvizsgálat, hatékonyság (jobbítható-e? hogyan?) jó program 8. Dokumentálás (hogyan működik? használható?) használható program 9. Használat, karbantartás (még mindig jó?) évelő (időálló) program A specifikáció fogalma: Célja: a feladat formális megoldása Összetevői: 1. Bemenő adatok (azonosító, értékhalmaz [mértékegység]) 2. Ismeretek a bemenetről (előfeltétel) 3. Eredmények (azonosító, értékhalmaz) 4. Az eredményt meghatározó állítás (utófeltétel) 5. A használt fogalmak definíció 6. A megoldással szembeni követelmények 7. Korlátozó tényezők Tulajdonságai: 1. „Egyértelmű”, pontos, teljes 2. Rövid, tömör; formalizált 3. Szemléletes , érthető (fogalmak) Specifikációs eszközök: 1. Szöveges leírás 2. Matematikai megadás Az algoritmus fogalma: Fogalma:Lépések sorozata, amellyel egy feladat kiindulásától a megoldásig jutunk. Összeállítási módjai: Szekvencia (egymás utáni végrehajtás) Elágazás (választás kettő vagy több tevékenységből) Ciklus (ismétlés adott darabszámszor vagy adott feltételtől függően) Alprogram (egy összetett tevékenység, egyedi néven – absztrakció)
Példa: a 3 szám lehet-e egy derékszögű háromszög 3 oldala? Specifikáció: Bemenet: x,y,z R (valós számok halmaza) Kimenet: lehet L (logikai értékek halmaza) Előfeltétel: x>0 és y>0 és z>0 Utófeltétel: lehet=(x2+y2=z2) Itt rögzítettük az átfogót a z-re lehet=((x2+y2=z2) vagy (x2+z2=y2) vagy (y2+z2=x2)) Itt nincs rögzítve semmi Algoritmus: A programunk 4 fő részből áll: az adatok deklarálása az adatok beolvasása az eredmény kiszámítása az eredmény kiírása Be: x,y,z [x>0 és y>0 és z>0] lehet:=(x2+y2=z2) Ki: lehet A deklarációt, az „elemi” utasításokat egy-egy „dobozba” írjuk. Később a be- és kimenetet nem algoritmizáljuk! Példa: Addjuk meg a másodfokú egyenlet egy megoldását! Az egyenlet: ax 2+bx+c=0 Kérdések: Mitől függ a megoldás? – bemenet Mi a megoldás? – kimenet Mit jelent: „megoldásnak lenni”? – utófeltétel Mindig/Mikor van megoldás? – előfeltétel Biztos egy megoldás van? – kimenet/utófeltétel Specifikáció: Bemenet: a,b,c R Kimenet: x R, van L Előfeltétel: a≠0 Utófeltétel1: ax2+bx+c=0 √
Utófeltétel2:
Utófeltétel3: van=(b2–4ac≥0) és √
van Algoritmus: Program MasodfokuEgyenlet: Változó a,b,c,x:Valós van:Logikai d:Valós Be: a,b,c [a≠0] d:=b2–4ac van:=d≥0 Ha van akkor … Program Vége.
√
Algoritmusleíró nyelvek: Szöveges leírás Mondatokkal leírás Mondatszerű elemekkel – pszeudokód Rajzos leírás Folyamatábra Struktogram
Struktogram Szekvencia: Utasítás1 Utasítás2 Utasítás3 Elágazás: Feltétel I
H Igaz-ág utasításai
Hamis-ág utasításai
Feltétel1
Feltétel2
Utasítások1
Utasítások2
… …
egyébként UtasításokN
Ciklusok: Bennmaradás feltétele ciklusmag utasításai ciklusmag utasításai Bennmaradás feltétele cv=tól…ig ciklusmag utasításai
Fejlesztői környezet (Kódolás) Keretrendszer (IDE): Code::Blocks (Letöltés: www.codeblocks.org, verzió 13.12) Struktogram szerkesztő program: structorizer (Letöltés: http://structorizer.fisch.lu) Alacsony szintű programozási nyelv: Assembly Magas szintű programozási nyelvek: C, C#, C++, Java, Pascal, VB, PHP Script programozási nyelvek: JS, Python, PHP, SH, PS Egyéb programozási nyelvek: SQL, Logo Gyakorlat oktató: Név: Menyhárt László Órakezdés: kedd 08:15 – 09:45 Email:
[email protected] (Üzenet küldési forma: [ProgAlap5] – 09.17-ei házi) Weboldal: http://progalap.elte.hu Projekt létrehozása: projekt létrehozása (Windows-ra) sablon kiválasztása (Console application) projektnév megadása projekt szülőkönyvtár megadása fordítóválasztás projekt létrehozásának befejezése a kód beírása Build > Build: fordítás Build > Run: a fordított program futtatása
Code::Blocks programfejlesztés fájlfelépítése:
Adatokkal kapcsolatos fogalmak
Konstans az az adat, amely a műveletvégzés során nem változtathatja meg értékét, mindvégig ugyanabban az „állapotban” marad. Változó az ilyen adatféleségnek lényegéhez tartozik a „változékonyság”, más szóval: vonatkozhatnak rá olyan műveletek is, amelyek új értékkel látják el. Tudományosabban fogalmazva: nem egyelemű az állapothalmaza. Értékadás az az utasítás, amely révén a pillanatnyi állapotból egy új (a meghatározottba) állapotba kerül át a változó. (Nyilvánvaló, hogy konstans adatra nem vonatkozhat értékadás, a kezdőértéket meghatározón kívül.) Típus olyan „megállapodás” (absztrakt kategória), amely adatok egy lehetséges körét jelöli ki az által, hogy rögzíti azok állapothalmazát és az elvégezhető műveletek készletét. Azonosító Az a jelsorozat, amellyel hivatkozhatunk a tartalmára, amely által módosíthatjuk tartalmát. Kezdőérték A születéskor hozzárendelt érték. Konstansoknál nyilvánvaló, hogy deklarációban kapja; változóknál akár deklarációban, akár futáskor szerez értéket magának.
A típus Összetettség(strukturáltság) szempontjából beszélhetünk strukturálatlan (vagy skalár, elemi) típusról, ha (az adott szinten) szerkezetet nem tulajdonítunk neki; vagy strukturált (más szóval: összetett) típusról, ha (elemibb) összetevőkre bontjuk. Elemi típusok egész típus Értékhalmaz: – 231…+ 231 – 1 (Min’Egész…Max’Egész, ez 4 byte) Műveletek: +,–, ⃰ , /, Div (egészosztás), Mod (osztási maradék), – (unáris mínusz), ^ (pozitív egészkitevős hatványozás) Relációk: =, <, ≤, ≠, ≥, > Ábrázolás: kettes komplemens kódú Változatai: méret és előjel szerint sokféle valós típus Értékhalmaz: ???...??? (Min’Valós…Max’Valós nem definiáltak, vagy implementációfüggőek) Műveletek: +, –, ⃰ , /, ^, – (unáris mínusz) Relációk: =, <, ≤, ≠, ≥, > Ábrázolás: lebegőpontos ábrázolás (pontosabb lenne, ha e típus racionálisnak neveznénk, mert csak racionális számot képes ábrázolni) logikai típus Értékhalmaz: Hamis…Igaz (Min’Logikai…Max’Logikai: Hamis, illetve Igaz) Műveletek: nem, és, vagy (a szokásos logikai műveletek) Relációk: =, <, ≤, ≠, ≥, > (általában = és ≠ használjuk) Ábrázolás: 0B = Hamis, –1B = Igaz (esetleg: 1B = Igaz) … ahol xB = x érték „bináris egészként” ábrázolva
karakter típus Értékhalmaz: 0…255 – kódú jelek – ASCII (Min’Karakter…Max’Karakter: a 0, illetve a 255 kódú karakter) Műveletek: karakter-specifikus nincs (esetleg a Kód:Karakter Egész függvény, és inverze a Kód:Egész Karakter függvény, amelyek a belső ábrázolással hozza kapcsolatba) Relációk: =, <, ≤, ≠, ≥, >(a belső ábrázolásuk alapján nem ABC-sorrend!)
Adminisztráció Célszerűen a programok forrása tartalmazzák: 1. a szerző adatait, 2. a feladat szövegét és 3. a feladat specifikációját; valamint 4. használható algoritmusmagyarázatokat; 5. a fejlesztés – esetleg – még hátralévő teendőit. Kis szívesség a Code::Blocks-tól: A szerző adatai (1.) a sablonba (a template-be) fixen beépíthetők.
C++ alapok Programszerkezet – main függvény intmain() { lokális adatdeklarációk … a függvénytörzs végrehajtható utasításai … returnfvÉrték; } Alaptípusok int – egész long – egész float – valós double – valós char – karakter string – szöveg bool – logikai
Első program #include
//kiírás és beolvasás függvény ebben található #include //ez az exithez kell //könyvtárfájlokat (header-fájlok) az #include és #include "saját" tudjuk a programba építeni using namespacestd;//így adhatom meg a névteret (csomagot); beolvasás és kiírás szempontjából a nyelvek kétfélék lehetnek: //a nyelv eleve tartalmaz ilyen parancsokat; a nyelv eljáráskönyvtára tartalmaz beolvasó és kiíró függvényeket intmain() { stringnev;//a string egy tetszőleges hosszúságú karaktersorozat constunsigned shortjokor = 18;//konstans deklarálása unsigned shortkor;//ez egy egész típus deklarálása cout<<"Udvozollek!"<< endl;//így írok ki egy sort a konzol képernyőre cout<<"Hogy hivnak? : "; cin>>nev;//beolvasás cout<<"Szia "<>kor; if (kor<jokor) {//ez egy reláció (logikai kifejezés), továbbiak: ==, !=, <=, >=, > cout<<"Tul fiatal vagy!"<< endl; exit(1); //ezzel kilépek a programból (hibaértékkel) } else { cout<<"OK"<< endl; } return0;//ha végigfut a program és elér a főfüggvény végéig,akkor hiba nélkül kilép }
Hibakeresés, hibajavítás Hibák fajtái: Fordítás során kiírt hibák javítása o Hibaüzenet értelmezése o A hiba okának kiderítése o A hiba keletkezési helyének keresése o A hiba kijavítása Futtatás során fellépő hibák javítása o Tesztelés o A hiba keletkezési helyének keresése o A hiba kijavítása
A kétirányú elágazás használata Feladat: Egy ember vércsoportját (Rh negatív vagy pozitív) egy génpár határozza meg. Mindkét gén lehet "+" vagy "-" típusú. A "++" és a "+-" típusúak az "Rh pozitívok", a "--" típusúak pedig "Rh negatívok". Írjunk programot, amely megadja egy ember vércsoportját a génpárja ismeretében!" Specifikáció: Bemenet: x, y K (K - karakterek halmaza) Kimenet: v S (S - karakter-sorozatok halmaza) Előfeltétel: x, y {"+","–"} Utófeltétel: (x="+" vagy y="+") akkorv="Rh+" és (x="–" és y="–") akkorv="Rh–" Algoritmus: x="+" vagy y="+"
I
v:= "Rh+"
H
v:= "Rh–"
Kétirányú elágazások egymásba ágyazása Feladat: Egy ember vércsoportját (A, B, AB vagy 0) egy génpár határozza meg. Mindkét gén lehet a, b vagy 0 típusú. A vércsoport meghatározása: A={aa,a0,0a}; B={bb,b0,0b}; AB={ab,ba}; 0={00}. Írjunk programot, amely megadja egy ember vércsoportját a génpárja ismeretében! Specifikáció: Bemenet: x, y K (K - karakterek halmaza) Kimenet: v S (S - karakter-sorozatok halmaza) Előfeltétel: x, y {"a","b","0"} Utófeltétel: (x="a" és y≠"b" vagy x≠"b" és y="a") akkor v="A" vagy (x="b" és y≠"a" vagy x≠"a" és y="b") akkor v="B" vagy (x="a" és y="b" vagy x="b" és y="a") akkor v="AB" vagy (x="0" és y="0") akkor v="0" Algoritmus: kétirányú elágazások egymásba ágyazásával x="a" és y≠"b" vagy x≠"b" és y="a"
I I v:="A"
H
x="b" és y≠"a" vagy x≠"a" és y="b" v:="B"
Algoritmus: sokirányú elágazással x="a" és y≠"b" vagy x≠"b" és y="a" v:="A"
I
H
x="a" és y="b" vagy x="b" és y="a" v:="AB" x="b" és y≠"a" vagy x≠"a" és y="b" v:="B"
H
v:="0" x="a" és y="b" vagy x="b" és y="a" v:="AB"
x="0" és y="0" v:="0"
Algoritmus: segédváltozók bevezetésével (lokális változók deklarálása) vana:= x="a" vagy y="a" vanb:= x="b" vagy y="b" vana
I vanb
I
H
v:="AB"
v:="A"
H vanb
I v:="B"
Elágazások használata (C++) kétirányú: if (Feltétel) { UtasításI } else { UtasításH } sokirányú (egymásba ágyazott kétirányúk): if (Feltétel1) { Utasítás1 } elseif (Feltétel2) { Utasítás2 } elseif (…) { … } elseif (FeltételN) { UtasításN } else { Utasítás } sokirányú (speciális): switch (kifejezés) { case érték1: Utasítás1; break; … case értékN: UtasításN; break; default: Utasítás; break; }
Vércsoport (A,B,AB,0) feladat kódolása
H v:="0"
A konzol input kódolása az előfeltétel alapján Előfeltétel: Helyes(x) ahol a Helyes(x) egy x-től függő logikai kifejezést rövidít most
Ugyanez egyszerűbben:
Szintaktikus és szemantikus ellenőrzés Értelemszerűen csak bizonyos típusú változóba történő olvasásnál alkalmazható (pl. valamely szám típusúba)
Ugyanez egyszerűbben:
Ciklusok használata (for ciklus)
Tömbök használata
Tovább 3. előadás
