# Adatszerkezetek

Czirkos Zoltán, Ress Sándor · 2025.09.30.

Sztringek formázása, f-string, .format() függvény. Az adatszerkezet fogalma. Referenciák fogalma. Listák két dimenzióban.

# Formázott kimenet

## 2. Kiírás: a problémák

Néhány zűrzavaros `print()` utasítás:

    print("A szó " + str(i) + ". betűje: " + szo[i] + ".")
    print(x * y, end="\t")

Lássuk, mik a problémák! Például a sorszámot jelző `.` elé nem szerettünk volna szóközt tenni, ezért az `i` indexet sztringgé alakítottuk az `str()` segítségével, és összefűztük. De jó lett volna az is, ha a `print()`-nek azt mondjuk, ne tegyen semmit a kiírt adatok közé, szóközt se:

    print("A szó ", str(i), ". betűje: ", szo[i], ".", sep="")

Ez talán kicsit olvashatóbb, de még mindig nehéz érteni.

A régebbi előadásról származó szorzótáblánk se volt túl szép. A számjegyeket szerettük volna a szorzótáblában egymás alá rendezni, de ez sajnos a tabulátorral nem megy. Nincsenek a helyiértékek egymás alatt:

    1       2       3       4
    2       4       6       8
    3       6       9       12
    4       8       12      16
    5       10      15      20
    ...

Összefoglalva, a `print()`-et bizonyos esetekben:

- Nehéz átlátni.
- A kiírást nehéz formázni.

Hogy lehetne használhatóbbá és áttekinthetőbbé tenni a kimenet formázását?

## 3. Az f string: sztringek formázása

### A formázó működése

    formazott= f"A szó {i}. betűje: {szo[i]}"

- A sztringek elé egy 'f' betű kerül
- A kapcsos zárójelek `{}` helyére helyettesíti be az adatot
- Az adat tetszőleges kiértékelhető Python kifejezés lehet
- Python 3.6 verzió felett használható (2016. december)

### Használata

    szo="Barack"

    for i in range(len(szo)):
        print( f"A szó {i}. betűje: {szo[i]}")

Nem törvényszerű, de legtöbbször az így leírt kifejezés eredményét (amely egy sztring) rögtön a `print()`-nek adjuk.

## 4. Miért pont {}? – módosítók

### Módosítók

    gyumolcs="körte"
    print(f"|{'alma':<12}|")
    print(f"|{gyumolcs:>12}|")
    print(f"|{math.pi:12.5}|")
    print(f"|{math.pi/2.0:12.5e}|")

    |alma        |
    |       körte|
    |      3.1416|
    | 1.57080e+00|

A kettőspont után pedig formázási módosítók adhatóak meg. Például:

- Egy számmal megadhatjuk a kiírás szélességét (hány karakter széles legyen egy oszlop).
- A kacsacsőrökkel azt adhatjuk meg, merre igazítsa az oszlopot: < balra vagy > jobbra. Van egyébként = is, az középre teszi.
- Számok esetén egy pont után megadhatjuk a tizedesjegyek számát is, illetve a megjelenítés módját: e = exponenciális (tudományos) alak, f = fix alak (mindig ugyanannyi tizedesjegy).

A fenti példák csak a legfontosabbakat mutatják be. Érdemes az alapokat fejből tudni, de jóval többet is tud ennél. A mini nyelvéről itt lehet többet olvasni: Format Specification Mini-Language.

## 5. A szorzótábla még egyszer

A szorzótábla javított megoldása:

    y = 1
    while y <= 5:
        x = 1
        while x <= 5:
            print(f"{x*y:3}", end="")
            x+=1
        print()
        y+=1

Ebben a számok egymás alatt vannak, és a kiírás oszlopai sem szükségtelenül szélesek már.

Gondban csak akkor vagyunk, ha túl nagy szorzótáblát szeretnénk. Ha a `10×10`-es változatot jelenítenénk meg, akkor a 3 karakter szélességű kiírás már kevés, mert 10×10 = 100, amihez kell 3 karakter. Legjobb lenne a kiírás szélességét a legnagyobb számhoz igazítani. Ezt így tehetjük meg:

    maxx = 10
    maxy = 10
    maxszel = len(str(maxx * maxy))+1

    for y in range(1, maxy+1):
        for x in range(1, maxx+1):
            print(f"{x*y:{maxszel}}", end="")
        print()

Az ötlet lényege a következő. Tudjuk, hogy a legnagyobb szám a jobb alsó sarokban lesz, és az értéke `maxx * maxy`. Amennyi hely ehhez kell, annyi hely elegendő lesz az összes oszlophoz. A `maxszel` sorban kiszámítjuk ezt a szorzatot, sztringgé alakítjuk, és megvizsgáljuk a hosszát.

A kiírásnál az összes sort ilyen szélességűre kell méretezni, és persze szükség van még egy szóközre is minden szám előtt, így eggyel nagyobb értéket veszünk. A `while` ciklust pedig `for` ciklussá alakítottuk.

## 6. Régebben: str.format(): sztringek formázása

### A formázó működése

    minta = "A szó {}. betűje: {}"
    eredmeny = minta.format(i, szo[i])

- A sztringek `.format()` függvénye végzi
- Bármennyi paramétert kaphat
- A kapcsos zárójelek `{}` helyére helyettesíti be az adatot

### Használata

    szo = "barack"

    for i in range(0, len(szo)):
        print("A szó {}. betűje: {}".format(i+1, szo[i]))

Általában egy sorba írjuk, `"...".format(...)` módon. Bár ez nem törvényszerű, de legtöbbször az így leírt kifejezés eredményét (amely egy sztring) rögtön a `print()`-nek adjuk.

## 7. Említésképp: oldschool formázás a % operátorral

### Általános forma

    eredmeny = "minta" % (adat1, adat2, ...)

