# 3. hét: adatszerkezetek építése

Czirkos Zoltán, Frey Balázs · 2024.09.22.

Gyakorlófeladatok az előadás anyagához kapcsolódóan.

## 1. Listák: statisztikák, indirekt adatelérés

### Statisztika a számokról (részletes mintamegoldással)

    1: 5 db
    2: 3 db
    3: 4 db
    ...

Írj programot, amelyik a szabványos bemenetről olvas számokat, ameddig üres sort nem kap. Számold meg benne, hogy a beírt számok közül, amelyek 1 és 10 között vannak, melyik hányszor szerepelt! Írd ki ezt a szabványos kimenetre az oldalt látható formában!

Figyelj arra, hogy ezt egy fix méretű listával meg kell tudnod oldani. Vagyis bármilyen sok számot ad is meg a felhasználó, a megépített adatszerkezeted nem nőhet azzal együtt; nem kell eltárolnod a beolvasott adatokat.

Megoldás

### A megoldáshoz vezető ötletek

- Biztosan kell egy ciklus, amelyik a számokat olvassa be.
- Minden pontszámhoz tartozik egy számláló, amit növelni kell akkor, ha hozzá tartozó számot látunk.
- A számlálók és a beolvasott számok között egy megfeleltetést kell létrehozni: melyik számhoz melyik számláló tartozik.

Szám | Számláló | Érték
--- | --- | ---
1 | `t[0]` | 5 db
2 | `t[1]` | 3 db
3 | `t[2]` | 4 db
x | `t[x-1]` | ...

A sok számlálóhoz létrehozhatunk egy listát. Mivel tízféle szám van, azokhoz tíz számláló kell tartozzon, a lista elemszáma is tíz lesz. A megszámolandó számok egész számok, ezért könnyű egy szám–listaelem hozzárendelést kitalálni: egy adott számhoz pont az annyiadik elemet használjuk, amennyi a szám értéke. Mivel a beérkező számok az 1…10 tartományban vannak, a lista viszont 0…9 tartományban indexelődik, ezért az indexeléshez mindig a szám−1 értéket használjuk. (Hogy mindenhol ugyanilyen legyen az indexelés, és jobban érthető legyen a program, a számlálók nullázása és a kiírás is ezt az elvet követi a lenti programban.) A kialakuló adatszerkezet a táblázatban látható.

Lényegében a számlálás tételét kell megvalósítani, két különbséggel: 1) nem egy számláló lesz, hanem sok, 2) a számlálás feltétel nélküli.

    db = [0] * 10

    print("Számok 1 és 10 között, üres sor = vége: ")
    sor = input()
    while sor != "":
        szam = int(sor)
        db[szam - 1] += 1
        sor = input()

    szam = 1
    while szam <= 10:
        print("{}: {} db".format(szam, db[szam - 1]))
        szam += 1

### Kódtörő I.

Bölcsész haverod, aki az angol nyelvvel foglalkozik, szeretné megvizsgálni a szavakban előforduló betűk gyakoriságát. Ezért megkér téged, hogy írj egy programot, amely a szabványos bemenetén egy angol nyelvű szöveget fogad. A szöveg eleve nagybetűsítve van: „TO BE OR NOT TO BE: THAT IS THE QUESTION.” A programod feladata egy statisztikát készíteni, amelyben az szerepel, hogy melyik betű hányszor fordult elő a szövegben, és az összes betű hány százalékát adja. A kimenete ilyen:

    A: 19 db, 5.0%
     B: 7 db, 1.8%

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.

### Kódtörő II.

Kódtörő haverod nagyon ért a titkosítások visszafejtéséhez, a programozással viszont hadilábon áll. Szerzett egy számjegyekből álló titkos kódot:

    1238971125432563125555535555665554325671231321555253555

Megfigyelte, hogy ebben nem egyforma a jegyek gyakorisága. Megkért téged, hogy írj egy programot, amely a szabványos bemenetén fogadja ezt a szöveget, és megmondja, hogy melyik az a számjegy, amely a legtöbbször szerepelt, és azt is, hogy hány % a gyakorisága! A fenti bemenetre ez az 5-ös számjegy, 40%-kal. Ha bemeneten számjegyen kívül más karakter is szerepel, azt figyelmen kívül kell hagyni.

