1
Információk 2
Elérhetőség
[email protected]
Fogadóóra: szerda 9:50-10:35
Számonkérés
A PROGRAMOZÁS ALAPJAI 2.
Április 25. 900
Május 17. 900
Június 7. 900
írásban
elégségeshez: 50%
Segédanyag
A félév célja
Készítette: Vénné Meskó Katalin
Ismétlés
időpontok
www.ketif.hu oldalon algoritmikus gondolkodás kifejlesztése
Ismétlés II.
3
4
Algoritmus
Pontos előírás, amely megmondja, hogy egy adott típushoz tartozó összes feladat megoldásakor a kezdeti adatokon milyen műveleteket milyen meghatározott sorrendben kell elvégezni. Tulajdonságai meghatározott széleskörű véges megvalósítható
Algoritmus ábrázolása
szerkezeti diagram pszeudo kód
Programozás fázisai
Problémafelvetés (Feladat) Specifikáció Algoritmustervezés …
a további lépések a kódoláshoz kapcsolódnak
Ismétlés III.
Két egész szám viszonya
5
Feladat
Beolvasás (a, b)
Határozzuk meg, hogy hogyan viszonyul egymáshoz két egész szám (kisebb, nagyobb egyenlő)!
a és b vizsgálata
Algoritmustervezés
a
Pszeudo kóddal Egész a Egész b Be: a Be: b Ha a < b akkor Kiír: „a kisebb b-nél” Egyébként Ha a > b akkor Kiír: „a nagyobb b-nél” Egyébként Kiír: „a egyenlő b-vel”
i
n
// változók definiálása //változók bekérése a>b
Kiíratás: „a kisebb b-nél”
//1. feltétel //ha az 1. feltétel teljesül //ha az 1. feltétel nem teljesül //2. feltétel //ha a 2. feltétel teljesül //ha a 2. feltétel nem teljesül
i
Kiíratás: „a nagyobb b-nél” 6
n
Kiíratás: „a egyenlő b-vel”
Ismétlés IV.
Feladat
Algoritmustervezés
Melyik szám nagyobb?
Beolvasás (a, b)
Határozzuk meg, hogy két egész szám közül melyik a nagyobb!
a és b vizsgálata
a>b
Pszeudo kóddal Egész a Egész b Be: a Be: b Ha a > b akkor Kiír: „a nagyobb b-nél” Egyébként Ha b > a akkor Kiír: „b nagyobb a-nál” Egyébként Kiír: „a egyenlő b-vel”
// változók definiálása
i
n
//változók bekérése //1. feltétel //ha az 1. feltétel teljesül //ha az 1. feltétel nem teljesül //2. feltétel //ha a 2. feltétel teljesül //ha a 2. feltétel nem teljesül
7
b>a
Kiíratás: „a nagyobb b-nél” i
Kiíratás: „b nagyobb a-nál”
n
Kiíratás: „a egyenlő b-vel”
8
Ismétlés V.
Feladat
Algoritmustervezés
Melyik szám kisebb?
Beolvasás (a, b)
Határozzuk meg, hogy két egész szám közül melyik a kisebb!
a és b vizsgálata
a
Pszeudo kóddal Egész a Egész b Be: a Be: b Ha a < b akkor Kiír: „a kisebb b-nél” Egyébként Ha b < a akkor Kiír: „b kisebb a-nál” Egyébként Kiír: „a egyenlő b-vel”
// változók definiálása
i
n
//változók bekérése //1. feltétel //ha az 1. feltétel teljesül //ha az 1. feltétel nem teljesül //2. feltétel //ha a 2. feltétel teljesül //ha a 2. feltétel nem teljesül
9
b
Kiíratás: „a kisebb b-nél” i
Kiíratás: „b kisebb a-nál”
n
Kiíratás: „a egyenlő b-vel”
10
Algoritmusok 11
Algoritmusok II. 12
Feladat Számítsuk ki, hogy a nap két időpontja között mennyi idő telt el! Specifikáció Input
két időpont (óra, perc formában) → O1, P1, O2, P2
Bemeneti feltétel
Output
az óra és perc értékek a valóságnak megfeleljenek O és P → az eltelt idő
Algoritmustervezés
Az eltelt idő percben kifejezve
Pszeudo kóddal
(O2 * 60 + P2) – (O1 * 60 + P1) = K, ahol K az eltelt idő percben Egész o1, o2, p1, p2 Egész o, p Egész k Be: o1, p1 Be: o2, p2 Vizsgáld meg, hogy helyesek-e az adatok! k = (o2 * 60 + p2) – (o1 * 60 + p1) o = k / 60 egészrésze p = k / 60 maradéka Ki: „Az eltelt idő: ”, o, „óra és ”, p, „ perc.”
Algoritmusok III.
Eltelt idő 14
Feladat Határozzuk meg, hogy milyen háromszöget határoz meg három egész szám, mint a háromszög három oldalhosszúsága!
Számítás
Beolvasás
Kiíratás
Specifikáció Input
K = a különbség percben
o és p kiszámítása
a, b, c pozitív egész számok
Bemeneti feltétel
adatok átrendezése szükséges, hogy a ≥ b ≥ c teljesüljön.
Átrendezés után Nem háromszög, ha a ≥ b + c Szabályos háromszög, ha a = b és b = c Egyenlőszárú háromszög, ha a = b vagy b = c vagy a = c Derékszögű háromszög, ha a2 = b2 + c2
K = (o2 * 60 + p2) - (o1 * 60 + p1) O = K / 60 egészrésze
P = K / 60 maradéka
Output
13
Algoritmusok IV.
Hogyan lehet átrendezni/cserélni az értékeket?
A háromszög típusa
Algoritmusok V.
15
16
Ha a = b vagy b = c vagy a = c akkor
Algoritmustervezés
Ha a2 = b2 + c2 akkor
Pszeudo kóddal
Ki: „Egyenlőszárú derékszögű háromszög.”
Egész a, b, c Be: a, b, c
Egyébként
Cseréld ki a változók értékét, hogy a ≥ b ≥ c teljesüljön
Ki: „Egyenlőszárú háromszög.” Egyébként
Ha a ≥ b + c akkor
Ha a2 = b2 + c2 akkor
Ki: „Ez nem háromszög.”
Ki: „Derékszögű háromszög.”
Egyébként
Egyébként
Ha a = b és b = c akkor
Ki: „Egyéb háromszög.”
Ki: „Szabályos háromszög.” Egyébként
Háromszög Osztályozás
Beolvasás
a, b, c átrendezése
a és b átrendezése
a és c átrendezése
a
Osztályozás
b
a
i
N
Sz
E
D
Nem háromszög
Szabályos háromszög
Egyenlőszárú háromszög
Derékszögű háromszög
b és c átrendezése
i
n
n D
m=a 17
a=b
b és c cseréje
a és c cseréje
a és b cseréje
b=m
m=a
a=c
c=m
m=b
b=c
i
Egyenlőszárú derékszögű háromszög
c=m 18
n
Egyenlőszárú háromszög
Egyéb
Sorok, sorozatok 19
Sorok, sorozatok II. 20
Dolgok egy listája pl. számok, függvények, betűk, stb. A lista tagjainak sorrendje jól meghatározott Y, C, R nem ugyanaz mint R, Y, C Egy elem többször is előfordulhat Megnevezések
Véges sorozat
Végtelen sorozatok
Sorozat tagjai → elemek Elemek száma → sorozat hosszúsága
Sorok, sorozatok: Számtani sorozat 21
Elemek számától függően A, B, C, D pl. a pozitív páros számokból (2, 4, 6…) képzett sorozat
Részsorozat
az eredeti sorozat néhány elemének elhagyásával kapjuk
az elemek egymáshoz viszonyított sorrendjét nem változtatjuk meg
Sorok, sorozatok: Számtani sorozat II. 22
Aritmetikai sorozat Legalább három számból álló (véges, végtelen) sorozat A szomszédos elemek különbsége állandó
Példák
Feladat
Algoritmustervezés
különbség → differencia (d)
Írjuk ki a számtani sorozat első n db elemét! Pszeudo kóddal Egész a1, d Egész db Egész ai, i Be: a1 Be: d Be: db i vegye fel 1-től db-ig az értékeket és hajtsd végre ai = d * i + (a1 − d) Ki: „A sorozat „, i, „. eleme”, ai
csupa azonos elemből álló konstans sorozat: 1, 1, 1, 1, ... (d = 0) természetes számok sorozata: 0, 1, 2, 3, 4, ... (d = 1) páros számok sorozata: 0, 2, 4, 6, 8, ... (d = 2) 101, 81, 61, 41, 21, 1, -19, ... (d = -20)
A számtani sorozat n. eleme
an = d * n + (a1 − d) vagy an = a1 + (n - 1) * d;
Sorok, sorozatok: Számtani sorozat III. 23
Számtani sorozat
A ciklus másképpen ai = a1 i vegye fel 1-től db-ig az értékeket és hajtsd végre Ki:
Beolvasás
i = 1 → db
„A sorozat „, i, „. eleme”, ai
ai = ai + d; ai = d * i + (a1 − d)
24
Kiíratás
Sorok, sorozatok: Mértani sorozat 25
Sorok, sorozatok: Mértani sorozat II. 26
Legalább három számból álló (véges, végtelen) sorozat A szomszédos elemek (bármelyik tag és az azt megelőző tag) hányadosa állandó
Feladat:
Algoritmustervezés:
hányados → kvóciens (q)
csupa azonos elemből álló konstans sorozat: 2, 2, 2, 2, ... (q = 1) 2, 6, 18, 54, … (q = 3) 90, 30, 10, … (q = 1/3)
A mértani sorozat n. eleme
Írjuk ki a mértani sorozat első n db elemét! Pszeudo kóddal Egész a1, q Egész db Egész ai, i Be: a1 Be: q Be: db i vegye fel 1-től db-ig az értékeket és hajtsd végre ai = a1 * qi-1 Ki: „A sorozat „, i, „. eleme”, ai
Példa:
an = a1 * qn-1
Sorok, sorozatok: Mértani sorozat III. 27
Mértani sorozat
A ciklus másképpen ai = a1 i vegye fel 1-től db-ig az értékeket és hajtsd végre Ki:
Beolvasás
i = 1 → db
„A sorozat „, i, „. eleme”, ai
ai = ai * q;
ai = a1 * qi-1
Kiíratás
28
Sorok, sorozatok: Fibonacci sorozat 29
Sorok, sorozatok: Fibonacci sorozat II. 30
Az első két elem 0 és 1 A további elemeket az előző kettő összegeként kapjuk Fibonacci-sorozat első néhány eleme: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, … A Fibonacci sorozat n. eleme an = a n – 1 + a n – 2 Természetben megfigyelt Fibonacci-számok
Feladat
Algoritmustervezés
Írjuk ki a Fibonacci sorozat első n db elemét! Pszeudo kóddal Egész db Egész a1, a2 Egész ai, i a1 = 0 a2 = 1 Be: db Ki: „A sorozat 1. Ki: „A sorozat 2. i vegye fel 3-tól ai = ai-1 + ai-2 Ki: „A sorozat
eleme „, a1 eleme „, a2 db-ig az értékeket és hajtsd végre „, i, „. eleme”, ai
Sorozatok összegzése 32
Fibonacci sorozat
Beolvasás
Nevezetes sorozatok összegzése – az első n elem összege
Számtani sorozat első n elemének összege ((a1 + an) * n) / 2
Mértani sorozat első n elemének összege (a1 * (qn – 1)) / (q – 1)
i = 3 → db
ai = ai-1 + ai-2
Kiíratás
31
Sorozatok összegzése II.
Számtani sorozat összegzése
33
Feladat
Algoritmustervezés
Határozzuk meg egy számtani sorozat első n db elemének összegét!
Beolvasás
Számítás
Kiíratás
Pszeudo kóddal Egész a1, an Egész db Egész d Egész összeg Be: a1 Be: d Be: db an = d * db + (a1 − d) összeg = ((a1 + an) * db) / 2 Ki: „A mértani sorozat első n elemének összege: „, összeg
an kiszámítása
Összeg kiszámítása
an = d * n + (a1 − d)
összeg = ((a1 + an) * n) / 2
34
Sorozatok összegzése III. Mértani sorozat összegzése
35
Feladat
Algoritmustervezés
Határozzuk meg egy mértani sorozat első n db elemének összegét! Beolvasás
Pszeudo kóddal Egész a1 Egész db Egész q Egész összeg Be: a1 Be: q Be: db összeg = (a1 * (qdb – 1)) / (q – 1) Ki: „A számtani sorozat első n elemének összege: „, összeg
Számítás
Összeg kiszámítása
összeg = (a1 * (qdb – 1)) / (q – 1)
36
Kiíratás
Sorozatok összegzése V.
Sorozatok összegzése IV. 37
38
összeg = összeg + szám
Határozzuk meg egy egész számsorozat legkisebb és legnagyobb elemét, valamint a sorozat átlagát!
db = db + 1 Ha a szám < min akkor
Specifikáció
min = szám
Input
Amíg a szám <> végjel addig hajtsd végre
Feladat
egyébként
számsorozat, melyet egy végjel zár le, amit a felhasználó ad meg a számsorozat előtt
Ha szám > max akkor max = szám
Algoritmustervezés
Be: szám Ha db = 0 akkor
Pszeudo kóddal
Ki: „Üres sorozat.”
Egész szám, végjel Egész min, max, átlag, db, összeg Be: végjel, szám összeg = 0 db = 0 max = szám min = szám
egyébként átlag = összeg / db Ki: „A megadott számsorozat minimuma, maximuma és átlaga: „, min, max, átlag
Min-max-átlag
Prímszámkeresés Erathosztenész szitájával 40
szám <> végjel
Inicializálás
Kiíratás
Ezzel a módszerrel meghatározhatjuk az n-nél nem nagyobb prímszámokat
Szám feldolgozása
Összeg és db feldolgozása
2. lépés
3. lépés
n
szám > max
min = szám
i
n
A 2 kivételével töröljük közülük a 2-vel oszthatóakat A megmaradó számok közül a legkisebbel, a 3-al megismételjük az előző eljárást
4. lépés
5. lépés
max = szám
39
Írjuk fel egy tetszőlegesen nagy n-ig az 1-nél nagyobb természetes számokat
szám < min i
1. lépés
Beolvasás (szám)
Folytatjuk a fenti módszert, amíg van nem törölt szám A megmaradó számok az n-nél nem nagyobb prímszámok lesznek
Faktoriális számítása Faktoriális
41
n! → n faktoriális, ahol n ≥ 0 egész szám n! = 1 * 2 * 3 * 4 * … * n Feladat
Beolvasás
Algoritmustervezés
Faktoriális kiszámítása
Határozzuk meg n! értékét! i=1→n
Pszeudo kóddal Egész n, fakt Egész i Be: n fakt = 1 i vegye fel 1-től n-ig az értékeket és hajtsd végre fakt = fakt * i Ki: „A faktoriális értéke: ”, fakt
fakt = fakt * i
42
Kiíratás
Faktoriális alkalmazása – n alatt k 43
Faktoriális alkalmazása – n alatt k II. 44
Feladat
Pszeudo kóddal Egész n, k
Határozzuk meg n alatt k értékét!
Egész nak
Algoritmustervezés
Egész i Be: n, k
n alatt k = n! / (k! * (n – k)!)
nem célszerű a faktoriálisokat egyenként kiszámolni, mert ezek nagy értékek lennének
a nevező egyik tényezőjével tudunk egyszerűsíteni
Ha n ≥ k és k ≥ 1 akkor nak = 1 i vegye fel 1-től k-ig az értékeket és hajtsd végre nak = nak * (n – i + 1) / i Ki: „n alatt k értéke: ”, nak Egyébként Ki: „Nem megfelelő értékeket adott meg.”
További algoritmusok
n alatt k 46
Matematikai algoritmusok
Beolvasás
n ≥ k és k ≥ 0 i
n
nak = 1
i=1→k
Kiíratás
Beolvasás
Nem matematikai algoritmusok
nak = nak * (n – i + 1) / i
45
Köszönöm a figyelmet!
Másodfokú egyenlet gyökeinek meghatározása A legnagyobb közös osztó meghatározása Számrendszerek közötti átváltások (2-16) Különböző számrendszereken (2-10) belül végzett műveletek Rendezések
Szöveges (string) típusú változók alkalmazása és ezekkel kapcsolatos műveletek problémái