Régebbi Python verziókban a formázást a `%` operátorral lehetett elvégezni. Bal oldalon a mintát megadó sztring (lásd lentebb), jobb oldalon pedig zárójelben a behelyettesítendő adatok.

### Példák

    print("%s %d éves." % ("Ernőke", 4))
    print("|%8.4f|" % math.pi)

    Ernőke 4 éves.
    |  3.1416|

Az adatokat az egyes százalékjellel megjelölt helyre helyettesítette be. A százalékjel után opcionálisan szélességet lehetett megadni, végül pedig egy karakter következett, amely a típust reprezentálta. Sztringek esetén ez `s`, egész számoknál `d` („decimal”, mert tízes számrendszerben íródtak ki), valósaknál pedig `f` („floating point”).

Ezt a módszert a C nyelvtől örökölte meg a Python. Manapság, új programokat írva már nem használjuk. Azért érdemes tudni róla, mert régebben írt programokban elég gyakran előfordul.

# Adatszerkezetek

## 9. Példa: dolgozat pontszámainak eloszlása

Feladat: egy évfolyam kis ZH-iról szeretnénk statisztikát készíteni. A dolgozatok 0–10 pontosak lehetnek. A kérdésünk, hogy melyik pontszámból hány darab lett.

Bemenet:

    5
    7
    10
    9
    10
    ...

Kimenet:

     0 p     1 db
     1 p     7 db
     2 p     3 db
    ...
     9 p    34 db
    10 p    17 db

## 10. Hány dolgozat – nem túl jó megoldás

Egy nem túl jó megoldás a következő:

Nem túl jó így,
ne tanuld meg

    # pontok beolvasása
    pontok = []
    be = input("Pont? ")
    while be != "":
        pontok.append(int(be))
        be = input("Pont? ")

    # 0–10-ig megszámoljuk mindig
    for keresett in range(0, 10+1):
        db = 0
        for pont in pontok:
            if pont == keresett:
                db += 1
        print(f"{keresett:2} p, {db:2}")

Miért mondjuk azt, hogy ez nem túl jó megoldás? Egyrészt felesleges eltárolni az összes pontszámot. Mint azt később látni fogjuk, nincsen rá szükség. Másrészt pedig érezzük, hogy a megszámlálásokból túl sok van. 11-féle pontszám lehetséges (nullától tízig), és a programunk 11-szer megy végig a listán, újra és újra mindig egy másik pontszámot keresve. Így alakul ki végül a táblázat, ami a kimenetre kerül. De tényleg ehhez végig kell menni 11-szer? Nem lehetne valahogyan előre meghatározni ezt a táblázatot, egy lépésben?

## 11. Hány nulla pontos dolgozat lett?

Lássunk egy egyszerűbb kérdést: hány nulla pontos dolgozat lett?

Ehhez a megszámlálás tételét alkalmazzuk a szokásos módon.

    db = 0
    for pont in pontok:
        if pont == 0:
            db += 1
    print(f"0 p, {db:2} db")

Vegyük észre: több számlálóval több pontszámot is kiválogathatnánk.

    db0 = 0
    db1 = 0
    db2 = 0
    # ...
    for pont in pontok:
        if pont == 0:
            db0 += 1
        if pont == 1:
            db1 += 1
        if pont == 2:
            db2 += 1
        # ...
    print(f"0 p, {db0:2} db")
    print(f"1 p, {db1:2} db")
    print(f"2 p, {db2:2} db")
    # ...

Ezzel lényegében ugyanazt csináltuk a beolvasott pontokkal, mint az előző válogatásnál. Most egy számláló helyett összesen tizenegy darab van (képzeljük oda a többit). A lista bejárása közben 0 pontos dolgozatot látva `db0`-t növeljük meg, 1 pontos dolgozatot látva `db1`-et, és így tovább. Az eredmény kiírása hasonlóképp történik, felsoroljuk az összes pontszámot, és kiírjuk a hozzájuk tartozó számlálót.

Kérdés, mi lesz ezzel a sormintával. Ez így biztosan nem jó, az már a kipontozásból is látszik. Száz pontos dolgozat esetén 100 számlálót hoznánk létre, 100 `if` elágazással, 100 `print()` kiírással? Kell lennie jobb megoldásnak.

## 12. Tizenegy számláló egy listában

### Adatszerkezet: definíció

Az adataink strukturális elrendezése a programban.

### Az adatszerkezet

Tizenegy számlálót kell használni. Legyen egy listánk:

db[0] | db[1] | db[2] | ... | db[10]
--- | --- | --- | --- | ---
3 | 9 | 4 | ... | 17

Az ötlet a következő. A számlálók tárolásához ne tizenegy, egymástól független változót használjunk. Legyen inkább helyettük egyetlen egy lista, amelyik a számlálókat tartalmazza.

### Az adatok elérése

Ez a lista lesz a programunkban az adatszerkezet, amelyben a számunkra lényeges információkat tároljuk. Az adatszerkezetek tervezésekor azt is végig kell gondolni, hogy az adatot hogyan érjük el. Jelen esetben egyszerű a dolgunk: a nulladik számláló a lista nulladik eleme (0. indexű), az első számláló a lista első eleme, és így tovább.

    db[0] += 1      # 0 pontos
    db[2] += 1      # 2 pontos

    db[pont] += 1   # általában: indirekt adatelérés

Vagyis mindig éppen annyiadik indexű számlálóval, azaz listaelemmel dolgozunk, ahány pontos dolgozatot épp találtunk. Ezt fogalmazza meg általánosságban a `db[pont] += 1` sor, ahol a `db` lista tartalmazza a számlálókat, a `pont` változó pedig a dolgozat eredményét 0 és 10 között.

## 13. Hány dolgozat – a majdnem jó megoldás

