# 4. hét: nevezetes algoritmusok, listák

Czirkos Zoltán, Frey Balázs, Bulla Ádám · 2025.10.06.

Listákkal végezhető műveletek. Egyszerűbb adatszerkezetek építése, indirekt adatelérés.

## 1. Sztring formázása: "A válasz: 42."

Írj programot, amely kér a felhasználótól két számot, és kiírja az összegüket! Méghozzá pontosan ebben a formában:

    a = 30  a számot a felhasználó adja meg
    b = 12

    A válasz: 42.

Oldd meg a feladatot kétféleképpen:

- Állítsd elő sztringek összefűzésével és konverzióval a kiírandó szöveget!
- Alkalmazd a sztringek formázási lehetőségeit, az előadáson tanult módon!

## 2. Lista megfordítása

A listák `.reverse()` függvénye megfordítja a listát, amelyre meghívják:

    szamok = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    szamok.reverse()
    print(szamok)

    [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]

Készíts listákat megfordító algoritmusokat, amelyek a következőképpen működnek:

- Adott egy lista az `eredeti` nevű változóban. Járd be ezt visszafelé (végétől az elejéig), és fűzd hozzá a `forditott` nevű listához a benne tárolt adatokat!
- Adott egy újabb lista az `eredeti` nevű változóban. Minden végéről kivett elemet fűzz hozzá egy új lista végéhez!
- Fordítsd meg a listát helyben! Cseréld meg az első és az utolsó, a második és az utolsó előtti, ... elemét!

Megoldás

Új listába átmásolva az elemeket:

    eredeti = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    forditott = []
    i = len(eredeti)-1
    while i >= 0:
        forditott.append(eredeti[i])
        i -= 1

    print(forditott)

Új listába áthelyezve az elemeket, az eredeti listát elfogyasztva:

    eredeti = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    forditott = []
    while len(eredeti) > 0:
        forditott.append(eredeti.pop())

    print(forditott)

Helyben megfordítva:

    lista = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    eleje = 0
    vege = len(lista)-1
    while eleje < vege:
        temp = lista[eleje]
        lista[eleje] = lista[vege]
        lista[vege] = temp

        eleje += 1
        vege -= 1

    print(lista)

### Vágás és lépésköz

Megjegyzés a vágáshoz. Korábban már szó volt előadáson, hogyan lehet hozzáférni egy szöveg bizonyos részeihez:

    szoveg = "Helló, világ!"
    print(szoveg[1:3])  # el

A valóságban van egy harmadik szám is, mely a lépésközt adja meg a vágás során. Például, ha szeretnénk minden második karaktert kiíratni:

    szoveg = "Helló, világ!"
    print(szoveg[::2])  # Hló iá!

A lépésköz felvehet negatív értéket is, ekkor az ellenkező irányba lépünk. És mindez működik listákkal is. Emiatt `lista[::-1]`-gyel fordított listát kapunk

## 3. Eldöntés

Alább látható az eldöntés tételének egy alkalmazása, ahogy az előadáson láttad. A program eldönti, hogy egy számnak van-e valódi osztója, és így megválaszolja a kérdést: prímszám-e a felhasználó által megadott szám.

    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.")

Másold át ezt a kódot a fejlesztőkörnyezetbe! Egészítsd ki úgy, hogy a ciklusfeltétel vizsgálata előtt mindig kiírod soronként az alábbi értékeket:

1. a számot,
2. az osztót,
3. az osztó kisebb-e a számnál, illetve a `not vanoszto` kifejezés értékét – vagyis a ciklusfeltétel két oldalát.

Ügyelj arra, hogy ehhez két helyre kell `print()`-eket írnod. Valami ilyesmit kell kapj:

    Kérem a számot: 25

    25  2   True    True
    25  3   True    True
    25  4   True    True
    25  5   True    True
    25  6   True    False
    Nem prím.

Próbáld ki a programot az alábbi számokra: 21, 1000000, 13, 25. Mit lehet mondani a két oszlopban megjelenő logikai értékekről?

1. Milyen értékek vannak az `oszto < szam` oszlopban és a `not vanoszto` oszlopban a `21` esetén? Miért áll meg a ciklus?
2. Mi a helyzet a `7` esetén? Miért áll meg a ciklus?

A beadott fájlban kommentekbe tedd a válaszokat!

Megoldás

A lényegi rész:

    vanoszto = False
    oszto = 2
    print(szam, oszto, oszto < szam, not vanoszto, sep="\t")
    while oszto < szam and not vanoszto:
        if szam % oszto == 0:
            vanoszto = True
        oszto += 1
        print(szam, oszto, oszto < szam, not vanoszto, sep="\t")

