Készítette: Nagy Tibor István Felhasznált irodalom: Kotsis Domokos: OOP diasor Zsakó L., Szlávi P.: Mikrológia 19

Készítette: Nagy Tibor István Felhasznált irodalom: Kotsis Domokos: OOP diasor Zsakó L., Szlávi P.: Mikrológia 19.

Programkészítés  Megrendelői igények begyűjtése  Megoldás megtervezése (algoritmuskészítés)

 Megoldás megvalósítása (implementálás)  Tesztelés

Algoritmus  Algoritmus kritériumai:  Elemi lépésekre kell bontani (elemi lépés = az algoritmus végrehajtója számára egyértelmű, végrehajtható utasítás)  Az összes lehetséges esetet számba kell venni  Véges sok lépésből kell állnia

Algoritmusleíró eszközök  Mondatokkal történő leírás 

 



Teljes magyar mondatokkal íródik az algoritmus Mondatszerű elemekkel történő leírás (pszeudo-kód) Kulcsszavakkal és az ezekből felépített tőmondatokkal íródik az algoritmus Blokk-diagram Irányított gráf ábrázolja az algoritmust Struktogram A teljes feladat egy téglalap, ennek részekre osztásával íródik az algoritmus …

Algoritmusokban használt strukturált elemek  Másnéven strukturált algoritmikus szerkezetek, vagy

vezérlőszerkezetek:  Szekvencia (utasítássorozat) : tevékenységek

egymásutánja  Szelekció (elágazás) : egy feltétel teljesülése, vagy nem teljesülése esetén más-más tevékenységeket kell elvégezni  Iteráció (ciklus) : egy tevékenységet, vagy tevékenységsorozatot többször meg kell ismételni

 A vezérlőszerkezetek egymásba is ágyazhatók

Blokk-diagram Szekvencia (utasítássorozat) utasítás1

utasítás2

utasítás3

Blokk-diagram Szelekció (elágazás) i

utasítás1

feltétel

n

utasítás2

Blokk-diagram Iteráció (elöltesztelős ciklus) Nincs külön jelölés a ciklusra. Elágazással lehet megvalósítani.

i

utasítás(ok)

feltétel

n

Blokk-diagram Iteráció (hátultesztelős ciklus) Nincs külön jelölés a ciklusra. Elágazással lehet megvalósítani.

utasítás(ok)

i

feltétel

n

Példa – Rablóbanda Feladat: Egy rablóbanda az erdőben les gazdag áldozataira. A gazdasági fellendülés következtében megnőtt az erdei úton közlekedő, kincsekkel megrakott konvojok száma, ezért szükségessé vált a bandát új taggal bővíteni. Az új tagnak el kell magyarázni a rablás folyamatát.

A rablás algoritmusa I. Bunkót kézbe Leshelyre ki

Lesés

i

Kirablás

Kocsma Haza

Jön karaván?

n

És ha nem volt a karavánnál pénz?

A rablás algoritmusa II. Bunkót kézbe Leshelyre ki

Lesés i

Jön karaván?

n

Kirablás

n

Elég a pénz?

i Kocsma Haza

És ha nem is jött karaván?

A rablás algoritmusa III. Bunkót kézbe Leshelyre ki

n

i

Este van? Lesés

i

Jön karaván?

n

Kirablás n

Elég a pénz?

i Kocsma

Haza

Ez már jó, de kusza

Struktogram Szekvencia (utasítássorozat) utasítás1 utasítás2 utasítás3

vagy

utasítás1 utasítás2 utasítás3

Struktogram Szelekció (elágazás) feltétel

i utasítás2

n utasítás3

vagy

feltétel

i utasítás2

n

Struktogram Iteráció (ciklus) feltétel

utasítás(ok)

vagy

utasítás(ok)

feltétel

A rablás algoritmusa Bunkót kézbe Leshelyre ki Amíg nincs este és nem elég a pénz Lesés Jön karaván?

i

n

Kirablás Elég a pénz?

i Kocsma

Haza

n

Pszeudo-kód Szekvencia (utasítássorozat)  Formátum:

utasítás1 utasítás2 … utasításN  Az utasítások végrehajtása leírásuk sorrendjében történik

Pszeudo-kód Szelekció (elágazás)  Formátum:

   

Ha feltétel akkor utasítás(ok)1 különben utasítás(ok)2 Elágazás vége Ha a feltétel igaz, akkor utasítás(ok)1, különben utasítás(ok)2 hajtódik végre A feltétel logikai igaz, vagy hamis értékű lehet utasítás(ok)1 az elágazás igaz-ága, utasítás(ok)2 az elágazás hamis-ága. A hamis-ág elhagyható