Már majdnem jó,
de még mindig
nem a végleges

    # pontok beolvasása
    pontok = []
    be = input("Pont? ")
    while be != "":
        pontok.append(int(be))
        be = input("Pont? ")

    # válogatás
    db = [0] * 11
    for pont in pontok:
        db[pont] += 1   # indirekt adatelérés

    # eredmény
    for pont in range(0, 10+1):
        print(f"{pont:2} p, {db[pont]:2} db")

Észre kell venni itt egy nagyon fontos dolgot. A `pont` nevű változó a dolgozatok megszámlálása közben nem ciklusváltozó. Vagyis a listát nem ciklusváltozóval indexeljük, nem járjuk be. Ehelyett a lista indexe tulajdonképp a bejövő adat az algoritmusban, amit a felhasználó gépelt be. Ezért nevezzük ezt indirekt adatelérésnek vagy indirekt szabálynak. A program megírásakor nem is tudjuk, milyen sorrendben lesznek elérve a lista elemei; ez teljes mértékben attól függ, hogy futás közben milyen bemenő adatokat kap a program.

Tulajdonképp ez a legfontosabb gondolat és kódsor a programban. A `db[pont]` kifejezés egyébként az eredményt kiíró programrésznél is szerepel. Ott ugyanez a célunk: a pontszámhoz tartozó számláló kiolvasása a listából. Csak itt a pontszámot a program határozza meg, mert fel kell sorolni az összeset, nullától tízig mindegyikhez kiírni a darabszámot.

Már csak egy dolgot kell észrevennünk: a `pontok` nevű listára, amibe kezdetben tettük a billentyűzetről beolvasott adatokat, egyáltalán nincsen szükségünk. Emlékezzünk vissza a megszámlálás tételére: a számláló növelése után a vizsgált adatot eldobhatjuk, felesleges már megtartani. Itt is ugyanezt tehetnénk: a billentyűzetről beolvasott adatot egyből felhasználhatnánk valamelyik számláló növeléséhez.

## 14. Hány dolgozat – a végleges megoldás

A legjobb megoldás, amely már a billentyűzetről beolvasás közben megnöveli a számlálókat, így fest:

Végleges verzió,
legjobb megoldás

    # pontok beolvasása és válogatás
    db = [0] * 11
    be = input("Pont? ")
    while be != "":
        pont = int(be)
        db[pont] += 1   # indirekt adatelérés
        be = input("Pont? ")

    # eredmény
    for pont in range(0, 10+1):
        print(f"{pont:2} p, {db[pont]:2} db")

Miért jobb ez az új verzió? Egyrészt mert sokkal rövidebb, egyszerűbb. Másrészt pedig mert sokkal kevesebb memóriát foglal futás közben. Bárhány dolgozatot is kell feldolgozni, a program által használt lista mindig csak 11 elemű; és ez teljesen független a feldolgozandó adatok mennyiségétől.

## 15. Ládarendezés – az algoritmus

A ládarendezés (leszámláló rendezés) nem hasonlítja össze az egyes elemeket egymással, hanem nagyságuk szerint csoportosítja őket. Lássuk a legegyszerűbb esetet, rendezzünk egy listát egész számokkal!

A rendezendő lista:

5 4 8 4 0 6 4 8 9

Ebben a listában 0 és 9 között vannak számok. Fogunk egy másik listát, amelyben leszámláljuk, hogy melyikből hány darab szerepel:

A számlálás eredménye:

0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
--- | --- | --- | --- | --- | --- | --- | --- | --- | ---
1 | 0 | 0 | 0 | 3 | 1 | 1 | 0 | 2 | 1

Ebből az információból egy új lista állítható elő, amelyik rendezett lesz. Nem kell hozzá mást tenni, mint 1 db 0-st, 3 db 4-est, 1 db 5-öst, 1 db 6-ost, 2 db 8-ast és 1 db 9-est tenni bele:

A rendezett lista:

0 4 4 4 5 6 8 8 9

## 16. Ládarendezés – legkisebb és legnagyobb

Lássunk egy újabb példát!

A rendezendő lista:

8 6 9 6 6 9 6 8 9

A ládarendezéshez használható adatszerkezet az előzőek alapján könnyen kigondolható. Megint egy olyan listára lesz szükségünk, amelyik számlálókat tartalmaz: az eredeti számokhoz kell ezeket hozzárendelnünk, hogy meg tudjuk mondani, melyikből hány darab szerepelt. Ha találunk egy 4-est, akkor a 4-esekhez tartozó számlálót növeljük. Ha 8-as jön, akkor a 8-asokhoz tartozó számlálót.

A ládarendezés akkor tud jól működni, ha kevésféle szám szerepel a sorba rendezendő tömbben, hiszen annyi számláló kell, ahányféle szám van ott. Ha az eredeti lista nullától kezdődően tartalmaz kicsi egész számokat, akkor könnyű a dolgunk, hiszen a listák 0-tól indexelődnek. Ha nagyobb számok vannak benne, akkor viszont így a számlálók listájának az „alját” nem fogjuk használni semmire:

Melyik részét használjuk a listának?

0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
--- | --- | --- | --- | --- | --- | --- | --- | --- | ---
0 | 0 | 0 | 0 | 0 | 0 | 4 | 0 | 2 | 3

A fenti listának a hasznos része a 6-tól 9-ig terjedő szakasz. Legjobb ötlet ezért, ha megnézzük, hogy melyik a legkisebb és a legnagyobb szám a listában, és ehhez a tartományhoz hozunk létre számlálókat. Közben pedig reménykedünk abban, hogy nem túl nagy a tartomány, nem túl kevésféle szám van benne, mert akkor nagyon sok üres, nem használt számlálónk lesz, mint amilyen most a 7-es is. (Ez egyszerűen a ládarendezésnek egy tulajdonsága, amit ismerni kell – tudjuk, mikor érdemes használni és mikor nem.)

A javított adatszerkezetünk:

db[0] | db[1] | db[2] | db[3]
--- | --- | --- | ---
4 | 0 | 2 | 3
`db[szám - legkisebb]`