A 21 esetén a kimenet:

    21  2   True    True
    21  3   True    True
    21  4   True    False

A ciklus azért állt meg, mert `21 % 3 == 0`, tehát a 3-nál a `vanoszto` változó értéke `True` lett. Utána az `oszto` még megnő 1-gyel, és `4 < 21`, de a `not vanoszto` már `False.`

A 7 esetén:

    7   2   True    True
    7   3   True    True
    7   4   True    True
    7   5   True    True
    7   6   True    True
    7   7   False   True

A 7 prímszám, ezért `vanoszto` értéke `False` marad, azaz a `not vanoszto` kifejezése mindvégig `True`. Az `oszto < szam` lesz az, ami hamissá válik, amikor eléri az osztó a 7-et.

## 4. Növekvő sorozat-e

Adott egy számokból álló lista. A programodnak azt kell eldöntenie, hogy a számok növekvő sorozatot alkotnak-e (rendezett-e a lista), és ezt kiírni a kimenetre!

Melyik programozási tételt kell ehhez használnod? Mit jelent az elempárokra nézve, hogy rendezett a lista? Mikor mondhatod azt, hogy nem alkotnak növekvő sorozatot?

Hozz létre tíz elemű listát, amin tesztelsz! Próbáld ki a programod olyan bemenetekre is, ahol a rendezettség a) több helyen elromlik, b) egy helyen romlik el, c) az elején van a hiba, d) a végén van a hiba!

Megoldás

Akkor rendezett a sorozat, ha minden eleme nagyobb, vagy ugyanannyi, mint az előtte álló. Vagyis akkor nem rendezett, ha van olyan elempár, amire ez nem teljesül. Vagyis az eldöntés tételéről van szó: hibát kell keresnünk a sorozatban. Ha csak egyetlen egy helyen hiba van, a keresés megállhat. A mintamegoldás tartalmaz néhány listát, amiben hiba is van; egy vagy több, az elején, és a végén.

    l_jo = [5, 16, 27, 42, 42, 87, 100, 111, 168, 256]

    l_egy_hiba = [5, 16, 42, 27, 42, 87, 100, 111, 168, 256]
    l_tobb_hiba = [5, 27, 42, 16, 42, 111, 100, 256, 168, 87]
    l_elejen_hiba = [16, 5, 27, 42, 42, 87, 100, 111, 168, 256]
    l_vegen_hiba = [5, 16, 27, 42, 42, 87, 100, 111, 256, 168]

    l = l_jo    # melyik listát?

    i = 0
    hibas = False
    while i < len(l)-1 and not hibas:
        if l[i] > l[i+1]:
            hibas = True
        i += 1

    if hibas:
        print("Nem növekvő a lista")
    else:
        print("Növekvő a lista")

## 5. Legnagyobb

Adott az alábbi lista:

    lista = [-25, 12, -54, 8, 77, 98, -29, 35, 3, 71]

Írj ciklust, amely meghatározza, melyik a legnagyobb szám a listában, és írd ki ezt a számot! (Melyik elemeket kell a ciklusnak vizsgálnia? Vigyázat: nem kell az összeset! Ha a listának csak egyetlen eleme van, az egyben maximum is.)

Módosítsd úgy a programot, hogy a ciklusba belépés előtt, és a ciklustörzs végén is kiírod mindig az épp megvizsgált elemet, és a maximum változó értékét! Vizsgáld meg az eredményt, figyeld meg, a maximum változó hogyan változik!

Megoldás

    lista = [-25, 12, -54, 8, 77, 98, -29, 35, 3, 71]

    print("elem", "maximum", sep="\t")

    maximum = lista[0]
    print(lista[0], maximum, sep="\t")

    for i in range(1, len(lista)):
        if lista[i] > maximum:
            maximum = lista[i]
        print(lista[i], maximum, sep="\t")

    print("Legnagyobb:", maximum)

    elem    maximum
    -25     -25
    12      12
    -54     12
    8       12
    77      77
    98      98
    -29     98
    35      98
    3       98
    71      98
    Legnagyobb: 98

## 6. Hol a legkisebb elem?

Írj programot, amely tartalmaz egy tíz elemű listát, az általad megadott kezdeti értékekkel inicializálva! (Tehát nem kell a programnak egyesével beolvasnia azokat a billentyűzetről.) Figyelj arra, hogy az elemek különbözőek legyenek, ez most fontos lesz. Írd ki ezt a listát!

    A lista: 25 69 54 8 77 6 29 10 3 98

