A *típusalgoritmusok* olyan „minták”, amelyek nagyon sok feladatban ugyanúgy működnek: - összegzés - eldöntés - kiválasztás - keresés - megszámlálás - maximum-kiválasztás Mindenhol feltételezzük, hogy van egy listánk: `L[0..n-1]`. ## Összegzés (SUM) **Cél:** elemek összege (vagy pl. pontszámok, bevétel, stb.) >[!note] Pszeudó kód >``` >összeg ← 0 >for i = 0..n-1 > összeg ← összeg + L[i] > endfor > kiír(összeg) >``` >[!note] Python kód >```python >def osszegzes(L): > osszeg = 0 > for x in L: > osszeg += x > return osszeg > >print(osszegzes([3, 1, 4])) # 8 >``` ## Eldöntés (DECISION / ANY) **Cél:** igaz/hamis kérdés: „Van-e olyan elem, ami … ?” >[!note] Pszeudó kód >``` > válasz ← HAMIS >for i = 0..n-1 > if L[i] teljesíti a feltételt then > válasz ← IGAZ > break > endif > endfor > kiír(válasz) >``` >[!note] Python kód - Van-e `L`-ben negatív szám? >```python >def eldontes(L): > valasz = False > for x in L: > if x < 0: > valasz = True > break > return valasz > print(eldontes([2, 5, -1, 9])) # True print(eldontes([2, 5, 1, 9])) # False >``` ##  Kiválasztás (SELECTION) **Cél:** _biztosan létezik_ legalább egy elem, ami teljesíti a feltételt, a feladatunk ezen elemek (vagy indexek) kigyűjtése. >[!note] Pszeudó kód - elemek kiválasztása >``` > kiválasztottak ← üres lista > for i = 0..n-1: > if L[i] teljesíti a feltételt then > a kiválasztottakhoz hozzáadjuk L[i]-t > endif >endfor >kiír(kiválasztottak) >``` >[!note] Pszeudó kód - indexek kiválasztása >``` > indexek ← üres lista > for i = 0..n-1: > if L[i] teljesíti a feltételt then > az indexekhez hozzáadjuk i-t > endif >endfor >kiír(indexek) >``` >[!note] Python kód - Páros számok kiválasztása >```python >def kivalasztas_paros(L): > paros_szamok = [] > for x in L: > if x % 2 == 0: > paros_szamok.append(x) > return paros_szamok > >print(kivalasztas_paros([1, 2, 3, 4, 5, 6])) # [2, 4, 6] >``` >[!note] Python kód - Páros számok kiválasztása indexekkel >```python >def kivalasztas_paros_index(L): > indexek = [] > for i in range(len(L)): > if L[i] % 2 == 0: > indexek.append(i) > return indexek > >print(kivalasztas_paros_index([1, 2, 3, 4, 5, 6])) # [1, 3, 5] >``` ## Keresés (SEARCH) **Cél:** megkeresni, van-e olyan elem, ami teljesíti a feltételt; ha igen, hol van (index), ha nem, akkor jelezni, hogy nincs ilyen elem. >[!note] Pszeudó kód - keresés >``` > index ← -1 > for i = 0..n-1: > if L[i] teljesíti a feltételt then > index ← i > break > endif >endfor >print(index) >``` >[!note] Python kód - 42 keresése >```python >def kereses_index(L, target): > index = -1 > for i in range(len(L)): > if L[i] == target: > index = i > break > return index > > print(kereses_index([5, 42, 7], 42)) # 1 > print(kereses_index([5, 8, 7], 42)) # -1 >``` ## Megszámlálás (COUNT) **Cél:** megszámolni hány elem teljesíti a feltételt. >[!note] Pszeudó kód - megszámlálás >``` > db ← 0 > for i = 0..n-1: > if L[i] teljesíti a feltételt then > db ← db + 1 > endif >endfor >print(db) >``` >[!note] Python kód - 3-mal osztható számok > >```python >def megszamlalas(L) > db = 0 > for x in L: > if x % 3 == 0: > db += 1 > return db > >print(megszamlalas([3, 6, 7, 9, 10])) # 3 >``` ## Maximum-kiválasztás (MAX-SELECTION) **Cél:** a legnagyobb elem (és gyakran az indexe). >[!note] Pszeudó kód - maximum-kiválasztás >``` > max ← L[0] > maxIndex ← 0 > for i = 1..n-1 > if L[i] > max then > max ← L[i] > maxIndex ← i > endif > endfor > kiír(max, maxIndex) >``` >[!note] Python kód - maximum kiválasztás > >```python >def maximum_kivalasztas(L): > max_ertek = L[0] > max_index = 0 > for i in range(1, len(L)): > if L[i] > max_ertek: > max_ertek = L[i] > max_index = i > return max_ertek, max_index > >print(maximum_kivalasztas([2, 10, 3, 10])) # (10, 1) (első max) >``` ## Feladatok A következő feladatok mind **egy ismert algoritmikus gondolkodási mintára** épülnek. A feladatok **NEM** mondják meg, melyik típusalgoritmust kell használni, ezt neked kell felismerned! ### Könnyű >[!task] Feladat > Egy osztályban minden tanuló matematika dolgozatot írt. Adott egy lista, amely a dolgozatok pontszámait tartalmazza.  Határozd meg, hogy összesen hány pontot értek el a tanulók! >[!task] Feladat >Egy jelszóellenőrző program vizsgálja a beírt jelszót.  A jelszó karakterei egy listában vannak eltárolva.  írj programot, amely megállapítja, hogy van-e benne számjegy! >[!task] Feladat >Egy futóversenyen a célba érkezési idők (másodpercben) sorban vannak eltárolva.  Írd ki, hogy hány versenyző ért célba 300 másodpercnél gyorsabban! ### Közepes >[!task] Feladat >Egy könyvtár adatbázisában egy lista tárolja a könyvek oldalszámát. Készíts programot, amely kigyűjti azokat a könyveket, amelyek legalább 500 oldalasak! >[!task] Feladat >Egy buszjegy-ellenőrző rendszerben egy lista tartalmazza az utasok bérletének érvényességi napjait (pozitív szám: még érvényes, 0 vagy negatív: lejárt). Írj programot, amely megállapítja, hogy volt-e olyan utas, akinek már lejárt a bérlete! >[!task] Feladat >Egy online bolt napi eladásait egy lista tartalmazza (forintban).  Határozd meg, hogy melyik napon volt a legnagyobb bevétel, és add meg annak értékét is! ### Nehéz >[!task] Feladat >Egy iskolai versenyen a diákok pontszámait egy lista tartalmazza.  Írj programot, amely visszaadja azoknak a diákoknak a sorszámát, akik legalább 80 pontot értek el! >[!task] Feladat >Egy meteorológiai állomás egy héten mért hőmérsékleteit tárolja egy listában.  Írj programot, amely megállapítja, hogy volt-e olyan nap, amikor a hőmérséklet fagypont alá esett, és ha igen, add meg az első ilyen nap indexét! >[!task] Feladat >Egy videojátékban a játékos minden pályán szerzett pontszámait egy lista tartalmazza. Számítsd ki: >- az összes pontszámot, és >- hogy hány pályán ért el a játékos 100 pontnál többet!