Ezek szerint egy adott számhoz tartozó számlálót a `db[szám - legkisebb]` indexeléssel fogjuk tudni elérni.

## 17. Ládarendezés – kódban

A minimum és a maximum megkeresését mi is lekódolhatjuk, de egyszerűbb a `min()` és a `max()` függvényt használni. A számlálók listájának mérete `legnagyobb - legkisebb + 1`, mert a tartomány mindkét vége előfordul.

    eredeti = [61, 73, 16, 51, 62, 51, 71, 14, 13, 13, 55, 13, 7, 45, 61]
    legkisebb = min(eredeti)    # 7
    legnagyobb = max(eredeti)       # 73
    darab = [0] * (legnagyobb - legkisebb + 1)
    for szam in eredeti:            # 61, 73, 16, ...
        darab[szam - legkisebb] += 1
    rendezett = []
    for szam in range(legkisebb, legnagyobb + 1):
        hanyszor = darab[szam - legkisebb]
        rendezett.extend([szam] * hanyszor)
    print(rendezett)

A rendezett lista előállítását így is írhatnánk:

    for i in range(len(darab)): # a 0. index a legkisebbhez tartozik
        rendezett.extend([i+legkisebb] * darab[i])

    [7, 13, 13, 13, 14, 16, 45, 51, 51, 55, 61, 61, 62, 71, 73]

A kód többi része az adatszerkezet megértése után magától értetődő. Az `.extend()` függvény egyébként a lista `.append()` függvényéhez hasonló, de nem csak egyetlen új elemet fűz hozzá egy listához, hanem egy másik lista összes elemét. Például a számlálás után tudjuk, hogy `3` darab `13`-as szám volt az eredeti listában, ezért a rendezett listát kiegészítjük (extend) `[13] * 3`-mal, azaz `[13, 13, 13]`-mal.

## 18. Eratoszthenész szitája

### A szita: többszörösök kihúzása

Eratoszthenész szitája prímszámokat keres. A módszer a következő. Felírjuk a számokat valameddig. 2 prímszám, ezt megjegyezzük. Kihúzzuk a többszöröseit, mivel azok nem prímszámok. Ezután 3 a következő, ami még nincs kihúzva. Az is prímszám, mivel nem találtunk ezidáig osztót hozzá: a nála kisebb összes szám többszöröseit kihúztuk, nála nagyobb osztója pedig nem lehet. A többszörösei viszont nem prímek: kihúzzuk az összes 3-mal oszthatót. 4-et már kihúztuk (2×2). 5 a következő prím, kihúzzuk n×5-öt stb.

1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10
11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20
21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30
31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40
41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50

Írjuk ki ezek alapján a prímszámokat 999-ig! Az algoritmus adott, az adattárolás módját kell csak meghatározni: hogyan tárolható el az, hogy ki lett-e húzva már egy szám, vagy nem? Minden számhoz tartozóan egy igaz/hamis értéket kell tárolni.

### Az adatszerkezet

Egy tömbre, azaz fix méretű listára van szükség. A lista elemei itt logikai értékek, nem pedig számok. A listát pedig mindig magával a számmal indexeljük; `prim[2]` pl. azt tárolja, hogy a 2 prímszám-e. Az első két elemet így ugyan nem használjuk, de a program egyszerűbb, mert az index megegyezik magával a számmal. Az 1000 méretű listában így 999-ig lehet megkeresni a prímeket.

Az algoritmus futása után tehát a listánk így néz ki:

0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | ...
--- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | ---
i | i | i | i | h | i | h | i | h | h | h | i | h | i | ...

Az első két helyen (0, 1 indexű elemek) az igaz érték változatlan maradt; a 4, 6, 8, 9, … helyekre pedig az algoritmus hamis értékeket tett, mert nem prímszámok. Lényegében a lista első két elemét nem használjuk semmire; azért, hogy az index mindig pontosan megegyezzen a vizsgált számmal: `lista[szám]`. Eltolhatnánk ezt 2-vel, hogy ne vesszen kárba ez a két listaelem, de az 1000 elemhez képest nincs ennek jelentősége. Ezért inkább elpazaroljuk azokat, hogy egyszerűbb legyen a programunk.

## 19. Eratoszthenész szitája – kódban

    # 1000 elemű, True-kból álló lista
    prim = [True] * 1000

    # Prímek keresése
    for sz in range(2, 1000):
        if prim[sz]:
            for t in range(sz * 2, 1000, sz):
                prim[t] = False

    # Kiírás
    for sz in range(2, 1000):
        if prim[sz]:
            print(sz, end=" ")
    print()

Az algoritmus így egy csupa `True`-kból álló listával indul; és a megtalált prímszámok többszöröseihez `False` értéket ír. Ahol `True` maradt, azok a prímszámok. A `t`-vel jelölt számok a többszörösök. Az ott megadott tartomány, a `range(sz * 2, 1000, sz)` jelentése: `sz * 2`-től indulva, `1000`-ig, mindig `sz`-et ugorva. Ugyanez `while` ciklussal így nézne ki:

            t = sz * 2
            while t < 1000:
                prim[t] = False
                t += sz

A külső ciklust egyébként elég lenne a táblázat méretének gyökéig futtatni, mert az afölötti osztóknak azalatti párja is van (pl. 1000-nél 2×500, 4×250 és így tovább).

## 20. Kis kitérő: az álvéletlenszámok

Feladat: két kockával dobás összegét vizsgáljuk. Melyik összeg, milyen gyakran fordul elő?

A következő programban azt fogjuk megvizsgálni, hogy két dobókockával dobva, a két kockán látható számok összegének milyen eloszlása van. Az egy kockával dobással ellentétben ennél nem egyenletesen jön ki mindegyik összeg. A kockadobások szimulálásához véletlenszámokat fogunk használni.