Írd át úgy a programot, hogy megjelenjen a listaelemek előtt a listaindex is!

    A lista: [0]=25 [1]=69 [2]=54 [3]=8 [4]=77 [5]=6 [6]=29 [7]=10 [8]=3 [9]=98

Írj programrészt, amely megmondja, melyik a legkisebb szám a listából! Írd ki ezt a számot! (Próbáld ki a programod úgy is, hogy a legkisebb szám a lista legelején és legvégén van!)

    A lista: [0]=25 [1]=69 [2]=54 [3]=8 [4]=77 [5]=6 [6]=29 [7]=10 [8]=3 [9]=98
    A legkisebb szám: 3

Alakítsd át a minimumkeresést úgy, hogy ne csak a legkisebb szám értékét, hanem annak helyét, azaz listabeli indexét is meg tudd mondani! Ehhez szükséged lesz egy minhely változóra, amely azt fogja megjegyezni, hányadik indexen volt a legkisebb szám.

Az igazán jó megoldás az, ha továbbra is egy ciklusod lesz, amelyik ezt a keresést végzi. Tehát nem úgy kell működnie, hogy előbb megjegyzi a legkisebb számot (3), utána pedig újból végigszalad a listán, hogy rájöjjön, hol is volt az (8-as hely). A helyet már a keresés közben is meg lehet jegyezni. A futási eredmény legyen ilyen:

    A lista: [0]=25 [1]=69 [2]=54 [3]=8 [4]=77 [5]=6 [6]=29 [7]=10 [8]=3 [9]=98
    A legkisebb szám: 3
    A legkisebb indexe: 8

Végül pedig írd úgy ki a listát, hogy a legkisebb elem mellé egy jelölést teszel:

    Jelölve: 25 69 54 8 77 6 29 10 3[MIN] 98

Megoldás

    lista = [25, 69, 54, 8, 77, 6, 29, 10, 3, 98]

    # Kiírás
    print("A lista: ", end="")
    i = 0
    while i < len(lista):
        print(lista[i], end=" ")
        i = i+1
    print()

    # Index kiírás
    print("A lista: ", end="")
    i = 0
    while i < len(lista):
        print(f"[{i}]={lista[i]}", end=" ")
        i = i+1
    print()

    # Keresés
    minhely = 0
    i = 1
    while i < len(lista):
        if lista[i] < lista[minhely]:
            minhely = i
        i = i+1
    print("A legkisebb szám:", lista[minhely])
    print("A legkisebb szám indexe:", minhely)

    # Jelölt kiírás
    print("Jelölve: ", end="")
    i = 0
    while i < len(lista):
        print(lista[i], end="")
        if i == minhely:
            print("[MIN]", end="")
        print(" ", end="")
        i = i+1
    print()

## 7. Indexek tárolása

Adott egy valós számokat tartalmazó lista, benne vegyesen mindenféle előjelű számokkal.

    szamok = [2.5, -69, 5.4, -8, -7.7, 6, 2.9, -10, -3, 9.8]

Írj egy olyan programot, amelyik kilistázza a számokat az elemek indexeivel! (Emlékezz vissza, ezt a feladatot egyszer már megoldottad laboron.) Valahogy így:

    Összesen 10 szám van.
    [0] = 2.5
    [1] = -69
    [2] = 5.4
    [3] = -8
    ...

A következő lépés kigyűjteni egy másik listába a negatív listaelemek indexeit. Hozd létre ezt a másik listát, töltsd fel az indexekkel, majd legvégül – ha már kész vagy a lista megépítésével – írd ki ezeket is!

    Ebből 5 szám negatív.
    Indexeik: 1 3 4 7 8

Ha ez is megvan, egy olyan programrészt kell írnod, amelyik az indexek ismeretében kiírja, hogy mik voltak a negatív számok. Fontos, hogy ne keresd meg újra a negatív számokat! Elvégre is, ha az indexeik megvannak, abból már lehet tudni, melyek voltak azok. A végeredmény ilyen formátumú legyen:

    Ebből 5 szám negatív.
    1. [1] = -69
    2. [3] = -8
    3. [4] = -7.7
    ...

Rajzolj ábrát, amely a listákat, az elemekben tárolt számokat, és az azok közötti összefüggéseket ábrázolja!

Megoldás

Az adatszerkezetünk az alábbi:

A `szamok` lista tartalmazza a vizsgálandó valós számokat. Fölötte a lista indexei láthatóak. A `neg_idx` lista az, amelybe a negatív számok indexei kerültek. Hasonlítsuk össze a benne tárolt számokat a fent látható indexekkel! Látszik, hogy a kékkel jelölt elemek sorszámai kerültek az alsó listába.

