# Nevezetes algoritmusok, sztringek, listák

Czirkos Zoltán · 2025.09.13.

Nevezetes algoritmusok, azaz programozási tételek. Karakterkódok, logikai típus. Sztringek kezelése, for ciklus.

## 1. Emlékeztető: feladatok és eszközök

### Algoritmus

- Programozó: algoritmust tervez a feladat megoldására
- Többé-kevésbé általános
- Véges számú lépésben fut

### Vezérlési szerkezetek

- Számítási folyamat leírása: mi a lépések sorrendje
- Már ismeritek a működést, sejtitek, mi lesz az eredmény

Szekvencia

    print("Sugár?")
    r = float(input())
    t = r**2 * math.pi
    print("Területe:", t)

Elágazás

    if szam % 2 == 0:
        print("páros")
    else:
        print("páratlan")

Ciklus

    i = 0
    while i < 10:
        print(i)
        i = i+1

Példák az általánosság fogalmához:

- Prímszámok: szám → igaz/hamis. Első 100 prímet tudja? Jó, de nem elég általános. Osztók próbálgatása: ez jobb megoldás!
- Böngészőprogram: leíró kód → megjelenített oldal. Bemenet: szöveg, színek, margók, betűméretek, … Kimenet: a formázott oldal képe.

## 2. Az állásinterjús kérdés: fizz buzz

### Fizz buzz: a feladat

    1
    2
    fizz
    4
    buzz
    fizz
    7
    8
    fizz
    buzz
    11
    fizz
    13
    14
    fizzbuzz

Mondjuk sorban a számokat, de ha

- 3 többszöröse, a szám helyett: „fizz”
- 5 többszöröse, akkor „buzz”
- mindkettőé, akkor „fizzbuzz”

Ezt a feladatot gyakran állásinterjúkon is feladják, és meglepő, hogy mennyiszer elrontják a jelentkezők. (Lásd itt és itt.) Hogyan függenek össze a feltételek? Hogyan kell egymásba tenni a vezérlési szerkezeteket? Jó-e az, ha leírjuk a három vizsgálatot (3-mal, 5-tel, mindkettővel), mindenhova közé `else`-t téve? Nem lenne jó itt felsorolni az összes rossz megoldást, és megmagyarázni mindegyikről, hogy mi a bajuk – az egy egyszerű nyomkövetéssel észrevehető. Mindenki kipróbálhatja magának!

### Az oszthatóság vizsgálata

Ezt már ismerjük az előző előadásról:

    # osztható? → a maradék nulla?
    if szam % 3 == 0:
        print("fizz")

## 3. Fizz buzz: 3-mal és 5-tel is

Vigyázat! Melyik feltétel is teljesül 15-nél???

`and`
„és”: mindkét
feltétel teljesül

    # 3-mal és 5-tel is osztható
    if szam % 3 == 0 and szam % 5 == 0:
        print("fizzbuzz")

Azért kell vigyázni, mert az egyes kiírások (fizz, buzz, fizzbuzz, szám) feltételei nem zárják ki egymást. Ha egy szám 3-mal és 5-tel is osztható, akkor igaz az is, hogy 5-tel osztható.

Így a programban két lehetőségünk van. Egyik, hogy leírjuk azokat a feltételeket, amelyek teljesen kizárják egymást (pl. 3-mal és 5-tel is osztható; 3-mal igen, de 5-tel nem osztható stb.). Másik, hogy olyan vezérlési szerkezetet írunk, amely figyelembe veszi a halmaz–részhalmaz kapcsolatokat. Az utóbbi esetben az sem mindegy, hogy az elágazásokban melyik feltételt vizsgáljuk előbb. Ha a két oszthatóság együtt nem teljesül, még mindig lehet, hogy külön-külön valamelyik igen!

Az utóbbi elven működő megoldás:

    szam = 1
    while szam <= 20:
        if szam % 3 == 0 and szam % 5 == 0:
            print("fizzbuzz")
        else:
            if szam % 3 == 0:
                print("fizz")
            else:
                if szam % 5 == 0:
                    print("buzz")
                else:
                    print(szam)
        szam = szam + 1

## 4. A for ciklus és az elif

Két ötlet segítségével tehetjük ezt a programot kicsit áttekinthetőbbé. Az első a ciklust egyszerűsíti. A `változó = eleje`, `while változó < vége`, `változó += lépés` alakú ciklus is annyira gyakori, hogy külön rövidítést találtak ki hozzá. Ez a `for ... in range(...)` szerkezet. A működéséről később lesz szó, egyelőre csak a használatát mutatjuk meg. Az alábbi ciklus 1-től 10-ig írja ki a számokat:

    for x in range(1, 10+1, 1):
        print(x)        # 1 2 3 4 5 6 7 8 9 10

Azért 1-től 10-ig, mert a `range()` balról zárt, jobbról nyílt intervallumban várja a határokat. Vagyis az `1` már része lesz a sorozatnak, a `10+1` már nem (`10` még igen). A lépésközt elhagyhatjuk, ebben az esetben `1` lesz az:

    for x in range(1, 10+1):
        print(x)        # 1 2 3 4 5 6 7 8 9 10

Ha a kezdeti értéket is elhagyjuk, akkor pedig 0-nak tekinti azt a `range()`:

    for x in range(5):
        print(x)        # 0 1 2 3 4

A második ötlet az elágazásokkal kapcsolatos. Az `else`–`if` fordulat elég gyakori, ezért erre egy külön rövidítést találtak ki: az `elif` kulcsszót. Ez azért jó, mert így az `elif` sorában rögtön írhatjuk a következő feltételt, és eggyel kisebb behúzással írhatjuk tovább a kódot.