A programok lényege, hogy determinisztikusak. Kérdés: akkor honnan lesznek véletlenszámaink?

A determinisztikusság azt jelenti, hogy egy adott programot ugyanazzal a bemenettel futtatva mindig ugyanazt a kimenetet kapjuk. A legtöbb esetben ez természetesnek tűnik, éppen ezt a megbízhatóságot várjuk a számítógéptől. Azonban bizonyos alkalmazásoknál ez korlátot jelent. Elképzelhetjük, elég unalmas lenne egy olyan kártyajáték, amelyben mindig ugyanazt a leosztást kapjuk. Mégis ha a számítógép determinisztikus természetű, hogyan lehetne olyan programot írni, amelynél nem minden futásnál ugyanaz az eredmény? Hogyan tudunk a programból feldobni egy pénzt, fej vagy írás, vagy kockával egy 1 és 6 közötti számot dobni?

A megoldás egy álvéletlenszám-generátor (vagy más néven: pszeudovéletlenszám-generátor) alkalmazása. Ez egy olyan matematikai műveletsort jelent, amelynek az eredménye egy összevisszának tűnő számsor. Annyira összevisszának, hogy az már véletlenszerűnek fogadjuk el. Ha pl. az `x = (5*x+1)%16` kifejezést újra és újra kiértékeljük, az `x` változó a 1, 6, 15, 12, 13, 2, 11, 8, 9, 14, 7, 4, 5, 10, 3, 0, … értékeket veszi fel, amelyben nem nagyon látunk szabályosságot. Ha tovább folytatjuk, akkor persze igen, mert a számsor elkezd ismétlődni.

A Python nyelv `random` modulja a fentihez hasonló, de bonyolultabb módon előállított álvéletlenszámokat ad. Adott tartományban lévő egész számot legegyszerűbben a `random.randint()` függvénnyel állíthatunk elő. Ha például azt nézzük, hogy az előállított véletlenszám 0 vagy 1, pénzfeldobást imitálhatunk:

    import random

    if random.randint(0, 1) == 0:
        print("fej")
    else:
        print("írás")

Kockadobáshoz pedig a `random.randint(1, 6)`-ot használhatjuk:

    import random

    for i in range(10):
        print(random.randint(1, 6), end=" ")

Fontos, hogy az álvéletlenszámok determinisztikusak, hiszen csak egy matematikai műveletsor eredményeként állnak elő. Ez lehetővé teszi azt, hogy többször is előállítsuk ugyanazt a „véletlen” számsort. Például egy kártyajátékban ez hasznos lehet, mert meg tudjuk ismételni ugyanazt a leosztást. Vagy egy szimulációban, ahol egy kísérletet el szeretnénk végezni újra.

A véletlenszámgenerátor belső állapota a `.seed()` függvényével módosítható. Ez egy egész számot kaphat, amit kiindulási értéknek használ. Próbáld ki a lenti programot: akárhányszor indítod, mindig ugyanaz lesz a kockadobások eredménye. De ha más a seed értéke, akkor újabb számsor jön:

    import random

    random.seed(12345)
    i = 0
    while i < 10:
        print(random.randint(1, 6), end=" ")
        i += 1

A `random` modul egyébként sok egyéb függvényt tartalmaz, amikről itt lehet olvasni: Generate pseudo-random numbers. Lehet valós számokat is generálni véletlenszerűen. Vagy egy listából választani véletlenszerűen egy elemet a `random.choice(lista)` függvénnyel, esetleg megkeverni azt a `random.shuffle(lista)` függvénnyel.

## 21. Kockadobások: az adatszerkezet

Térjünk vissza a feladathoz, a kockadobások összegzéséhez! Azt kell vizsgálnunk, két kockával dobva milyen gyakorisággal állnak elő a lehetséges összegek.

### Ezt szeretnénk eltárolni

A kockadobások lehetséges összegei `1+1 = 2` és `6+6 = 12` között lesznek. Minden összeghez rendelünk egy számlálót; a dobás után az adott számlálóhoz húzunk egy strigulát.

dobás | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12
--- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | ---
hányszor | | | | | ||| | ||| | |||| | ||||| | || | ||| | | | || | |

### Így jelenik meg a programban

Az összegek közül a legkisebb az 2, a legnagyobb a 12. Ezért a gyakoriságokat tároló lista `12-2+1 = 11` elemű kell legyen. Ennek a listának az indexei a 0…10 tartományban lesznek, ezért a dobások összegéből 2-t le kell vonni: `2…12 - 2 = 0…10`, úgy kapjuk az adott dobás gyakoriságát tároló listaelem indexét.

d0 | d1 | d2 | d3 | d4 | d5 | d6 | d7 | d8 | d9 | d10
--- | --- | --- | --- | --- | --- | --- | --- | --- | --- | ---
1 | 1 | 3 | 3 | 4 | 5 | 2 | 3 | 1 | 2 | 1
`d[összeg - 2]` → számláló az adott összeghez

## 22. Kockadobások összege

Alább látható a programrészlet, amely elvégzi a kísérletet.

    import random

    dobas = [0] * (12-2+1)

    for i in range(1000):
        kocka1 = random.randint(1, 6)
        kocka2 = random.randint(1, 6)
        osszeg = kocka1 + kocka2
        dobas[osszeg - 2] += 1  # 2-12 → 0-10

    for osszeg in range(2, 12+1):
        print(f"k1+k2 = {osszeg}, {dobas[osszeg-2]} alkalom")

A programban a számlálókat kezdetben nullázzuk; egész pontosan, létrehozzuk azt a listát, ami csupa nullákat tartalmaz. Ennek elemszáma 11, de azt egyszerűbb `12-2+1` formában beírni a programba, így emlékeztetjük magunkat, hogy jött ki.

Az adatszerkezet működése, nevezetesen, hogy egy adott összeghez az `összeg - 2` indexű listaelem tartozik, legjobban a felkiáltójellel jelölt sorban látszik.