Pszeudo-kód Szelekció (többirányú elágazás)  Formátum:

Elágazás feltétel1 esetén utasítás(ok)1 feltétel2 esetén utasítás(ok)2 … különben utasítás(ok)N Elágazás vége  Ha feltétel1 igaz, akkor utasítás(ok)1, ha feltétel2 igaz, akkor utasítás(ok)2, ha egyik feltétel sem igaz, utasítás(ok)N hajtódik végre  Minden feltétel logikai igaz, vagy hamis értékű lehet  A különben-ág elhagyható

Pszeudo-kód Iteráció (elöltesztelős ciklus)  Formátum:

Ciklus amíg feltétel Ciklusmag Ciklus vége  A ciklusmag utasításai addig ismétlődnek, amíg a feltétel igaz

Pszeudo-kód Iteráció (hátultesztelős ciklus)  Formátum:

Ciklus Ciklusmag amíg feltétel Ciklus vége  A ciklusmag utasításai addig ismétlődnek, amíg a feltétel igaz  A ciklusmag egyszer mindenképp végrehajtódik a feltétel-től függetlenül

Pszeudo-kód Iteráció (számlálós ciklus)  Formátum:

Ciklus változó = kezdőérték-től végérték-ig Ciklusmag Ciklus vége  A ciklusmag utasításai kezdőérték-végérték+1-szer ismétlődnek  A változó értéke kezdetben kezdőérték-kel egyenlő, minden cikluslépés végén 1-gyel nő, amíg végértéknél nagyobb nem lesz

A változó  Egy memóriában elhelyezkedő „rekesz”  Egy értéket tárol

 Van azonosítója (vagyis neve)  Van típusa (milyen értéket tárolhat)  Az értéke értékadással módosítható  Az értéke egy kifejezésben lekérdezhető

Változókkal végezhető tevékenységek  Értékadás

Érték elhelyezése a változóban  változónév = érték  változónév = kifejezés

 Érték lekérdezése

A változó tartalmának kiolvasása. Az érték a kiolvasás után is megmarad a változóban. Pl.:  Ha változónév > 10 akkor …  változó2 = 3 * változónév + 12

Feladat – másodfokú egyenlet megoldása ax2 + bx + c = 0 a0 ax2 + bx + c = 0

a=0 bx + c = 0

𝑏2 − 4𝑎𝑐 = 0 b=0 c=0

𝒙𝟏,𝟐

b0

𝑏2 − 4𝑎𝑐 > 0

𝒄 𝐱=− 𝒃 𝒙𝟏,𝟐

c=0 c0 Azonosság Ellentmondás 𝒙𝟏,𝟐

−𝒃 ± 𝒃𝟐 − 𝟒𝒂𝒄 = 𝟐𝒂

𝑏2 − 4𝑎𝑐 < 0 𝒃 =− ± 𝟐𝒂

𝒃𝟐 − 𝟒𝒂𝒄 𝒋 𝟐𝒂

𝒃 =− 𝟐𝒂

Feladat – másodfokú egyenlet megoldása a=0

i b=0

i i

c=0

Azon.

𝑏2 − 4𝑎𝑐 = 𝟎

n i n

Ellentm.

n

𝒄 𝒃 i 𝐱=− 𝒙𝟏,𝟐 = − 𝟐𝒂 𝒃 𝒙𝟏,𝟐

𝑏2 − 4𝑎𝑐 > 𝟎 −𝒃 ± 𝒃𝟐 − 𝟒𝒂𝒄 𝒃 = 𝒙𝟏,𝟐 = − ± 𝟐𝒂 𝟐𝒂

n

n 𝒃𝟐 − 𝟒𝒂𝒄 𝒋 𝟐𝒂

Algoritmusok specifikációja  Négy részből áll:  Bemenet: az algoritmusnak milyen bemenő adat(ok)ra van szüksége  Kimenet: az algoritmus milyen eredmény(eke)t állít elő  Előfeltétel: a bemenő adatok milyen feltételeknek kell, hogy eleget tegyenek ahhoz, hogy az algoritmus helyesen tudjon működni  Utófeltétel: Milyen feltételeknek tesz eleget a kimenet az algoritmus végrehajtása után, vagy másképpen: hogyan állítja elő az algoritmus a bemenő adatokból a kimenetet