### ZH statisztika I.

Egy oktató statisztikát szeretne készíteni a megíratott ZH-k sikerességéről. A ZH-n 4 csoport volt (A…D). Mindegyikben három feladat, ezek pontszáma egész szám, egyenként maximum 10 pont, így a ZH-k maximum 30 pontosak lehetnek. A ZH akkor sikeres, ha a feladatok külön-külön legalább 2 pontosak, és a ZH legalább 12 pontos.

Írj programot, mely a szabványos bemenetéről olvassa be soronként egy ZH betűjelét és 3-3 pontszámát, és a szabványos kimenetre írja ki az egyes sorokra, hogy hány embernek sikerült. A beolvasott adatsor végét üres sor zárja.

Példa bemenet:

    A 1 10 7
    C 3 3 5
    B 10 10 9

Példa kimenet:

    A 0
    B 1
    C 0
    D 0

### ZH statisztika II.

Egy oktató statisztikát szeretne készíteni a megírt ZH-król. A ZH-ban három feladat van, ezek pontszáma nemnegatív egész szám, egyenként max. 10 pont, így az egész max. 30 pontos lehet.

Írj programot, mely a szabványos bemenetéről olvassa be soronként a ZH-k pontszámait. Az adatsort üres sor zárja. Írja ki ezután a szabványos kimenetre, hány 0 pontos, hány 1 pontos, … és hány 30 pontos megoldás lett. Ha adott pontszámú dolgozat nem született, a sort ne írja ki.

Példa bemenet:

    8 10 7
    4 3 5
    10 10 9
    10 9 10

Példa kimenet:

    12 pontos: 1 db
    25 pontos: 1 db
    29 pontos: 2 db

### Múzeum I.

Egy múzeumban kíváncsiak arra, a hét mely napján van a legtöbb látogató. Ehhez több hét adatait feldolgozzák.

Írj programot, mely a szabványos bemenetén fogadja a múzeum napi látogatási adatait úgy, hogy soronként a hét napjának sorszámát kapjuk 0-6 között, majd szóközzel elválasztva a látogatók számát. Az adatok rendezetlenül érkeznek, adott sorszámú naphoz több bejegyzés is tartozhat. A bemenet végét üres sor jelzi.

Írja ki a program a szabványos kimenetre annak a napnak a sorszámát, mely a legtöbb látogatót jelenti. Feltételezzük, hogy egy ilyen nap van.

Példa bemenet:

    1 7
    2 3
    6 33
    5 44
    4 4
    6 55

Példa kimenet:

    6

### Múzeum II.

Kis ZH volt

Egy múzeumban gazdasági okok miatt heti egy szünnapot szeretnének tartani, ezért keresik a hét azon napját, amikor a legkevesebb a látogató.

Írj programot, mely a szabványos bemenetén fogadja a múzeum napi látogatási adatait úgy, hogy soronként a hét napjának sorszámát kapjuk 1-7 között, majd szóközzel elválasztva a látogatók számát. Az adatok rendezetlenül érkeznek, adott sorszámú naphoz több bejegyzés is tartozhat. A bemenet végét üres sor jelzi.

Írja ki a program a szabványos kimenetre annak a napnak a sorszámát, amely a legkevesebb látogatót jelenti. Feltételezzük, hogy egy ilyen nap van.

Példa bemenet:

    1 7
    3 5
    6 56
    2 3
    7 88
    5 25
    4 7
    1 6
    0 0

Példa kimenet:

    2

## 2. Listák kétdimenzióban

### Ülőhelyek

Egy 195 fős előadóba előadást szerveznek. A székek 13 sorban, összesen 15 oszlopban (téglalap) helyezkednek el. A székek számozása a (színpaddal szembeni) bal alsó sarokból kezdődik, jobbra növekszik, és a legfelső sorban vannak a legnagyobb számú székek.