Fontos megérteni a fenti `dobas[osszeg-2] += 1` sor működését is. A lényeg itt, hogy az összeg ismeretében az adatszerkezetben azonnal meg tudjuk találni a számlálót, amit növelnünk kell eggyel. Ezen a helyen nem lineárisan haladunk végig a listán, sőt végig sem kell haladni rajta, nem kell megkeresni a számlálót: csak megindexeljük a listát `osszeg - 2`-vel, és meg is van a „keresett” elem. Véletlenszerű sorrendben érjük el az adatokat. Most szó szerint véve is, hiszen az indexet véletlenszámgenerátortól kaptuk. De a listáknak ezt a tulajdonságát, nevezetesen, hogy bármikor, bármelyik elemet azonnal el tudjuk érni, véletlenszerű adatelérésnek nevezzük (random access).

Vegyük észre azt is, hogy a jól megválasztott adatszerkezet miatt a kísérletek eredményét – a dobott számokat – nem kell eltárolni. Ezt a megszámlálás tételéből is tudjuk, és a szempontunkból most lényegtelen, hogy nem egy számláló van, hanem tizenegy. Ha eltárolnánk az adatokat, egyre nagyobbra kellene nyújtani a listát attól függően, hogy hány kísérletet végzünk. De azokra az adatokra nincs szükségünk, csak a gyakoriságra, ezért elegendő a fix méretű lista (tömb) is.