A fenti két nyelvi elemet beépítve a programba, végül ehhez jutunk:

    for szam in range(1, 20+1):
        if szam % 3 == 0 and szam % 5 == 0:
            print("fizzbuzz")
        elif szam % 3 == 0:
            print("fizz")
        elif szam % 5 == 0:
            print("buzz")
        else:
            print(szam)

# Nevezetes algoritmusok

Avagy: programozási tételek.

Avagy: programozási tételek.

## 6. Sorozatok és tételek

### Programozási tételek

Általánosságban megfogalmazott algoritmusok; mindig kicsit átalakítjuk a konkrét feladatunkhoz.

Vannak bizonyos alapvető algoritmusok, amelyeket nagyon gyakran használunk, és amelyek olyan fontosak, hogy külön nevet is kaptak. Ezeket nevezetes algoritmusnak, vagy más néven programozási tételnek szoktuk nevezni. Ezek általában valamiféle sorozatokon, nagy mennyiségű adaton dolgoznak.

### Sorozatok (nem a Dallas)

Ezek a tételek általában sorozatokkal, sok feldolgozandó elemmel szoktak foglalkozni, pl. számsorok, névsorok, kirajzolandó alakzatok. A bemutatáshoz ezért most választunk egy konkrét példát: számsorokkal fogunk foglalkozni.

Az elemszám kétféleképpen lehet adott.

- Adott hosszúságú. A sorozat hossza előre adott.
  Pl. 4 elem: 9, 1, 3, 5
- Végjeles. A sorozat végét egy speciális érték jelöli.
  Pl. 9, 1, 3, 5, −1

## 7. Hogy olvasunk be egy végjeles sorozatot?

Mi a teendő, ha a programunknak végjeles sorozatot kell beolvasnia? Melyik a legalkalmasabb vezérlési szerkezet? Pl. ha ez a bemenetünk:

    2
    3
    1
    -1

### A végjeles sorozat kezelése: a beolvasás helye

- A ciklus feltétele ez lesz: AMÍG szám ≠ −1, …
- Ez a beolvasott számtól függ → már az első előtt lennie kell beolvasásnak
- De mindig kell egy új szám → a cikluson belül is, méghozzá a végén

„az első
különleges”

    BE: szám              első
    CIKLUS AMÍG szám ≠ −1, ADDIG
        szám feldolgozása...
        BE: szám          következő (többi)
    CIKLUS VÉGE

A fenti pszeudokód a feladat megoldása. Itt a ciklus működését meg kell érteni! A ciklus egy utasítássorozatot ismétel, amíg egy feltétel fennáll. A ciklusfeltétel ellenőrzi azt, hogy a kapott szám −1-e, vagy nem. Mivel ez egy elöltesztelő ciklus, ezért ennek a feltételnek az ellenőrzése a ciklusba belépés előtt fog megtörténni. Ez azt jelenti, hogy a ciklus első elérésekor már rendelkeznünk kell egy számmal, ami a felhasználótól származik, vagyis kell lennie egy beolvasásnak a ciklus előtt. Ezt jelöli az első buborék.

Namármost, ha a feltétel igaz, akkor bekerül a végrehajtás a ciklus belsejébe. Ilyenkor éppen van egy számunk, amit a billentyűzetről kaptunk, és ami nem −1, ezért része a sorozatnak. Ezért ezt a ciklustörzs elején feldolgozzuk. Később ez a `...`-tal jelzett rész lesz az, ahova egy konkrét feladat megoldása kerülhet.

A ciklustörzs egy újabb beolvasással végződik, a következő buboréknál. Ami első ránézésre olyan, mintha a következő beolvasott számmal már nem csinálnánk semmit, de ez nincs így! A ciklustörzs végrehajtása után a vezérlés újra a ciklusfeltétel ellenőrzéséhez kerül. Ilyenkor már az új számot fogja ellenőrizni a feltétel újbóli kiértékelése – és ha igaznak adódott, vagyis ha a szám nem −1, akkor már az új szám fog az összeghez hozzáadódni. A ciklustörzs végén álló beolvasás a következő iteráció számára készíti elő a terepet. Vegyük észre, hogy ilyenkor a „terep” pont ugyanúgy néz ki, mint az első végrehajtás előtt. Van egy számunk, amit meg kell vizsgálni, hogy −1-e, és ha nem, akkor feldolgozni, végül várni a következőre.

## 8. Összegzés tétele

### Összesítsük a rendeléseket!

Írjunk programot, amely összegzi a fogyasztásunkat: a felhasználótól kapott pozitív, egész számokat összegez, amíg −1-et nem kap.

2 + 3 + 1 = ?

### Összegzés tétele

    összeg = 0                      akkumulátor
    CIKLUS AMÍG van még szám, ADDIG
        szám = következő elem
        összeg = összeg + szám
    CIKLUS VÉGE
    KI: összeg

Az „akkumulátor” változó az, amelyikben összegyűlik, akkumulálódik az eredmény. Ezt először nullázzuk, utána minden feldolgozott számot hozzáadunk. Minden iteráció végén az addig látott számok összegét fogja így tartalmazni. Ha esetleg egyszer sem ment volna be a ciklusba, akkor pedig nullát.

A bemeneti adatsor formátumát tekintve ez pont ugyanolyan, mint az előző pontban látott: egy végjeles sorozat. Úgyhogy a tétel alkalmazásához a beolvasást kicsit át kell írni az előbb látott módon: az AMÍG van még szám ciklusfeltétel `while szam != -1`-re átírása mellett a beolvasást is ki kell hoznunk a ciklus elé, illetve a ciklustörzs végére. Így jutunk el a feladat megoldásához, amely lentebb látható.