Feladat – másodfokú egyenlet megoldása specifikációval Bemenet: a, b, c ∈ ℝ Kimenet: 𝑥1 , 𝑥2 ∈ ℂ Előfeltétel: Utófeltétel:

a=0

i

b=0

i i

c=0

Azon.

𝒃𝟐 − 𝟒𝒂𝒄 = 𝟎

n i n

Ellentm.

n

𝒄 𝒃 i 𝐱=− 𝒙 =− 𝟐𝒂 𝒃 𝟏,𝟐 𝒙𝟏,𝟐

𝒃𝟐 − 𝟒𝒂𝒄 > 𝟎 −𝒃 ± 𝒃𝟐 − 𝟒𝒂𝒄 𝒃 = 𝒙𝟏,𝟐 = − ± 𝟐𝒂 𝟐𝒂

n n 𝒃𝟐 − 𝟒𝒂𝒄 𝒋 𝟐𝒂

Feladatok 1.  Adott a, b, c oldalhossz. Állapítsuk meg, hogy a

  



három oldal milyen háromszöget alkot. Adott a, b, c oldalhossz. Adjuk meg a háromszög kerületét és területét. Adott x és y. Adjuk meg x * y értékét az + művelet felhasználásával. Adott a és x. Adjuk meg ax értékét, a * művelet felhasználásával Adott a és x. Adjuk meg ax értékét, az + művelet felhasználásával

Feladatok 2.  Adott x és y. Határozzuk meg a két szám legkisebb

közös többszörösét.  Adott x és y. Határozzuk meg a két szám legnagyobb közös osztóját.  Adott x. Mondjuk meg, hogy x prímszám-e.

Feladatok 3.  Egy meteorológiai állomáson mérik a napi

középhőmérséklet-értékeket egy hónapon keresztül. Írjuk ki azoknak a napoknak a sorszámát, amikor:  a hőmérséklet fagypont alatt volt  a leghidegebb volt

 a legmelegebb volt

Feladatok 4.  Egy toronyugró versenyen N versenyző indul.

Minden versenyzőnek egy ugrásra van lehetősége. Az ugrásokat 7 bíró pontozza. Egy ugrás összpontszáma a pontok összegéből számítódik, amelyben a legkisebb és a legnagyobb pont nincs benne. Az a versenyző győz, aki a legtöbb pontot kapta az ugrására. Adjuk meg ennek a versenyzőnek a nevét! (Tételezzük fel, hogy van egy utasítás, amellyel a versenyző nevét és a bírói pontokat tudjuk bekérni)

A tömb  Több, memóriában

   

elhelyezkedő „rekesz” együttese Több, azonos típusú értéket tárol Elemei a tömbön belüli sorszámukkal (index) érhetők el Egy elem értéke értékadással módosítható Egy elem értéke egy kifejezésben lekérdezhető

Tömbbel végezhető tevékenységek  Értékadás

Érték elhelyezése egy tömbelemben  Érték lekérdezése Egy tömbelem tartalmának kiolvasása. Az érték a kiolvasás után is megmarad a tömbelemben

Tömbelem elérése (indexelés)  A tömb egy adott eleméhez a tömb neve után

szögletes zárójelek között megadott sorszámmal (index) férhetünk hozzá: tömbnév[index]  A tömb első elemének indexe: 0  A tömb utolsó elemének indexe: elemszám – 1

tomb

0.

1.

2.

3.

4.

28

3

17

11

50

tomb[3]

Feladatok  Egy meteorológiai állomáson mérik a napi

középhőmérséklet-értékeket egy hónapon keresztül.  Tároljuk el ezeket az értékeket egy tömbben 

valósítsuk meg a feladatot mindhárom ciklusfajtával

 Határozzuk meg a havi átlaghőmérsékletet  Írjuk ki azoknak a napoknak a hőmérsékletét, amikor

hidegebb volt a havi átlagnál  Írjuk ki azoknak a napoknak a hőmérsékletét, amikor fagyott  Írjuk ki azoknak a napoknak a számát, amikor fagyott

Programozási tételek  Egy adott feladatosztályba tartozó összes feladatra

megoldást adó algoritmus.  pl.: a keresés tétel bármilyen elemsorozatban bármilyen feltételnek megfelelő elemek keresésére használható

Programozási tételek – alkalmazott jelölések  ℍ : valamilyen (azonos) típusú elemek halmaza.

Például ℍ lehet a természetes számok halmaza, vagy a karakterek halmaza, …  ℍ𝑁 : ℍ összes lehetséges N elemű részsorozata Például: ℕ3 = * 0,1,2 , 1,0,2 , 1,2,0 , 1,1,1 , … +