Látványosabb programot kapunk, ha egy egyszerű trükkel grafikusan jelenítjük meg az eredményt. Ebben a dobások számát elosztjuk 10-zel; méghozzá egész osztással, a `//` operátorral – ennél pl. 23//10 = 2, a törtrészt eldobja. Utána pedig az `"X"` sztringet sokszorozzuk meg, hogy sok X betű legyen egymás mellett.

    import random

    dobas = [0] * (12-2+1)

    for i in range(1000):
        kocka1 = random.randint(1, 6)
        kocka2 = random.randint(1, 6)
        osszeg = kocka1 + kocka2
        dobas[osszeg - 2] += 1

    for osszeg in range(2, 12+1):
        x = "X" * (dobas[osszeg-2] // 10)
        print(f"{osszeg:2} {x}")

    2    XX
    3    XXXXX
    4    XXXXXXX
    5    XXXXXXXXXX
    6    XXXXXXXXXXXXX
    7    XXXXXXXXXXXXXXXXXX
    8    XXXXXXXXXXXXXX
    9    XXXXXXXXXXXX
    10   XXXXXXX
    11   XXXXX
    12   XX

# Referenciák

## 24. Mi történik itt?!

Futtassuk le az alábbi programokat! Mit fognak kiírni?

    a = 3
    b = a

    a += 1

    print("a =", a)
    print("b =", b)

    a = [1, 2, 3]
    b = a

    a.append(4)

    print("a =", a)
    print("b =", b)

Megoldás

    a = 4
    b = 3

    a = [1, 2, 3, 4]
    b = [1, 2, 3, 4]

Az első kódban azt mondjuk, hogy `a` értéke legyen 3, és `b` értéke legyen ugyanannyi, mint `a`-é, vagyis az is 3. Ezután `a`-t megnöveljük, ezért az 4 lesz, `b` pedig 3 marad – miért is változna.

A második kódrészletben hasonló dolgot csinálunk. Az `a` legyen egy lista, az 1, 2, 3 számokkal. Ezek után `b` legyen ugyanez. Az `a`-hoz hozzáfűzünk egy új számot, a 4-et– és hopp, a `b` is megváltozott.

Hogy lehet ez, mi ennek az oka? Miért van az, hogy amikor számokkal dolgozunk, akkor a két változó függetlennek tűnik, ha pedig listával, akkor nem?

## 25. A probléma megértéséhez: listák másolása

Említettük a múltkori előadáson, hogy értékadással a lista nem másolható le. Elevenítsük fel ezt a problémát!

### Csak a hivatkozás másolódik

    a = [1, 2, 3]
    b = a       # !

    b.append(4)
    print(a)    # [1, 2, 3, 4]

Ebben a kódban létrehozunk egy listát. A `b = a` értékadásnál nem jön létre új lista, hanem csak egy hivatkozást állítunk be. Vagyis innentől kezdve egy listánk van, és ahhoz két név tartozik. Akár az `a`, akár a `b` nevet használjuk, ugyanarról a listáról beszélünk. Ha az egyiket módosítjuk, akkor a másik is látszólag módosul, de ez azért van, mert valójában nincs „egyik” és „másik”: egyetlen egy listánk van.

### A lista másolódik

    x = [1, 2, 3]
    y = list(x) # !

    y.append(4)
    print(x)    # [1, 2, 3]

Itt viszont két listánk lesz. Az első a szokásos módon létrejön, az `x` változónéven keresztül érhető el. Az `y` változót pedig úgy inicializáljuk, hogy meghívjuk a `list()` függvényt: ez új listát hoz létre, amelybe átmásolja a paraméterként kapott listában található elemeket. A lényeg, hogy így létrejön egy másik lista. Tehát most két változónk van, de listából is kettő van. Ha az `y` változón keresztül látott listát módosítjuk, akkor az `x`-en keresztül látott nem módosul, mert az az eredetitől független.

## 26. A referenciák fogalma

Ezek szerint tehát itt egy darab lista van és két darab változó. Vizsgáljuk meg újra az értékadásokat!

A listát, mint memóriában tárolt adatot, objektumnak (object) nevezzük. A lista objektumot a szögletes zárójelekkel `[]` hoztuk létre, és itt az `append()` függvénnyel módosítjuk.

Az objektumra hivatkozhatunk, ahogy az ábra nyilai is mutatják. Az objektumokra hivatkozást referenciának (reference) nevezzük. A létrehozott változók (variable) azok, amelyek ezeket a referenciákat tárolják, azaz hozzájuk kötöttünk egy objektumot (binding). Így lehet több referenciánk ugyanarra az objektumra: több változó tárolja ugyanazt a referenciát, több változóhoz van hozzákötve egy objektum.

    a = [1, 2, 3]
    b = a
    b.append(4)

Amikor egy változónak értéket adunk, akkor egy referenciát állítunk be egy meglévő objektumra. Maga az értékadás igazából nem hoz létre objektumot, csak nevet adunk egy objektumnak (name binding). Ez könnyen látható a `b = a` esetben: ott egy újabb változó jön létre, amely ugyanannak az objektumnak a referenciáját tárolja. De ez történik még az `a = [1, 2, 3]` sorban is. Ott az `[1, 2, 3]` kifejezés az, ami a listát létrehozta, utána az értékadás már csak a meglévő listára állít be referenciát.

Mi történik olyankor, amikor számokkal dolgozunk? Az `a = 3` és `b = a` után ugyan egy objektumunk van, két referenciával. A `b += 1` viszont valójában csak a `b = b + 1` rövidítése – amiből a legfontosabb a `b =` rész, vagyis az értékadás. A `b`-nek itt értéket adunk, vagyis másik objektumra állítjuk át (a létrejövő egész szám objektumra, a 4-re), és mindennek semmi köze sem az `a` változóhoz, sem a `3` objektumhoz.

A fentiek miatt van az is, hogy a Python nyelvben a változóknak nincsen típusa: valójában a változó által hivatkozott objektum az, aminek típusa van. Ennek ellenére szoktunk pongyolán a „változó típusáról” beszélni, de a Python nyelvben mindig a változó által hivatkozott objektum típusát értjük ezalatt.

## 27. Az „is” operátor: identitás vizsgálata

Az `is` operátor referenciákat hasonlít össze. Vagy másképp fogalmazva, az `is` operátorral referencia szerint hasonlíthatunk össze két objektumot. Nem azt vizsgáljuk vele, mint az `==` operátorral, hogy ugyanolyan értékű, tartalmú objektumokról van-e szó. Hanem azt, hogy az operátor két oldalán álló objektum ugyanaz-e, azonosak-e: tehát valójában egyetlen objektumról van-e szó. Azt is szoktuk mondani, hogy az `is` operátor az objektumok identitását hasonlítja össze. (Ennek tagadására használható az `is not` operátor: `a is not b`, ami értelemszerűen csak a `not a is b` rövidítése.)

### Ugyanaz a lista

    a = [1, 2, 3]
    b = a
    print("a == b:", a == b)
    print("a is b:", a is b) # !

    b.append(4)
    print(a)

    a == b: True
    a is b: True
    [1, 2, 3, 4]

### Ugyanolyan lista

    x = [1, 2, 3]
    y = [1, 2, 3]
    print("x == y:", x == y)
    print("x is y:", x is y) # !

    y.append(4)
    print(x)

    x == y: True
    x is y: False
    [1, 2, 3]

A fenti kódrészletek erre mutatnak példát. Az első esetben egy listánk van, amelyre `a` és `b` változók is referenciák az `a = b` értékadás miatt. Ilyenkor természetesen `a == b` igaz lesz, hiszen ugyanazokat a számokat látjuk. De `a is b` hasonlóképp igaz, mert ugyanarról az egyetlen egy listáról van szó, csak két nevet adtunk neki. Így amikor `b`-hez adunk hozzá elemet, akkor `a` is változni fog.

A második esetben két különálló listánk van. Kétszer értékeltük ki az `[1, 2, 3]` kifejezést, tehát két lista jött létre, amelyek egymástól függetlenek. (Ugyanezt a hatást értük volna el az `y = list(x)` sorral.) Bár ilyenkor `x == y` továbbra is igaz – ugyanaz a tartalom –, mégis az `x is y` kifejezés hamisat ad, mert a két lista identitása nem egyezik meg. Különállóak, így amikor `y`-hoz új elemet adunk hozzá, `x` nem változik.

## 28. Minden változó referenciát tárol

### Változók és listák: referenciákat tárolnak

A Python szemléletében még a számok is objektumok. És valójában, ha egy változónak számot adunk értékül, akkor is csak egy referenciát állítunk be egy bizonyos szám objektumra, ami ugyanúgy létrejön valamikor, ahogy egy listát is létrehozunk. Maga a lista is csak referenciákat tartalmaz.

    a = "almafa"

    b = a

    c = 2

    d = [c, a, 5]

Lássuk, mi történik ebben a kódban!

- `a = "almafa"`: létrejön egy sztring, és az `a` változó eltárolja a referenciáját.
- `b = a`: nem jön létre sztring, csak a `b` változó is meghivatkozza a meglévőt.
- `c = 5`: új változó, és új szám típusú objektum jön létre.
- `d = [c, a, 5]`: új lista jön létre, benne három referenciával. Az első referencia ugyanaz lesz, mint ami a `c`-ben is volt, így `d[0]` értéke is 5. A második pedig ugyanaz, mint ami `a` is volt, tehát `d[1]` értéke `almafa`. A `d[2]` listaelemhez új objektum társítódik, az `5`-ös szám.

Mivel a számok és a sztringek immutábilisak, sem `a`, sem `b`, sem `d[1]` módosítása nem lenne hatással a többi változóra, hiába osztoznak hárman az `almafa` objektumon. Ugyanígy, `d[0]`-nak is adhatnánk értéket, vagy `c`-nek, de azok is függetlennek tűnnének.

### Vigyázat!

    a = 1000
    b = 500 + 500
    print("a == b:", a == b)
    print("a is b:", a is b)

    a == b: True
    a is b: False

Számok és sztringek esetén is létrejöhetnek különböző objektumok ugyanazzal az értékkel! Mindkét változónak ugyanazt az értéket adtuk: az egyik `1000`, a másik `500+500`, ami szintén `1000`. De két objektum jött létre! Az összeadás után nem kereste meg a gép, hogy létezik-e már `1000` értékű, `int` típusú objektum valahol, hanem létrehozott egy újat. Emiatt bár `a == b` igaz, `a is b` nem: két különálló objektumról van szó. Nagyon fontos: számokat és sztringeket nem szabad az `is` operátorral vizsgálni egyenlőségre, hanem mindig az `==` operátort kell használni erre a célra!

# Listák két dimenzióban

## 30. 2D lista: foglaltság

Moziban szeretnénk a foglaltságot nyilvántartani:

Moziban szeretnénk a foglaltságot nyilvántartani. A teremben sorok vannak, a sorokban pedig székek. Minden szék foglalt lehet, vagy szabad. Egy konkrét szék foglaltságát legegyszerűbb `bool` típusú értékkel reprezentálni. Foglalt-e, igen vagy nem: `true`, ha foglalt, és `false`, ha szabad.

    foglalt = [
        [ False, False, False, False ],
        [ False, False, False, False ],
        [ False, False, False, False ],
        [ False, False, True,  False ],
        [ False, True,  True,  False ],
    ]

    foglalt[2][1] = True
    if foglalt[2][3]: # A Python-ban nullától, a moziban egytől sorszámozunk!
        print("3. sor 4. szék foglalt")

Táblázat két dimenzióban: listák listájával.

    foglalt[sor][oszlop] = ...

Két dimenzióban táblázatot egyszerűen listák listájával tudunk létrehozni. A `foglalt` változó által hivatkozott lista így az egyes sorokat tartalmazza. Az egyes sorok azon belül pedig logikai értékeket tárolnak: `True`, ha foglalt az adott szék, amúgy `False`.

Egy konkrét széket így két egymás utáni indexeléssel érünk el. Az első indexelés a sorok listájából kiválaszt egyetlen egy sort. Ez is egy lista, úgyhogy itt jönnie kell egy második indexelésnek: az pedig a sorból kiválasztja az adott széket.

Egyéb példák, ahol 2D listát használhatunk:

Amőba, vagy tic-tac-toe játék pályája

Mátrix számokkal

## 31. Miért nem működik?

Láttuk, hogy eleve feltöltött, adott méretű listát a `[kezdetiérték] * méret` kifejezéssel tudunk létrehozni. Ez az egyelemű listát fűzi össze annyiszor, amennyivel szoroztuk, így alakul ki a sokelemű lista. Kézenfekvőnek tűnik ezután, hogy a mozi foglaltsági táblázatát a `[[False] * székek_száma] * sorok_száma` kifejezéssel hozzuk létre. Itt azonban valami nagyon furcsa dolog történik:

    foglalt = [[False] * 4] * 4

    for sor in foglalt:
        print(sor)

    foglalt[2][1] = True

    for sor in foglalt:
        print(sor)

    [False, False, False, False]
    [False, False, False, False]
    [False, False, False, False]
    [False, False, False, False]

    [False, True, False, False]
    [False, True, False, False]
    [False, True, False, False]
    [False, True, False, False]

Olyan, mintha egyetlen egy szék foglaltra állítása miatt abban az oszlopban az összes szék foglalttá válna. Mitől van ez?

A referenciák és objektumok fogalmának ismeretében könnyű megmagyaráznunk, mi történt. A `[False] * 4` kifejezés létrehozott egy olyan listát, amiben négy `False` érték található; eddig rendben is van a dolog. Utána viszont ezt a listát tettük be négyszer egy másik listába. Vagyis a külső listába négyszer tettük ugyanannak az egy listának a referenciáját. Egy objektumunk van, és azt hivatkozzuk meg négyszer. Így nem csoda, hogy valamelyik elemet `True`-ra állítva úgy tűnik, hogy a „többi lista” is megváltozott. Nincsen többi lista, csak egyetlen egy.

## 32. 2D lista létrehozása

A megoldás: különálló listákat kell létrehozni!

    foglalt = []
    for _ in range(4):
        foglalt.append([False] * 4)

    for sor in foglalt:
        print(sor)

    foglalt[2][1] = True
    for sor in foglalt:
        print(sor)

    [False, False, False, False]
    [False, False, False, False]
    [False, False, False, False]
    [False, False, False, False]

    [False, False, False, False]
    [False, False, False, False]
    [False, True,  False, False]
    [False, False, False, False]

A megoldás lényege az, hogy négyszer hozzunk létre ugyanolyan listákat. Így négy különálló, egymástól független listákat kapunk – a sorokat –, és ezeket tesszük be a kezdetben üres, sorokat tároló `foglalt` nevű listába. Ha négyszer értékeljük ki a `[False] * 4` kifejezést, akkor négy különálló, független listánk lesz!

Miért ilyen furcsa a ciklusváltozó neve a fenti kódban? Az alulvonás karakter `_` ugyanolyan szerepű a kódban, mint bármelyik betű: lehet azonosító része. Azaz nevezhetünk el így változót is. Alulvonásnak szokás elnevezni ciklusváltozókat olyankor, amikor az értékére nincs szükségünk. A fenti kódban a `range()`-től származó egész számok pont ilyenek: nem használjuk semmire, csak kellett egy ciklus, ami minden létrehozandó sorra lefut.

Jó tanács: A referenciákkal kapcsolatos problémák megértéséhez mindig készítsünk rajzot!

## 33. Összefoglalás

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

- Kimenetet formázni f-string illetve string.format segítségével. A bonyolultabb formázási kódokat nem kell fejből tudni.
- Indirekt adatelérést használni.
- Álvéletlenszámokat generálni.
- Tisztában kell lenni a referencia fogalmával és ennek következményeivel, valamint az is operátorral.
- Többdimenziós listákat létrehozni.