A `neg_idx` lista önmagában nem túl hasznos, a benne lévő indexek nem mondanak semmit. A `szamok` listával együtt azonban az indexeknek jelentése van: minden index hivatkozik egy negatív számra a fenti listából. Az alsó lista mondanivalója tehát: „a felső lista 1., 3., 4., 7. és 8. indexű eleme kisebb nullánál”. Valóban, `szamok[1]`, `szamok[3]`, `szamok[4]`, `szamok[7]` és `szamok[8]` mind negatívak. Ezek pont a kék elemek.

    szamok = [2.5, -69, 5.4, -8, -7.7, 6, 2.9, -10, -3, 9.8]

    # Listázás
    print(f"Összesen {len(szamok)} szám van.")
    for i in range(0, len(szamok)):
        print(f"[{i}] = {szamok[i]}")   # 1
    print()

    # Negatívak indexeinek kigyűjtése
    neg_idx = []
    for i in range(0, len(szamok)):
        if szamok[i] < 0:
            neg_idx.append(i)

    # Negatívak kiírása
    print(f"Ebből {len(neg_idx)} szám negatív.")
    for i in range(0, len(neg_idx)):
        print(f"{i+1}. [{neg_idx[i]}] = {szamok[neg_idx[i]]}")   # 2

Érdemes összehasonlítani az 1-es és 2-es jelű sorokat. Mindkettő arra hivatott, hogy kiírjon egy indexet és a listaelemet a program kimenetére. De míg az első esetben a teljes listát kiírjuk, a másodikban már csak a negatív számokat. Ilyenkor a kiírandó indexet (sorszámot) is a `neg_idx` listából vesszük, és a `szamok` listát is olyan sorszámmal indexeljük meg, amelyet a `neg_idx` listából vettünk ki.

## 8. Autópálya forgalmi statisztika

Traffipax méri az autópályán az autók sebességét (0–199 km/h). A forgalom elemzése céljából statisztikát szeretnénk készíteni, milyen sebességgel közlekednek az elhaladó autók, 10 km/h bontásban.

Olvasd be a programban üres sorig az autók sebességét, majd írd ki a megadott formátumban a statisztikát! Ügyelj arra, hogy fix méretű tárolóval oldd meg a feladatot, ne jegyezze meg a program a teljes bemeneti adatsort!

Bemenet:

    125
    97
    149
    128
    117
    ...

Kimenet:

    km/h         autó
    0-9          0
    10-19        3
    ...
    120-129      12
    130-139      7

Megoldás

Az adatszerkezet a megszámlálós feladatoknál megismerthez hasonló. Itt is érdemes az előállítandó táblázatból kiindulni (sebességek tartományai → autók száma), és azt vizsgálni, hogy a bejövő adatoktól hogyan lehet eljutni az eredményhez. Az alábbi táblázatot rajzolható ehhez:

listaelem | sebesség (km/h) | autók (db)
--- | --- | ---
auto[0] | 0–9 | 0
auto[1] | 10–19 | 3
...
auto[12] | 120–129 | 12
auto[13] | 130–139 | 7
...