!=
nem egyenlő
Rövidítések:
a=a*b → a*=b
a=a+b → a+=b
stb.

    print("Kérem a számokat, -1: vége")

    szam = int(input())
    osszeg = 0                  # elején nulla
    while szam != -1:
        osszeg += szam          # összeg = összeg+szám
        szam = int(input())

    print("Összeg:", osszeg)

### Másik példa az „összegzésre”: faktoriális számítása

Mi a különbség az összegzés és a faktoriális számítása között programozási szempontból? Szinte semmi! Algoritmikai szempontból a kettő tökéletesen ugyanaz. Más a művelet, de ugyanaz az elv: ciklusban akkumulálunk. Csak lecseréljük:

- A kezdeti értéket 0-ról 1-re
- Az összeadást szorzásra

    print("Faktoriális")
    n = int(input("n = "))

    szorzat = 1
    i = 1
    while i <= n:
        szorzat *= i
        i += 1

    print(n, "faktoriálisa", szorzat)

Vagy rövidebben, `for` ciklussal:

    szorzat = 1
    for i in range(1, n+1):
        szorzat *= i

## 9. Számlálás tétele: osztók száma

### Feladat

Számoljuk meg, egy számnak hány osztója van (1 és saját maga is.)

1 2 3 4 5 6 7 8 9 10 11 12

### Megoldás gondolatmenete

- Legegyszerűbb: próbálgatás
- CIKLUS 1-től a számig
- HA osztható, AKKOR növelünk egy számlálót
- A számláló kezdeti értéke 0

Vegyük észre: ez is egy sorozat, méghozzá egy előre adott hosszúságú. 1-től az adott számig kell eljutni.

### Számlálás tétele

    db = 0
    CIKLUS AMÍG van még szám, ADDIG
        szám = következő elem
        HA igaz a feltétel szám-ra, AKKOR    melyikeket?
            db = db+1
        FELTÉTEL VÉGE
    CIKLUS VÉGE
    KI: db

A megoldás Python nyelven:

    szam = int(input("Kérem a számot: "))

    db = 0              # kezdetben 0
    for oszto in range(1, szam + 1):
        if szam % oszto == 0:
            db += 1     # ha ez osztója, +1

    print("Összesen", db, "osztója van.")

További példák:

- Hány páros számot kaptunk?
- Hányan születtek szeptemberben?
- Hány „e” betű van a szövegben?

## 10. A sztring típus – feladat

### Feladat