Programozási tételek – alkalmazott jelölések  𝑇: ℍ ⟶ 𝕃

𝑖𝑔𝑎𝑧, 𝑕𝑎 𝒂 𝑚𝑒𝑔𝑓𝑒𝑙𝑒𝑙 𝑎 𝑡𝑢𝑙𝑎𝑗𝑑𝑜𝑛𝑠á𝑔𝑛𝑎𝑘 𝑇 𝑎 = 𝑕𝑎𝑚𝑖𝑠, 𝑒𝑔𝑦é𝑏𝑘é𝑛𝑡  Például: 𝑖𝑔𝑎𝑧, 𝑕𝑎 𝒂 < 0 𝑇 𝑎 = 𝑕𝑎𝑚𝑖𝑠, 𝑒𝑔𝑦é𝑏𝑘é𝑛𝑡 vagy 𝑖𝑔𝑎𝑧, 𝑕𝑎 𝒂 𝑝á𝑟𝑜𝑠 𝑇 𝑎 = 𝑕𝑎𝑚𝑖𝑠, 𝑒𝑔𝑦é𝑏𝑘é𝑛𝑡 …

Eldöntés tétele  Adott egy N elemű sorozat és egy – a sorozaton

értelmezett – T tulajdonság. Mondjuk meg, hogy a sorozatban van-e T tulajdonságú elem. Bemenet: N ∈ ℕ, 𝐴 ∈ ℍ𝑁 Kimenet: 𝑉𝐴𝑁 ∈ 𝕃 Előfeltétel:Utófeltétel: 𝑉𝐴𝑁 ≡ (∃𝑖 0 ≤ 𝑖 < 𝑁 : 𝑇 𝐴𝑖 ) Algoritmus Eldöntés: i = 0; Ciklus amíg i
Kiválasztás tétele  Adott egy N elemű sorozat és egy – a sorozaton

értelmezett – T tulajdonság. Biztosan tudjuk, hogy a sorozatban van T tulajdonságú elem. Mondjuk meg az első ilyen elem sorszámát. Bemenet: N ∈ ℕ, 𝐴 ∈ ℍ𝑁 Kimenet: 𝑆𝑂𝑅𝑆𝑍 ∈ ℕ Előfeltétel: ∃𝑖 0 ≤ 𝑖 < 𝑁 : 𝑇(𝐴𝑖 ) Utófeltétel: 0 ≤ 𝑆𝑂𝑅𝑆𝑍 < 𝑁 é𝑠 𝑇(𝐴𝑆𝑂𝑅𝑆𝑍 ) Algoritmus Kiválasztás: i = 0; Ciklus amíg T(A[i]) i=i+1 Ciklus vége SORSZ = i Algoritmus vége

Lineáris keresés tétele  Adott egy N elemű sorozat és egy – a sorozaton

értelmezett – T tulajdonság. Mondjuk meg, hogy van-e T tulajdonságú elem a sorozatban, és adjuk meg az első ilyen elem sorszámát. Bemenet: N ∈ ℕ, 𝐴 ∈ ℍ𝑁 Kimenet: VAN ∈ 𝕃, 𝑆𝑂𝑅𝑆𝑍 ∈ ℕ Előfeltétel: Utófeltétel: 𝑉𝐴𝑁 ≡ ∃𝑖 0 ≤ 𝑖 < 𝑁 : 𝑇 𝐴𝑖 é𝑠 𝑉𝐴𝑁 ⇒ (0 ≤ 𝑆𝑂𝑅𝑆𝑍 < 𝑁 é𝑠 𝑇 𝐴𝑆𝑂𝑅𝑆𝑍 ) Algoritmus Keresés: i = 0; Ciklus amíg i
Megszámlálás tétele  Adott egy N elemű sorozat és egy – a sorozaton

értelmezett – T tulajdonság. Mondjuk meg, hogy hány T tulajdonságú elem van a sorozatban. Bemenet: N ∈ ℕ, 𝐴 ∈

ℍ𝑁 , 𝑈

1, 𝑕𝑎 𝑇(𝑥) 𝑥 = 0, 𝑒𝑔𝑦é𝑏𝑘é𝑛𝑡

Kimenet: DB ∈ ℕ Előfeltétel: Utófeltétel: 𝐷𝐵 = 𝑁 𝑖=1 𝑈(𝐴𝑖 ) Algoritmus Megszámlálás: DB = 0 Ciklus i = 0-től N-1-ig Ha T(A[i]) akkor DB = DB + 1 Ciklus vége Algoritmus vége