Az egyes sebességtartományokhoz listaelem rendelhető. A 0–9 km/h-val haladó autókhoz a nulladikat, a 10–19 km/h-val haladókhoz az elsőt, és így tovább. A sebességeket nem kell eltárolni: az eltárolandó adat csak az autók száma (hány autó haladt abban a tartományban). A sebesség (km/h) az az adat, ami alapján meg akarjuk találni a számlálót, és amiből a lista indexe egyértelműen következik. Méghozzá 10-zel osztva azt, és véve a hányados az egészrészét. Ez megoldható a `//` egész osztás operátorral is. Az adatelérés módja tehát:

    db = auto[sebesseg // 10]

A feladat megoldása:

    auto = [0] * 20
    be = input("Sebesség? ")
    while be != "":
        idx = int(be) // 10
        auto[idx] += 1
        be = input("Sebesség? ")

    print("km/h\tautó")
    for idx in range(0, 20):
        print(f"{idx*10}–{idx*10 + 9}\t{auto[idx]})

Az eredmények kiírásakor minden sebességtartományhoz egy eredményt kell kiírni, ahogyan a listában is minden tartományhoz egy elem van. Ezért ott egyszerűbb volt visszafelé gondolkozni: a listaindexekre építeni a ciklust, és az index ismeretében meghatározni, hogy az melyik tartományhoz is tartozott. Értelemszerűen ha a sebességből az indexet 10-zel osztással kaptuk, akkor az indexből a sebesség meghatározásához 10-zel szorozni kell azt. Haladhatnánk sebességek szerint is 10-esével:

    for sebesseg in range(0, 200, 10):
        idx = sebesseg // 10
        print(f"{sebesseg}–{sebesseg + 9}\t{auto[idx]})

## 9. Betűk gyakorisága

Szeretnénk megvizsgálni a szavakban előforduló betűk gyakoriságát egy programmal.

A program egy angol nyelvű szöveget kap. A szöveg eleve csupa nagybetűkből áll: „TO BE OR NOT TO BE: THAT IS THE QUESTION.” Ehhez kell statisztikát készíteni, hogy melyik betű hányszor fordult elő a szövegben, és az az összes betű hány százalékát adja. A kimenet legyen ehhez hasonló:

    A:  1 db,   3.33%
    B:  2 db,   6.67%
    E:  4 db,  13.33%
    ...

Ha valamelyik betű nem szerepelt a szövegben, az ne jelenjen meg a statisztikában se! A nem betű karaktereket figyelmen kívül kell hagyni.

Milyen adatszerkezet kell az adatok tárolásához? Rajzold le a program megírása előtt!

Tipp – adatszerkezet

Ez nagyon hasonló az előadáson szereplő válogatós feladatokhoz. Az `A` betűhöz tartozik majd az első számláló, a `B` betűhöz a második, és így tovább. Összesen 26 betű van az angol ábécében.

Tipp – karakterek

Emlékezz vissza: az `ord()` függvénnyel tudod lekérdezni egy karakter kódját, a `chr()` függvénnyel pedig egy betűt tudsz meghatározni, ha a karakterkódot ismered. Például `ord('A')` értéke `65`, és `chr(65)` értéke `'A'`. Akár ciklust is tudsz csinálni, végig az ábécén, ha az `A` kódjától a `Z` kódjáig haladsz. Az angol ábécében hosszát is ki tudod számolni, ha karakterkódokat kivonsz egymásból.

Megoldás

    szoveg = "TO BE OR NOT TO BE: THAT IS THE QUESTION."

    szamlalok = [0] * (ord('Z') - ord('A') + 1)

    for c in szoveg:
        kod = ord(c)
        if kod >= ord('A') and kod <= ord('Z'):
            szamlalok[kod - ord('A')] += 1

    osszes = sum(szamlalok)

    for idx in range(0, len(szamlalok)):
        c = chr(idx + ord('A'))
        db = szamlalok[idx]
        arany = db / osszes
        if db != 0:
            print(f"{c}: {db:2} db, {arany * 100:6.2f}%")

## 10. Torpedó

Írj programot, ami létrehoz egy 10x10-es Torpedó pályát és véletlenszerűen elhelyez rajta egy 4 hosszúságú anyahajót. A pályát egy kétdimenziós listában tárold, a hajó legyen '#', a tenger pedig a szóköz karakter. A hajó iránya (függőleges vagy vízszintes) szintén legyen véletlenszerű! Rajzold ki a pályát!

Tipp – a hajó véletlenszerű elhelyezése
A hajó baloldali koordinátáit generáljuk véletlenszámokkal. Vízszintes elhelyezés esetén a sor 0..9, az oszlop viszont csak 0..5 között lehet, mert különben a négy hosszúságú hajó kilógna a pályáról. A függőleges esetet pedig úgy kapjuk, hogy a koordinátákat egyszerűen felcseréljük.
Megoldás

    import random

    # pálya készítés, 10x10 kétdimenziós lista
    torpedo= []
    for _ in range(10):
        torpedo.append([' '] * 10)

    # négyes hajó elhelyezése
    k1= random.randrange(10)
    k2= random.randrange(7)  # 0..6, hogy elférjen a négyes hajó
    fuggoleges= random.randrange(2) == 0

    for i in range(k2, k2+4):
        if fuggoleges:
            torpedo[i][k1] = '#'
        else:
            torpedo[k1][i] = '#'

    # kirajzolas
    print(' '*3, end='')
    # ez egy picit már túlzás, de gyakorlásképp ciklussal
    for i in range(10):
        print(chr(ord('A')+i), end='')
    print('\n  ' + '-' * 12)
    for i in range(10):
        print(f"{i+1:>2}|", end='') # igazítjuk a számokat
        for j in range(10):
            print(torpedo[i][j], end='')
        print('|')
    print('  ' + '-' * 12)