A jegyirodában kétdimenziós listában tárolják a már kiadott foglalásokat. A foglalt helyeket a megfelelő székszámhoz írt `True` jelöli, `False` a szabad hely. Készíts programot, mely az újonnan érkező vendégek számára a kívánt számú, egymás melletti ülőhelyet kikalkulálja! Vigyázz a sorok szélére!

### Tic-Tac-Toe

Készíts el egy 3x3-as listát általad megadott Tic-Tac-Toe játék állásának tárolására! A programod legyen képes a játékhelyzet kirajzolására a szöveges képernyőre és vizsgáld meg, hogy nyerésre áll-e valamelyik játékos vagy sem!

        -----
        |O_X|
        -----
        |_OO|
        -----
        |X_X|
        -----

Ebben az állásban pl. a soron következő játékos tud nyerni, akár X, akár O.

### Lineáris algebra

Készíts n×m kétdimenziós listát mátrixok tárolására. Valósítsd meg az alapvető aritmetikai műveleteket, összeadás, szorzás stb. Ha már tanultál ilyen algoritmusokat, írd meg a négyzetes mátrix inverzét előállító kódot! (Vigyázz! A tankönyvi, adjungálton alapuló módszert ne használd, mert a számábrázolás pontatlansága miatt nem fog helyes eredményt adni, inkább keress kifejezetten numerikus módszereket!) A mátrixokat NEM ÍGY kell Pythonban használni, mert erre sokkal jobb könyvtárak vannak, ez csak a ciklusok és több dimenziós listák gyakorlására szolgáló feladat. Érdeklődők nézzenek utána a numpy-nak!

### Szavak, mondatok, betűk

Írj programot a bemeneten érkező szöveg listák listájában történő tárolására! Az első dimenzió a mondatok, a második dimenzió a szavak legyen. A program ezután kérjen be három számot, mondat, szó, betű sorrendben, majd írja ki megfelelő mondat és szó meg adott betűjét. Pl. ebben a szövegben a 3. mondat 4. szavának 2. betűje az "é".

## 3. Véletlenszámok, játékok

### Fej vagy írás

Adott egy feladat: „dobjunk fel egy pénzt” a programban, és írjuk ki, hogy fej vagy írás lett. Ennek a feladatnak az alábbi megoldása helytelen:

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

A kipróbálás nélkül mondd meg: milyen hibás eredményt adhat ez a program, és milyen elvi hiba miatt? Ha megvan, próbáld ki, és végül javítsd ki a programot!

Megoldás

A `.randint()` minden hívása egy új véletlenszámot ad. A fenti, hibás kódrészletben a `randint()`-et kétszer hívjuk meg, tehát tulajdonképpen mintha nem egy, hanem két pénzérmét vizsgálnánk: ha az első fej, kiírjuk hogy fej, ha a második írás, kiírjuk, hogy írás. Így aztán az is lehet, hogy mindkét szó kiíródik, de az is, hogy egyik sem. Javítva:

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

### Kő, papír, olló

    Kő (k), papír (p), olló (o) vagy vége (v)?

    Szerinted: k
    Szerintem: k.
    Senki nem kap pontot.

    Szerinted: p
    Szerintem: k.
    p>k, ezt te vitted!

    Szerinted: v

    Te nyertél, 1>0 ponttal.

Írj programot, amelyik „kő, papír, olló” játékot játszik! A program először kérje el a felhasználó tippjét (`k`, `p`, `o` betűk, mint kő, papír, olló). Ezután válasszon ő maga is egyet, és hasonlítsa a kettőt össze! A kő erősebb, mint az olló, mert kicsorbítja. A papír erősebb, mint a kő, mert becsomagolja. Az olló erősebb, mint a papír, mert elvágja. Ezek alapján a gép vagy a játékos kapjon egy pontot! Ha egyformát tippeltek, akkor semelyikük nem kap. A `v` beírása után írja ki a program, hogy ki nyert!

Tipp

A gépnek háromféle választása lehet. Érdemes ehhez a `random.choice()` függvényt használni egy listával, amiben a három választás van.