Maximumkiválasztás tétele  Adott egy N elemű sorozat. Mondjuk meg a sorozat

legkisebb elemének sorszámát.

Bemenet: N ∈ ℕ, 𝐴 ∈ ℍ𝑁 Kimenet: maxindex ∈ ℕ Előfeltétel: 𝕏 teljesen rendezett és N>0 Utófeltétel: 0 ≤ 𝑚𝑎𝑥𝑖𝑛𝑑𝑒𝑥 < 𝑁 é𝑠 ∀𝑖 0 ≤ 𝑖 < 𝑁 : 𝐴𝑚𝑎𝑥𝑖𝑛𝑑𝑒𝑥 ≥ 𝐴𝑖 Algoritmus Maximumkiválasztás: maxindex = 0 Ciklus i = 1-től N-1-ig Ha A[i] > A[maxindex] akkor maxindex = i Ciklus vége Algoritmus vége

Programkészítés lépései  Megrendelői igények begyűjtése  Megoldás megtervezése (algoritmuskészítés)

 Megoldás megvalósítása (implementálás)  Tesztelés

Implementálás (parancssorból) 1. Algoritmus  C# Forráskód 1. Forráskód megírása szövegszerkesztőben 2. Forráskód elmentése fájlnév.cs néven 2. C# forráskód  Futtatható fájl (.exe) 1. Parancssori ablak megnyitása 2. Belépés a forráskódot tartalmazó könyvtárba (cd) 3. Forrásfájl lefordítása (csc fájlnév.cs) 3. Futtatható fájl végrehajtása 1. Parancssori ablak megnyitása 2. Program futtatása (fájlnév.exe)

Üres C# program class ProgramNév { static void Main() { } }

C# utasítások – szekvencia  Minden utasítást ; zár le  Az utasítások írhatók külön sorokba:

utasítás1; utasítás2; … utasításN;  Az utasítások írhatók egy sorba: utasítás1; utasítás2; … utasításN;

C# utasítások – szelekció if ( feltétel ) utasítás1; [else utasítás2;]

if ( feltétel ) { utasítás1; utasítás2; … } else { utasítás3; utasítás4; … }

 else ág elhagyható

 Több utasítás esetén kötelező a { }

C# utasítások – szelekció if ( feltétel1 ) utasítás1; [else if ( feltétel2 ) utasítás2; [else if ( feltétel3 ) utasítás2; … ] [else utasításN; ]

 else ág elhagyható

 Több utasítás esetén kötelező a { }  else if ágakból tetszőleges számú használható

C# utasítások – szelekció switch( kifejezés ) { case érték1 : utasítás(ok)1; break; case érték2 : utasítás(ok)2; break; … [default: utasítás(ok)N; break;] }

 Ha a kifejezés értéke  = érték1, akkor utasítás(ok)1,  = érték2, akkor utasítás(ok)2, … hajtódik végre  Ha kifejezés értéke egyik case-ben megadottal

sem egyenlő, akkor utasítás(ok)N hajtódik végre

C# utasítások – iteráció while ( feltétel ) utasítás;

while ( feltétel ) { utasítások; }

 Amíg a feltétel igaz, utasítások újra és újra

végrehajtódik  Ha a ciklusmagban több utasítás van, kötelező a { }

C# utasítások – iteráció do { utasítás(ok); } while ( feltétel );

 Amíg a feltétel igaz, utasítás(ok) újra és újra

végrehajtódik  Mindig kötelező a { }

C# utasítások – iteráció for ( inicializáló_rész; feltétel; módosító_rész ) { utasítások; }  Amíg a feltétel igaz, utasítások újra és újra   



végrehajtódik Több utasítás esetén kötelező a { } inicializáló_rész: ciklusváltozó(k) inicializálása módosító_rész: ciklusváltozó(k) értékének módosítása A zárójelek közti három rész közül egyiket sem kötelező megadni (végtelen ciklus)

C# utasítások – iteráció foreach (típus ciklusváltozó in gyűjtemény) { utasítások; }  A gyűjtemény (pl. tömb) összes elemén végiglépked  Több utasítás esetén kötelező a { }

 A ciklusváltozó minden cikluslépésben a

gyűjtemény aktuális elemének értékét tartalmazza  ciklusváltozó a ciklusban nem változtatható meg  gyűjteményből elemet törölni, vagy új elemet felvenni a cikluson belül nem lehet!