Számoljuk meg, a begépelt szövegben hány „e” betű van!

        0123456789

     30   ␣!"#$%&'
     40 ()*+,-./01
     50 23456789:;
     60 <=>?@ABCDE
     70 FGHIJKLMNO
     80 PQRSTUVWXY
     90 Z[\]^_`abc
    100 defghijklm
    110 nopqrstuvw
    120 xyz{|}~

### Karakterek (character, char)

- Betű → kódszám hozzárendelés
- Minden betűhöz, számjegyhez, írásjelhez egy kódszámot rendelnek
- A gépnek szám: belső ábrázolás, nekünk betű: külső ábrázolás
- Többféle kódolás létezik, gyakori a Unicode, ASCII („eszki”, American Standard Code for Information Interchange)
- Pl. `A`→65, `a`→97, `!`→33, `0`→48, de vezérlő kódok is: sortörés (\n), oldaltörés stb.
- Nem kell tudni fejből a kódszámokat!

## 11. Karakterek és sztringek kezelése

A sztringekkel már találkoztunk az előző előadáson. Láttuk, hogy az `input()` függvény sztringet ad (a beolvasott sort), és hogy két sztringet össze tudunk fűzni a `+` operátorral. De van sok egyéb művelet is, amivel a sztring típusú adatok kezelhetők.

Szövegek jellegzetes műveletei:

    szoveg = "Helló, világ!"
    print(szoveg)       # kiírható
    len(szoveg)         # hossza

    szoveg[1]           # "e", mert 0-tól indexelődik
    szoveg[:5]          # "Helló", csak az eleje
    szoveg[7:]          # "világ!", csak a vége
    szoveg[1:3]         # "el", balról zárt, jobbról nyílt

    "alma" + "fa"       # "almafa", összefűzés (concatenation)
    "fru" * 2           # "frufru", sokszorozás

A sztring típusnak sok egyéb művelete is van, pl. `szoveg.upper()` egy csupa nagybetűs sztringet ad vissza. A műveletek itt találhatóak meg: String Methods, de később a tárgyban is több elő fog még kerülni.

Dijkstra

Érdemes kicsit elmerengeni azon, hogy a sztringrészleteknél mit jelent a balról zárt, jobbról nyílt intervallum. Először is, tudnunk kell, hogy a sztring legelején lévő karakter a 0. indexű (sorszámú). Ezt szóban és gondolatban is nulladiknak nevezzük. (Néha pongyolán az elsőnek, mert a hétköznapi életben 1-től számozunk mindent, de jobb erre figyelni.) A fenti példában `szoveg[0]` a `H` betűt adja. A `szoveg[:5]` kifejezés a sztring első 5 karakterét, a `szoveg[7:]` pedig a sztring végét adja, a hetes indexű karaktertől (kihagyva az első hetet).

Logikusnak tűnik, hogy a szám a vágás helyét kell megjelölje. És az is logikus elvárás, hogy ha ugyanott vágjuk a sztringet kétszer – de egyszer az elejét, másszor pedig a végét véve figyelembe –, akkor a két kapott darabot összeillesztve az eredeti sztringhez jussunk. Vagyis az alábbi kifejezés minden sztringre igaz legyen:

    szoveg == szoveg[:5] + szoveg[5:]
    #                ↑ ötödikig   ↑ ötödiktől

Így lesz a legegyszerűbb dolgozni vele, semmikor nem kell azon gondolkoznunk, hogy a pozícióhoz hozzá kell-e adni egyet, vagy le kell-e vonni belőle egyet. Ez viszont azt kell jelentse, hogy a `szoveg[:5]` vágás (vagy részletesebben: a `szoveg[0:5]` vágás) tulajdonképp a 0, 1, ... 4. indexű karaketereket kell adja, jobbról nyílt intervallumban. A negyedik még igen, az ötödik már nem. A `szoveg[5:]` vágásnál pedig balról zárt az intervallum; már az 5-ös indexű karakter is része a vágott szövegnek.

Mindezt Edsger W. Dijkstra tisztázta le először. Ő holland matematikus, programozó volt. Fontosnak tartotta a levelezést és a tapasztalatcserét kollégáival. Ezért a gondolatait, megfigyeléseit, útjairól szóló írásait számozva, fénymásolt kéziratok formájában küldte el nekik. A fentiekkel kapcsolatban álljon itt egy rövid írása (EWD831).

Karakterkódok kezelése:

    ord("A")            # 65 a kódja
    chr(65)             # "A" betű

    chr(ord("A") + 3)   # "D", mert A → B → C → D

A karakterek a számítógép számára csak számok (belső ábrázolás), nekünk jelennek meg betűkként (külső ábrázolás). Az `ord()` függvénnyel megtudhatjuk, hogy egy karakternek mi a kódja; a `chr()` függvény pedig a kódból karaktert hoz létre. Az angol ábécé betűi sorban vannak a karaktertáblában, így pl. `ord("A") < ord("D")` is igaz, mert az A betű előrébb van az ábécében, mint a D. Az ékezetes betűk viszont össze-vissza vannak a kódtáblában, úgyhogy ott már sajnos nem ilyen egyszerű a helyzet.

## 12. A sztring feldolgozása karakterenként

Írjuk ki egy sztring betűit egymás alá!

    # szöveg beolvasása
    szoveg = input()

    # ciklus az elejétől a végéig
    i = 0
    while i < len(szoveg):
        print(szoveg[i])
        i += 1

A ciklusban maradás feltételében a „kisebb” relációt szokás használni, nem pedig a „kisebb vagy egyenlő” relációt. Mégpedig azért, mert így a sztring méretéből nem kell egyet levonni. Bár `i<len(szamok)` és `i≤len(szamok)-1` ugyanazt jelenti, de az `i<len(szamok)` forma ebben az esetben sokkal egyszerűbb! Szokjuk meg ezt a formát a sztringekhez, az egész világon így csinálják!

Ki kell írnunk ilyenkor az indexelést? Valójában nem:

    szoveg = "hello"
    for c in szoveg:    # c = "h", c = "e", ...
        print(c)

A `for ... in ...` ciklus lényege éppen az, hogy egy tároló, sorozat minden elemét megadja. Sztringnél ez az összes karaktert jelenti, egyesével a sztring elejétől végéig. Ha ez jó nekünk (nem minden második kell, nem fordított sorrend kell stb.), akkor bátran használhatjuk itt is.

## 13. Számlálás tétele: „e” és „E” betűk

Térjük vissza az „e” betűk számlálása feladatra!

or
„vagy”: valamelyik
feltétel teljesül
(elég az egyik)

    sor = input()

    db = 0
    for c in sor:
        if c == 'e' or c == 'E':
            db += 1

    print("Összesen", db, "darab e betű volt.")

A program a két feltételét (kis „e” betű-e, nagy „E” betű-e) VAGY kapcsolatba hozva használtuk. Ez azt jelenti, hogy bármelyik megfelel számunkra. Akár kis „e” betű van, akár „E” betű, a számlálót megnöveljük. A pongyolán megfogalmazott feladatkiírás szólhatna úgy, hogy „számoljuk meg a kicsi és a nagy E betűket” – hiába tudjuk, hogy nem lehet egy betű egyszerre kicsi és nagy is.

A programok írásakor a logikai VAGY és logikai ÉS kapcsolatok közötti különbséget mindig pontosan át kell gondolni. Azért fontos ez, mert a köznapi beszédben a kettőt sokszor pont fordítva használjuk. Például elhangozhat egy tankörben a következő mondat: „Tegye fel a kezét, aki Budapesten és Debrecenben született!” Nyilvánvaló, hogy senki nem születhetett egyszerre Budapesten ÉS Debrecenben. Egyszerűen csak ezt a gondolatot rövidítjük: „Tegye fel a kezét mindenki, aki Budapesten született, és tegye fel a kezét az is, aki Debrecenben született!” A matematikailag, és ezért a programjainkban is korrekt változat élő beszédben szokatlanul hangzana: „Tegye fel a kezét mindenki, aki Budapesten vagy Debrecenben született!”

Vigyázat: a Boole-algebrában használt VAGY kapcsolat kicsit mást jelent, mint a hétköznapi értelemben használt. A hétköznapi VAGY általában azt szokta jelenteni, hogy a kettő közül csak az egyik lehet. A Boole-algebrában megengedjük a VAGY kapcsolatnál azt is, hogy mindkét feltétel igaz legyen. Tehát `True or True` értéke is `True` lesz. Ebben a konkrét példában persze ez nyilván lehetetlen, mert nem lehet a betű egyszerre kis `e` és nagy `E` is. Viszont a `szam % 3 == 0 or szam % 5 == 0` példában lehetséges lenne; a 3 és az 5 is osztója a 45-nek, és `szam == 45` esetén az egész kifejezés igaznak számít. `6` és `10` esetén is igaz amúgy, mert a 3 és 5 közül legalább az egyik osztója ezeknek a számoknak.

A fenti kód egyébként rövidebben így is írható:

    db = szoveg.count("e") + szoveg.count("E")

Itt az `"e"` és `"E"` részsztringek előfordulásait keressük meg, és számukat adjuk össze. A sztringek `.count()` függvénye éppen a számlálás tételét valósítja meg; ha egyetlen egy karakterből álló sztringet adunk neki, akkor tulajdonképpen a betű előfordulásainak számát fogja adni.

## 14. Szélsőérték keresése: a leg…

### Melyik a legmagasabb rakéta?

Olvassunk be a billentyűzetről a magasságokat! Hány darabot – kérdezzük a felhasználótól! Melyik volt a legnagyobb közülük?

### Szélsőértékkeresés tétele

    legnagyobb = első elem      első
    CIKLUS AMÍG van még szám, ADDIG
        szám = következő elem   többi
        HA szám > legnagyobb, AKKOR
            legnagyobb = szám
        FELTÉTEL VÉGE
    CIKLUS VÉGE
    KI: legnagyobb

Vigyázat! Az első „tippet” is a sorozatból kell venni! Általános esetben elvi hibás a legnagyobb=−1000 kezdetű vagy hasonló megoldás! (Ha az összes szám kisebb lenne −1000-nél, akkor hibás lenne az eredmény.)

### A maximumkeresés Python nyelven

    db = int(input("Hány szám lesz? "))

    # az első külön
    aktualis = float(input("1. szám: "))
    maximum = aktualis

    # a többit ciklusban
    for i in range(2, db+1):
        aktualis = float(input(str(i) + ". szám: "))
        if aktualis > maximum:
            maximum = aktualis

    print("Legnagyobb:", maximum)

## 15. Eldöntés tétele

### Feladat (általános megfogalmazásban)

Megvizsgálni, szerepel-e egy bizonyos tulajdonságú elem a sorozatban.
Például: prímszám-e. Ahogy találunk egy osztót, tudjuk, hogy nem az.

### Az eldöntés tétele

    találat = HAMIS
    CIKLUS AMÍG van elem ÉS NEM találat
        szám = következő elem
        HA szám = keresett, AKKOR
            találat = IGAZ                megvan: leáll a keresés
        FELTÉTEL VÉGE
    CIKLUS VÉGE
    KI: találat

A ciklus után a találat változó tartalmazza az eredményt: igaz v. hamis.

## 16. A logikai típus Pythonban

### Logikai típus

- Lehetséges értékei: IGAZ, HAMIS; műveletek: és, vagy, tagadás.
- A típus neve: `bool`, az igazat a `True`, a hamisat a `False` jelöli.

`not`
tagadás

    kisebb = x < y             # kisebb-e?
    if kisebb:
        print("x kisebb, mint y")

    piros = False              # hamis, igaz
    piros = True
    if not piros:
       print("nem piros, hanem más színű")

A logikai típusú értékre kiértékelődő kifejezések (`not` – tagadás, `and` – és kapcsolat, `<` – kisebb, mint stb.) épp ilyen típusú értéket állítanak elő.

Ha logikai kifejezéseket írunk egy elágazásban vagy ciklusban, nem szokás az `== True`-t és `!= False`-t kiírni. Egyszerűen fölösleges, redundáns, nem tesz hozzá semmit a programhoz. Ezzel az erővel az `if x < y:` helyett is írhatnánk azt, hogy `if (x < y) == True:`... De nem tesszük.

## 17. Eldöntés: prímszám-e (Python kód)

    szam = int(input("Kérem a számot: "))

    vanoszto = False
    oszto = 2
    while oszto < szam and not vanoszto:
        if szam % oszto == 0:
            vanoszto = True
        oszto += 1

    if vanoszto:            # volt találat?
        print("Nem prím.")
    else:
        print("Prím.")

Ha el kell dönteni egy számról, hogy prímszám-e, sokkal értelmesebb dolog az eldöntés tételét alkalmazni, mint a számlálás tételét. Mondhatjuk ugyan, hogy megszámoljuk a szám osztóit, és ha csak kettő (egy és saját maga), akkor az egy prímszám. De miért kellene a kérdés megválaszolásához megvizsgálni az összes osztót? Miért ne állnánk meg már az elsőnél, azt mondva, hogy kérem szépen, ez nem prímszám?! (Az osztókat amúgy elég lenne a szám feléig vizsgálni, hiszen ha osztója a fele, akkor osztója 2 is. Sőt elég lenne a gyökéig, ugyan emiatt.)

Ezt a ciklust egyébként, annak összetett feltétele miatt (van még vizsgálandó szám és nem találtunk osztót), nem tudnánk közvetlenül `for` ciklussal megfogalmazni. A `for ... in range(...)` szerkezet használatához az kell, hogy végig akarjunk menni a teljes tartományon.

### A De Morgan-féle szabály

A ciklusba belépésnek két feltétele van, 1) hogy nem értünk a számok végére, ÉS 2) nem találtunk még osztót. Mindkettőnek egyszerre teljesülnie kell, hogy bemenjünk a ciklusba. Ha nem mentünk be, akkor valamelyik – az egyik VAGY a másik – nem teljesült. Ezt vizsgáljuk a ciklus után: tudnunk kell, hogy melyik feltétel miatt lett vége a ciklusnak.

Itt jól látható a Boole-algebrában is tanult De Morgan azonosság: ha az együttes feltétel tagadását tagonként írjuk fel, akkor az ÉS-t VAGY-ra kell cserélnünk. Bemegyünk a ciklusba, ha IGAZ az első feltétel ÉS IGAZ a második feltétel; NEM megyünk be a ciklusba, ha HAMIS az első feltétel VAGY HAMIS a második feltétel.

Ebben a konkrét esetben: `not (oszto < szam and not vanoszto)` azonos az `oszto >= szam or vanoszto` kifejezéssel. Az is tudható, hogy ha a ciklusból kilépve `oszto < szam` még mindig igaz, akkor a kilépés a `not vanoszto` nem teljesülése miatt következett be, azaz, ha `oszto < szam`, akkor biztos, hogy `vanoszto`.

# Listák

## 19. Tíz darab szó

### Feladat

Kérjünk a felhasználótól 10 szót, és utána írjuk ki őket fordított sorrendben!

### Megoldás – sorminta???

    a = input()
    b = input()
    c = input()
    …
    print(c)
    print(b)
    print(a)

### Mire lenne itt szükség?

Az eddigi programjainkban:

- Csak néhány nevesített változóval dolgoztunk, amelyeknek mind kitüntetett szerepe volt
- Nem tudtuk azt mondani, hogy „sok”
- Csak a beérkezés sorrendjében tudtuk feldolgozni az adatokat

Ami hiányzik:

- Jó lenne egyszerre több elemet is tárolni
- Az elemeket sorszámozva hivatkozni (első szó, második szó…), mert akkor egy ciklus végigmehetne az elemeken
- Az elemeket tetszőleges sorrendben elérni, mert akkor kiírhatnánk fordított sorrendben

## 20. A lista

### Lista (list)

- Tároló, amely számokat, szövegeket, ... tartalmazhat
- Az elemek sorszámozva vannak, indexelhetőek.

a0 | a1 | a2 | a3 | a4 | a5
--- | --- | --- | --- | --- | ---
99 | 71 | 3 | -45 | 47 | 12

A listába általában egyforma típusú elemeket teszünk, hiszen együtt akarjuk feldolgozni őket. Létezhet egészek, valósak, szövegek, vagy akár logikai típusú változók listája is. Pythonban az elemek számozása 0-tól történik, és ez a legtöbb másik programozási nyelvben is így van.

Aki tanult már programozni, ezzel a típussal, az indexelt elemeket tároló adatszerkezettel tömb (array) néven is találkozhatott. Tömbnek általában az olyan tárolót nevezzük, aminek a mérete fix, előre adott. Ezeket az elnevezéseket gyakran összemossák, mert az egyes programozási nyelvek eltérőképp kezelik ezeket. A ProgAlap tárgyban mindig listának fogjuk ezeket nevezni; esetleg tömbnek, ha nagyon fontos épp kiemelni, hogy fix a méret. Az Algoritmusok és gráfok tárgyban ugyanez a szóhasználat szerepel majd; tömb alatt fix méretű tárolót kell érteni.

### Szóhasználat

- Egyszerű adattípusok: egész, valós, logikai, …
- Összetett adattípus: pl. a lista (több egész számból)

## 21. A listák kezelése I.

Létrehozás szögletes zárójellel:

Listát szögletes zárójelbe (bracket) írt adatokkal tudunk létrehozni:

    szamok = [9.3, 7.5, 3.7, 0.1, 4.2]

Az így létrehozott lista 5 elemű lesz. A sor elején álló, 0-s sorszámú elem a `9.3`, a sor végén pedig a 4-es indexű elem áll, ez a `4.2`.

Elem elérése: szintén szögletes zárójellel.

A lista indexelése (indexing), más néven címzése is a szögletes zárójellel történik. A művelet által megkapjuk a lista egyetlen egy elemét, amely ugyanúgy használható, mint egy önálló változó. Új érték adható neki, de szerepelhet bármilyen más kifejezésben, például egy `print()` paramétereként is.

    szamok[2] = float(input())
    print(szamok[3])        # 0.1

Méret lekérdezése:

Lista hossza lekérdezhető a `len()` beépített függvénnyel:

    print(len(szamok))      # 5

A lista feldolgozása: ciklussal. Az index tartománya: 0-tól méret−1-ig!

A listákat leggyakrabban ciklussal dolgozzuk fel. Ilyenkor figyelni kell arra, hogy a listaindexek tartománya 0-tól méret−1-ig-ig terjed. A lenti egy tipikus listás ciklus. Nullától indul az iterátor (ez a lista legelső eleme), és egyesével növekszik.

    i = 0
    while i < len(szamok):  # i = 0 ... i = 4
        print(szamok[i])
        i += 1

A ciklusban maradás feltételében a „kisebb” relációt szokás használni, pontosan ugyanúgy, mint a sztringeknél. Ha `i < len(szamok)`-at írunk, nem kell levonni egyet a méretből, és egyszerűbb, áttekinthetőbb a program. Ezért erre ugyanazt mondjuk, mint a sztringeknél: használjuk ezt a formát a listákhoz is!

## 22. A listák kezelése II.

A `print()` „felismeri” a listát, és ki tudja írni a teljes sort:

    szamok = [1, 2, 3, 4, 5]
    print(szamok)       # [1, 2, 3, 4, 5]

Lista végéhez hozzá tudunk fűzni új elemet:

    szamok.append(6)
    print(szamok)       # [1, 2, 3, 4, 5, 6]

El tudjuk dobni a végén lévő elemet:

    szamok.pop()
    print(szamok)       # [1, 2, 3, 4, 5]

Vannak további műveletek is, de azokkal majd később foglalkozunk.

## 23. A listák kezelése III.

Feltűnhetett az eddigi listás programocskákban, hogy mindig ugyanolyan kódrészlettel jártuk be a listát. Azaz ugyanolyan kódrészlettel iteráltunk (iterate) rajta. Mindig `i = 0`, mindig `while i < len(lista)`, mindig `i += 1`. A lista elemét is mindig `lista[i]`-vel kell elérni.

Indexek a `0...méret-1` tartományban:

    i = 0
    while i < len(szamok):
        print(szamok[i])
        i += 1

Lehet ezt rövidebben? Először is, az indexeket meghatározó ciklust kicserélhetjük egy `for i in range(...)` szerkezetre. Mivel 0-tól indulunk, ezért a kezdőérték elhagyható. A lista `len(szamok)`-adig eleme pedig már túlindexelés (`0`-tól `len(szamok) - 1`-ig vannak az érvényes indexek), ezért épp kapóra jön az is, hogy a `range()` jobbról nyílt intervallumot vár. Sőt egyébként épp ezért van így kitalálva. A fenti programrész kicsit egyszerűbben tehát:

    for i in range(len(szamok)):    # i = 0 ... len(szamok)-1
        print(szamok[i])

És van-e még egyszerűbb megoldás? Van, mert a sztringeknél látott `for ... in sorozat`, a `for` ciklus listákra is működik.

A legrövidebb megoldás:

    szamok = [9.3, 7.5, 3.7, 0.1, 4.2]
    for x in szamok:    # x = 9.3, x = 7.5, ...
        print(x)

Ezt a nyelvi elemet csak akkor tudjuk használni, ha 1) sorrendben kellenek az elemek, 2) hiánytalanul (pl. nem csak minden második), és 3) nem érdekes az algoritmusunkban az elem indexe. Mivel egyébként általában ez a helyzet, emiatt a `for` ciklust használjuk gyakrabban, szemben a `while`-lal.

Vigyázat: a `for` ciklus esetén a megadott változóban a lista elemeit kapjuk, nem az indexeket! Vagyis tulajdonképp a változónk fölveszi a listában tárolt számok (sztringek, ...) értékeit.

## 24. Tíz darab szó – és fordítva, 1. megoldás

A lista indexelése 0-tól 9-ig, aztán 9-től 0-ig.

    1. szó: alma
    2. szó: körte
    3. szó: barack

    …

    3. szó: barack
    2. szó: körte
    1. szó: alma

    # 10 üres sztring: ["", "", "", ...]
    szavak = [""] * 10

    # beolvasás
    i = 0
    while i < len(szavak):
        print(str(i+1) + ". szó: ", end="")
        szavak[i] = input()
        i += 1

    # kiírás
    i = len(szavak)-1
    while i >= 0:
        print(str(i+1) + ". szó:", szavak[i])
        i -= 1

Ebben a megoldásban előre létrehozunk egy 10 elemű listát. Ezt rögtön a program elején megtesszük, mert tudjuk, hogy ennyi szó kezelését kérte a feladat. A listát létrehozó kifejezés a `[""] * 10`: ez az egy elemű, csak egy üres sztringet tartalmazó listát „szoroz meg 10-zel”, vagyis fűz 10-szer egymás után. Így kapjuk meg a 10 elemű, előkészített listát, amelyik 0-tól 9-ig indexelhető, és minden helyen üres sztringek vannak benne.

Ezek után a beolvasás 0-tól 9-ig, a kiírás pedig 9-től 0-ig halad végig a listán. Szerencsére a lista méretét csak egyetlen egy helyen kell a programban szerepeltetni. Nem írjuk be mindenhova, hogy 10! Ehelyett inkább használjuk a `len()` függvényt, amellyel lekérdezhető.

A kiírásban mindig hozzáadunk egyet az indexhez, amikor a felhasználónak szóló szövegben a sorszámot hivatkozzuk. Így a programban az indexek tartománya 0…9 (ez kötelező, a Python nyelv így működik), de a felhasználó 1…10 sorszámokat lát.

A két ciklus egyébként megfogalmazható lenne `for ... in range` segítségével is.

## 25. Tíz darab szó – és fordítva, 2. megoldás

Használjuk az `.append()` és `.pop()` függvényeket!

    1. szó: alma
    2. szó: körte
    3. szó: barack

    …

    3. szó: barack
    2. szó: körte
    1. szó: alma

    # üres lista
    szavak = []

    # beolvasás
    for i in range(10):
        print(str(i+1) + ". szó: ", end="")
        szavak.append(input())

    # kiírás
    while szavak != []:
        print(str(len(szavak)) + ". szó:", szavak.pop())

A második megoldás teljesen máshogy működik. Ebben kihasználjuk azt, hogy az `.append()` segítségével a lista végéhez tudunk hozzátenni elemet, a `.pop()` segítségével pedig a lista végéről tudunk elvenni egyet. Vagyis ha `.append()`-elünk három szót (legyenek ezek `alma`, `barack`, `cseresznye`), aztán `.pop()`-olunk hármat, akkor közben a lista így néz majd ki:

    []
    ["alma"]
    ["alma", "barack"]
    ["alma", "barack", "cseresznye"]
    ["alma", "barack"]
    ["alma"]
    []

A programunkban ugyanez történik. Kezdetben ezért egy üres listától indulunk, ahhoz fűzzük az elemeket: `.append()`. Aztán visszafelé pedig addig vesszük el őket a végéről: `.pop()`, amíg a lista el nem fogy: `szamok == []`. Persze a ciklusnak belépési–bennmaradási feltétele van, tehát `szavak != []`-t kell írni. Egyébként írhattunk volna `len(szavak) > 0`-t is.

Melyik megoldás jobb? Tulajdonképp mindegy, egyformán jó mindkettő.

## 26. Tételek megvalósítása listákon: másolás

### Lista másolása

    forras = [9, 2, 4, 1, 5]

    cel = []
    for szam in forras:
        cel.append(szam)

    print(cel)  # [9, 2, 4, 1, 5]

Természetesen ennek a tételnek is meg lehet adni a pszeudokódját általánosságban:

    CIKLUS AMÍG van még szám, ADDIG
        BE: szám
        KI: szám
    CIKLUS VÉGE

A fenti kód ennek a tételnek a megvalósítása abból a célból, hogy egy lista tartalmát egy másikba lemásoljuk.

### Beépített módszer: `list()`

Erre van egyébként egy sokkal egyszerűbb megoldás Pythonban:

    forras = [9, 2, 4, 1, 5]

    cel = list(forras)

    print(cel)  # [9, 2, 4, 1, 5]

A `list(lista_neve)` egy másolatot készít a listánkról; itt azt tesszük a `cel` nevű változóba. A `cel = forras` nem elegendő; hogy miért, arról egy későbbi előadáson lesz majd szó.

## 27. Tételek megvalósítása listákon: összegzés

### Lista elemeinek összegzése

    szamok = [9, 2, 4, 1, 5]

    osszeg = 0
    for sz in szamok: # sz = 9, sz = 2, ...
        osszeg += sz

    print("Összeg:", osszeg)

### Beépített módszer: `sum()`

Erre is van beépített eszköz, a `sum` függvény. Ennek paramétere a lista, értéke pedig az abban található összes szám összege:

    szamok = [9, 2, 4, 1, 5]
    print("Összeg:", sum(szamok))

Látszik, hogy érdemes körbenézni a beépített függvények közt, mielőtt saját magunk implementálunk egy algoritmust. Ha alkalmas a beépített eszköz, használjuk azt! Ha nem, akkor pedig írjunk sajátot. Például az összes elem összegét megkaphatjuk a `sum()` függvénytől, de az összes elem szorzatát adó függvényt magunknak kell megírnunk, mert nincs olyan.

## 28. Tételek: kiválogatás

Páros elemek egyik listába, páratlanok a másikba.

    szamok = [3, 7, 2, 8, 6]

    paros = []
    ptln = []
    for szam in szamok:
        if szam % 2 == 0:
            paros.append(szam)
        else:
            ptln.append(szam)

    print("Párosak:", paros)
    print("Páratlanok:", ptln)

Ez az algoritmus egy adott tulajdonság szerint szétválogatja a lista elemeit. Amelyek rendelkeznek egy bizonyos tulajdonsággal (itt: párosak), azokat bemásolja az egyik listába, a többit pedig a másikba. Az eredeti lista változatlanul marad. A két cél lista kezdetben üres, és azokhoz `.append()`-eljük az egyes számokat.

## 29. A túlindexelés

### Túlindexelés: nagy hiba!

A Python ellenőrzi a túlindexelést, és `IndexError` típusú hibát kapunk:

    szamok = [3, 7, 2, 8, 5]
    print(szamok[5])            # csak 0...4 lehetett volna

    Traceback (most recent call last):
      File "proba.py", line 2, in <module>
        print(szamok[5])
    IndexError: list index out of range

A lista túlindexelése csak futási időben, azaz a program használata közben derül ki. Könnyen elképzelhető olyan programozási hiba, amikor bizonyos bemenetekre a programunk túlindexeli a listát, más bemenetekre nem; így néha működik, néha nem. Ez igen kellemetlen, mert lehet, hogy a hibajelenség csak a felhasználónál fog jelentkezni.

### Negatív indexek?

A negatív indexekkel a lista végét érjük el:

    szamok = [3, 2, 7, 8, 5]

    print(szamok[-1])   # 5
    print(szamok[-2])   # 8

[0] | [1] | [2] | [3] | [4]
--- | --- | --- | --- | ---
3 | 2 | 7 | 8 | 5
[-5] | [-4] | [-3] | [-2] | [-1]

Vigyázat: biztos ez volt a cél?

Bár a listát a vége irányába túlindexelve hibát kapunk, az „elején túlindexelve” a végét látjuk. Tehát `szamok[-1]` az utolsó elem, `szamok[-2]` az utolsó előtti és így tovább. A negatív indexekkel `-1`-től `-len(lista)`-ig mehetünk, ismét elérve az elejére; többször már nem mehetünk körbe.

Ezzel nagyon vigyázni kell. Néha nagyon jól jön, hogy ilyet tudunk csinálni, máskor viszont ez a lehetőség elfedheti előlünk a programozási hibánkat! Gondoljunk például egy visszafelé menő ciklusra: ha a végétől az elejéig dolgozzuk épp fel a listát, és túlmegyünk a `0`. indexű elemen, nem fogunk hibajelzést kapni. Pedig ha lett volna, akkor hamarabb észrevesszük, hogy hibás a programunk!

## 30. Mikor használunk listát?

Tipp: emlékezni
kell az összes
elemre → lista

### Listák használata: példák

- Fordított sorrendű kiírás,
- Növekvő sorrendbe rendezett kiírás,
- Átlagnál nagyobb számok kiírása.

Miért is kell eltárolnunk az összes számot, ha az a feladat, hogy írjuk ki a beolvasott számok közül az átlagnál nagyobbakat? Azért, mert az átlaguk akkor derül ki, amikor már láttuk az összeset. Ha pedig már megvan az átlag, csak akkor tudjuk eldönteni az elsőről, hogy ki kellett volna-e írni, a másodikról úgyszintén, és így tovább. Tehát emlékeznünk kell, mik voltak a számok.

### Kell lista vagy nem kell?

- Tipikus hiba listát használni, amikor nincs rá szükség.
- Összeg, keresés, szélsőérték: ezekhez nem kell, nem kell emlékezni a régiekre és sorrendben kell feldolgozni őket.

## 31. Összefoglalás

Az előadáson megismertek alapján tudni kell:

- bonyolult(abb) feltételeket használó szerkezeteket létrehozni (if/elif/else)
- for ciklust használni
- alapvető programozási tételeket (összegzés, számlálás, eldöntés, szélsőérték keresés)
- karaktereket és sztringeket kezelni, különös tekintettel az indexelésre
- listákat kezelni és az alapvető programozási tételeket a listákon elvégezni