Zárthelyi és vizsga segítség

Figyelmeztetés: ez az összefoglaló nem pótolja sem a laboron elvégzett munkát, sem az előadásanyag ismeretét, sem a feladatgyűjteményből történő önálló gyakorlást!

Ezek nélkül 我们可以用中文而不是 Python 来写

A "rajzolós" feladatoknak alapvetően kétféleképpen állhatunk neki.

Az egyik megoldási módban rá kell jönnünk arra az összefüggésre, amely az ábra lényeges elemeinek sor és/vagy oszlop függését tartalmazza. Ezt legegyszerűbb lerajzolni, rajzoljunk ábrát 2-3 esetre és nem lesz túl nehéz az általában lineáris összefüggést felismerni. Ezután már csak egy ciklust kell csinálnunk a sorokra és összerakni az ábrát sztring műveletekkel.

Például a csúcsán álló háromszög esetén:

n=3           n=4         n=5

  01234     0123456     012345678
0 ooooo     ooooooo     ooooooooo
1 .ooo      .ooooo      .ooooooo  
2 ..o       ..ooo       ..ooooo
3           ...o        ...ooo
4                       ....o

A sor elején lévő szóközök száma megegyezik a sor számával, az 'o' betűk száma pedig a 0.sorban 2n-1 és soronként kettővel csökken. Azaz például:

n=int(input())
for sor in range(n):
    print(' '*sor + 'o'*(2*n-1-2*sor))

A másik megoldási mód az, hogy használjuk a koordinátageometriai ismereteinket. Ez néha egyszerűbb, néha pedig bonyolultabb kódhoz vezet. Két, egymásba ágyazott ciklust készítünk, sor illetve oszlop szerint (y ill x), majd a ciklus belsejében döntjük el egy elágazással, hogy mit rajzolunk. Ne felejtsük el, hogy a belső ciklusban nem szabad új sort kezdeni, csak a külsőben. Azaz valami hasonló lesz a kódunk ebben az esetben:

n=int(input())
for y in range(n):
    for x in range(2*n):
        # ide jön az egy karaktert kiíró kód
        if x>y and x < 2*n-y:
            print('o', end='')
        else:
            print(' ', end='')
    print()

Valószínűleg az első könnyebben előállítható megoldás, mert a másodikhoz alaposan végig kellett gondolni az egyenesek egyenletét. De például a Négyzet (téglalap) rajzolása feladatnál ez a módszer lesz egyszerűbb.

Azt is megfigyelhetjük, hogy egybefüggő területeknél egyenlőtlenségek ÉS kapcsolata adja a rajzot, vonalas rajzok esetén pedig a vonalak egyenletének VAGY kapcsolatai.

Ezekben a feladatokban négy dolgot kell összekombinálni:

1. az adatszerkezet kialakítását
2. az adatok beolvasását és a hibás adatok kezelését
3. a feladat típusától függően(!) az adatok feldolgozását
4. az eredmények megjelenítését.

Nézzük őket sorban!

Adatszerkezet kialakítása

Számláló jellegű feladatok esetén (minimum, maximum, darabszám, összeg, átlag stb.) nem kell az összes adat, tehát nem is tároljuk. Ki kell találjuk a leképezést egy listára, ha átnézed és elolvasod az eddigi feladatokat akkor szinte mindent láttál már:

Feladat	Tároló	Leképezés
Dolgozat pontszámai	[0]*(max pontszám+1)	[pontszám]
Egész számok	[0]*(legnagyobb-legkisebb+1)	[szám-legkisebb]
Kockadobások (2 kocka)	[0]*(12-2+1)	[összeg- 2]
Autópálya bírságok	[0]*24	[óra]
Autópálya forgalmi statisztika	[0]*(maxsebesség//10)	[sebesség // 10]
Nagybetűk megszámolása	[0]*(ord('Z')-ord('A')+1)	[ord(betu)- ord('A')]

Nézd át és értsd meg az adatszerkezet kialakításának okait és azt, hogy hogyan címezzük a listát, valamint kijelzésnél hogyan lesz a forrásadatnak megfelelő adat a lista indexéből.

Ezután válaszold meg magadban, hogy milyen adatszerkezetet használnál és hogyan történik az elérés a Feladatgyűjtemény megadott példáin! (Ha kiválasztod egérrel, látható lesz a válasz.)

Feladat	Tároló	Leképezés
Statisztika a számokról	[0]*10	[szam]
Kódtörő II	[0]*10	[ord(szamjegy)-ord('0')], [int(szamjegy)]
ZH statisztika I	[0]*4	[ord(csoport)-ord('A')]
ZH statisztika II.	[0]*31	[pont]
Múzeum I.	[0]*6	[nap]
Múzeum II.	[0]*6, [0]*7	[nap-1] , [nap]
Autópálya I.	[0]*24	[ora]
Autópálya II.	[0]*24	[ora]
Bliccelés I.	[0]*48	[ora*2+perc//30]
Bliccelés II.	[0]*24	[ora]

Nem kell feltétlenül a lehető legkevesebb memóriahasználatra törekedni. Pl. a hónapok hosszának tárolásához nyugodtan használhatunk egy 13 elemű tömböt, ahol a nulladik elemet nem használjuk, így egyszerűen tudjuk a hónap sorszámával címezni, és nincs szükség 1 levonására, így nem is tudunk elfelejtkezni róla. Egy egész számnak megfelelő memória pedig elhanyagolható.

Beolvasás

Olvassuk be az adatokat a bemenetről, az adatok végét üres sor jelzi.

sor=input()
while sor!="":
    ## ellenőrzés
    ## feldolgozás vagy tárolás
    sor= input() # <-- figyelni kell, nehogy lemaradjon a végéről!

Jobb megoldás a break használata, picit logikusabb, hogy az input után van az ellenőrzés, és ha az sikeres a feldolgozás/tárolás

while True: # végtelen ciklus
    sor= input()
    if sor=="":
        break
    ## ellenőrzés
    ## feldolgozás vagy tárolás

Olvassunk fájl vége jelig!

while True: # végtelen ciklus
    try:
        sor= input()
        ## ellenőrzés
        ## feldolgozás vagy tárolás
        ## ami kivételt is dobhat, azt majd külön kezelni kell
    except EOFError:
        break

Olvassunk fájl vége jelig, ha hiba történik, írjuk ki a hibás sort, de haladjunk tovább

while True: # végtelen ciklus
    try:
        sor= input()
            ## ellenőrzés
            ## feldolgozás vagy tárolás
    except ValueError:
        print(f"Hiba történt: {sor}")
        continue # itt pont felesleges, de jelzi a szándékot
    except EOFError:
        break

stb.

Feldolgozás

Ez teljesen feladatfüggő. A leírásnak megfelelően darabolnunk kell esetleg beolvasott sort, egésszé vagy lebegőpontos számmá konvertálni az adatokat, majd az adatszerkezetet feltölteni vagy előállítani a bejövő adatokból valamilyen számolt adatot, amivel a tároló listánkat vagy címezni fogjuk, vagy más módon felhasználjuk.

Pl. kockadobások összege:

osszeg= random.randint(1,6) + random.randint(1,6)
db[osszeg -2] +=1 

Csoportok szerinti dolgozatok példáinak összegzése:

darabolt= sor.split()
csoport= sor[0]
pont= 0
for i in range(1, len(darabolt)):
    pont+= int(darabolt[i])

Adatok megjelenítése

Itt is két választásunk van, használhatjuk a listaelemeket, de ekkor a leképezés inverzével kell a forrásadatot előállítani. Pl. a betűk számolásánál:

for i in range(len(tarolo)):
    kar= chr(i+ord('A'))
    if tarolo[i] != 0:
        print(f"{kar}: {tarolo[i]})")

Csinálhatunk ciklust az eredeti adatokkal és visszaszámoljuk az indexet, mint amikor a listát töltöttük fel, pl. az autópályánál a sebesség számolása

for sebesseg in range(0, 200, 10):
    ertek= db[sebesseg//10]
    print(f"{sebesseg:>3}-{sebesseg+9:>3} {ertek}")

A kijelzés feldobhatjuk hisztogrammal:

    hist= '#' * (ertek*50//maxertek)

ahol a maxertek a maximális érték és ez lesz 50 karakter hosszú.

stb.

Ezeknél a feladatoknál nagyon fontos, hogy felülről-lefelé (top-down) gondolkozzunk. Minden, ami 3-4 sornál bonyolultabb, mehet függvénybe.

Pl. az Armstrong számok esetén a megoldás keresése valahogy így nézhet ki:

def main():
    n= int(input("Hány jegyű számok között?"))
    for i in range(10**(n-1), 10**n):
        if armstrong(i):
            print(i)    

Kelleni fog tehát egy armstrong függvény, ami megmondja, hogy az adott szám Armstrong tulajdonságú-e, vagy sem.

def armstrong(szam):
    szj= szamjegyek(szam)
    n= len(szj)

    rv= 0
    for sz in szj:
        rv+= sz**n

    return rv == szam

Már csak a számjegyekre bontást kell megírnunk. Itt az ötlet az, hogy addig osztjuk a számot tízzel, amíg nulla nem lesz (egész osztás!) és a maradék az mindig hátulról a következő számjegy, amit hozzáfűzünk egy listához. Pl. 135 esetén

135//10 = 13 és 135 % 10 = 5    --> 5
13//10 = 1 és 13 % 10= 3        --> 5, 3
1 //10 = 0 és 1 % 10= 1         --> 5, 3, 1

Fordított sorrendben kapjuk, ha fontos a sorrend, meg kell fordítani.

def szamjegyek(szam):
    rv=[]
    while szam >0:
        rv.append(szam % 10)
        szam //=10
    return rv

Persze lehet máshogy is, ezt a munkát az str függvény elvégzi, nekünk csak vissza kell alakítanunk egész számokká a karaktereket. Valójában az str függvény az egész számokra hasonlóan van megvalósítva.

A boldog számok lényeges algoritmusa pl.

def boldog(szam):
    szam= szamjegy_negyzetosszeg(szam)
    while szam > 10:
        szam= szamjegy_negyzetosszeg(szam)
    return szam == 1

A szamjegy_negyzetosszeg(szam) függvény pedig hívja a számjegyekrebontást és a számjegyek négyzetét összegzi.

A nagyon tökéletes számok megoldásötlete (egy kicsit trükkös, de követhető, egyszerűen Python-ra fordítjuk magyarból)

def nagyon_tokeletes(szam):
    # "osztói összegének osztóit összegezve az eredeti szám kétszeresét kapjuk." 
    return oszto_osszeg(oszto_osszeg(szam)) == 2* szam

Már csak az oszto_osszeg függvényt kell megírni. Ehhez pl. írhatunk egy osztok függvényt, ami egy listába visszaadja az osztók számát, majd simán összegezzük. Vagy akár így is, nem mindenáron kell a specializált függvényeket erőltetni:

def nagyon_tokeletes(szam):
    # "osztói összegének osztóit összegezve az eredeti szám kétszeresét kapjuk." 
    return sum(osztok(sum(osztok(szam)))) == 2* szam

A Kapitány main-je:

def main():
    ev=2024
    while len(osztok(ev))!=8 or 7 not in szamjegyek(ev):
        ev-=1
    print(f"{ev}-ban született a kapitány")

stb.

Alapvetően elvárt, hogy az osztálynak legyen konstruktora és az összes adattagot a konstruktorban inicializáljuk, ha éppen nem lehet hozzá értelmes értéket rendelni, akkor az legyen None. Ez valójában Python esetén nem kötelező, de a tárgyban elvárjuk és ha nem történik meg, az hibának értékeljük.

pl. Sebesség vektor

class Vektor:
    def __init__(self, vx, vy):
        self.vx = vx
        self.vy = vy

Az osztály metódusai (belső függvényei) első paramétere belül a self, de amikor egy példányon meghívjuk, már nem kell odatenni. Metódus esetén minden adattagot a self.adat szintaktikával kell elérni.

Az előző példa folytatásaként:

    def hossz(self):
        return math.sqrt(self.vx*self.vx + self.vy*self.vy)

Ugyanez külső függvényként megvalósítva:

def hossz(v):
    return math.sqrt(v.vx*v.vx + v.vy*v.vy)

Nem kötelező sem a metódusok, sem az operátorok használata, bár sokkal kényelmesebb, ebben a példában a hossz függvényt az abszolút érték operátor ki tudja váltani. A sztringgé alakító operátort viszont ismerni kell:

    def __str__(self):
        return f"Vx={self.vx} Vy={self.vy} |V|= {abs(self)}" 
    def __abs__(self):
        return math.sqrt(self.vx*self.vx + self.vy*self.vy)

Javasolt a with szerkezet általános használata, mert automatikus az erőforrás kezelés. Pl. fájl megnyitása olvasásra, majd soronkénti olvasás:

n=1
with open("valami.txt", "rt") as f:
    for sor in f:
        print(f"{n} {sor.rstrip()})

Figyelni kell arra, hogy a beolvasott sor tartalmazza az újsor karaktert. Ha erre nincs szükségünk, el kell távolítani.

Egy fájl megnyitása írásra:

with open("barmi.txt", "wt") as f:
    f.write("Barmi\n")  # f.write nem tesz újsort a végére
    print(1,2,3, file=f) # használható a print is.

Használható a try/finally szerkezet is, de ez a legegyszerűbb, ezt érdemes használni mindenütt.

Szótárt a legegyszerűbben úgy tudunk létrehozni, hogy felsoroljuk kapcsos zárójelben a kulcs-érték párokat. Pl.

bevasarlolista = {
    "alma": 2,      # kulcs
    "körte": 1,
    "barack": 5,
}

Az egyes elemeknek a hozzáadása és elérése az indexelő operátorral történik. Ha a kulcs nem létezik, kivétel keletkezik. Gyakran van olyan feladatunk - pl. számlálás - hogy ha létezik a kulcs, a hozzátartozó értéket pl. megnövelni kell, ha pedig nem létezik, akkor létrehozni egy adott értékkel. Erre a get metódus használható.

bevasarlolista["barack"]+=1
bevasarlolista["citrom"]= bevasarlolista.get("citrom", 0) + 1

A szótár elemein háromféleképpen iterálhatunk. A "sima" for ciklus a szótár kulcsait adja, amivel pl. indexelhetjük az értékeket:

for mit in bevasarlolista:
    print(f"Vegyél {bevasarlolista[mit]} kg {mit}-t")

Az items()-en történő iteráció egy (kulcs, érték) tuple-t ad vissza:

for mit, mennyit in bevasarlolista.items():
    print(f"Vegyél {mennyit} kg {mit}-t")

Végül - bár általában ezt nem ciklusban használjuk, hanem pl. a sum, max, min stb. függvényeknek adjuk oda - lehetőségünk van csak az értékeken végig menni a values() hatására.

for mennyi in bevasarlolista.values():
    print(f"{mennyi} kg ")

print(f"Összesen: {sum(bevasarlolista.values())} kg")

Ezekben a feladatokban az állapottábla elkészítése az "észmunka", mert maga program kódolása a táblázat alapján gyerekjáték, tehát leginkább az állapottábla létrehozását kell gyakorolni pl. az itt található feladatok megoldásával.

Eléggé el lehet bonyolítani, de számonkérésen 2-3 állapotnál/karakterosztálynál több nem várható.

Gyakorlásképpen fejtsd vissza, mit csinál ez az állapottábla!

	"	/	*	\	egyéb
KOD	->SZTRING, c	->KEZD	c	c	c
SZTRING	->KOD, c	c	c	->ESC,c	c
ESC	->SZTRING, c	->SZTRING, c	->SZTRING, c	->SZTRING, c	->SZTRING, c
KEZD	->SZTRING /,c	c	->KOMMENT	->KOD, /,c	->KOD, /,c
KOMMENT	-	-	->KILEP	-	-
KILEP	->KOMMENT	->KOD	-	->KOMMENT	->KOMMENT

Megoldás, de helyesen kezeli a szövegkonstansokat is, attól nőtt nagyra.

A standard bemenetről olvasó szűrő/számoló stb. állapotgépes feladatok csontváza a következő:

#
# az állapottábla, vagy más szöveges leírás, amit a feladat kér
#
import sys

# <-- az állapotok definíciói
ALAP=0
ELSO=1
#stb

# az állapotváltozó, ami az alap állapottal van inicializálva
allapot=ALAP
# egyéb szükséges változók, pl. számlálók

while True:     # a beolvasó ciklus
    c= sys.stdin.read(1)        # egy karaktert olvasunk, soha nem többet
    if c=='':
        break                   # megállunk ha vége

    # ide kerül az állapotgép. Egy nagy if/elif/else állapotonként, azon belül szintén egy if/elif/else bejövő karakter tulajdonságait vizsgálva. 
    # (vagy fordítva, az mindegy. Kis gyakorlással rá lehet jönni, melyik az egyszerűbb, de ez nem követelmény)


# ide kerül a végső okosság, pl. darabszám kiírás stb.

Ha az utolsó előadáson itt elmondott függvény referenciákat megértjük, még egyszerűbb lesz a kódolás, de ez nem követelmény már. Gyakorlásképpen érdemes megcsinálni egy-két feladatot többféleképpen:

1. if állapotok majd karakterek szerint szétválasztva
2. if karakterek majd állapotok szerint szétválaszva
3. tuple-k kétdimenziós táblázatával.

A fa egy csúcsát egy objektum írja le, amelyben az adatokon túl van két ugyanilyen objektumra mutató referencia: a bal, illetve jobb gyermek. Vagy ha épp arrafelé már nem lehet továbbmenni, akkor None.

class BinfaElem:
    def __init__(self, adat):
        self.adat = adat
        self.bal = None
        self.jobb = None

Ha "kézzel" (kódból) építünk fel egy fát, azt valahogy így kell csinálni.

       3
      / \
     1   4 
    / \
   0   2  

gyoker= BinfaElem(3)
gyoker.bal=BinfaElem(1)
gyoker.bal.bal= BinfaElem(0)
gyoker.bal.jobb= BinfaElem(2)
gyoker.jobb= BinfaElem(4)

Lehet persze másképp is, ha a konstruktorban átadjuk a fa bal és jobb referenciáját:

class BinfaElem:
    def __init__(self, adat, bal= None, jobb=None):
        self.adat = adat
        self.bal = bal
        self.jobb = jobb

gyoker= BinfaElem(3, BinfaElem(1, BinfaElem(0), BinfaElem(2)),BinfaElem(4))

Figyeljünk arra, hogy a bal illetve jobb referencia alapértelmezetten None legyen!

A keresés kivételével az algortimusok rekurzívak. Két dolog kell a rekurzióhoz: leállási feltétel és a rekurzív hívás mindkét irányba. A leállás általában az, hogy a hívott referencia None

def fafuggveny(gyoker):
    if gyoker==None:
        return
    # hivas, feltétel, számlálás stb mindkét irányba és return

Érdemes először szövegesen megfogalmazni magunkban, majd utána kódolni.

Sorrendben kiíratás:

1. Üres fában nincs mit kiírni
2. Írassuk ki a kisebbeket, amik a baloldali részfában vannak
3. Írjuk ki az adatot
4. Írassuk ki a nagyobbakat, amelyek pedig a jobboldali részfában vannak.

def binfa_sorban_kiir(gyoker):
    if gyoker is None:   # 1
        return

    binfa_sorban_kiir(gyoker.bal)  # 2
    print(gyoker.adat, end=" ")    # 3
    binfa_sorban_kiir(gyoker.jobb) # 4

Hány eleme van a fának?

Üres fának egy sincs, egyébként pedig annyi, amennyi a baloldali részfának meg a jobboldali részfának és önmagunk. Tehát:

def binfa_elemszam(gyoker):
    if gyoker==None:
        return 0 

    return binfa_elemszam(gyoker.bal) + binfa_elemszam(gyoker.jobb) + 1

Mennyi a fában tárolt elemek (egész számok) összege?

Az üres fában nyilván nulla. Egyébként pedig a gyökér elem + a baloldali fa összege + a jobboldali fa összege.

def binfa_osszeg(gyoker):
    if gyoker==None:
        return 0     
    return gyoker.adat + binfa_osszeg(gyoker.bal) + binfa_osszeg(gyoker.jobb) 

Milyen magas a fa?

Az üres fa épp 0. Egyébként pedig a magasabbik részfája, plusz egy.

def binfa_magas(gyoker):
    if gyoker== None:
        return 0
    return max(binfa_magas(gyoker.bal), binfa_magas(gyoker.jobb)) + 1

Mikulás

Ha van bal és/vagy jobboldali részfa, annak a gyökerébe kell összegezni, majd az hozzáadni a saját adatunkhoz és kinullázni.

Fa szintje

Olyan függvényt kell írnunk, aminek van egy egész szám szint paramétere is, ami a gyökérre történő híváskor 0. Innentől kezdve egyszerű az algoritmus: üres fába nincs mit beírni, egyébként beírjuk a szintet a fába és rekurzívan hívjuk a függvényt jobbra-balra, de egy szint+1 -el.

Cseresznye

Az üres fában nincs cseresznye :-). Egyébként cseresznye, ha balra-jobbra van elem, de egyiknek sincs gyereke, szép hosszú if. Ha nem cseresznye, akkor meg számoljuk le, mennyi cseresznye van a bal és jobboldali részfában.

def cseresznye(fa):
    if fa == None:
        return 0
    # balra és jobbra is van, de egyiknek sincs gyereke (jó hosszú if)
    if fa.bal!=None and fa.bal.bal== None and fa.bal.jobb== None nd fa.jobb!= None and fa.jobb.bal==None and fa.jobb.jobb==None:
        return 1
    return cseresznye(fa.bal) + cseresznye(fa.jobb)

Kiegyensúlyozott?

Egy bináris fa kiegyensúlyozott, ha minden csúcspont részfájának magassága közötti különbség legfeljebb egy. (Mint ahogy ez az Algoritmusok és Gráfok tárgyból közismert :-)

Tehát: Az üres fa kiegyensúlyozott. Egyébként kiegyensúlyozott, ha a baloldali és jobboldali részfája kiegyensúlyozott és a két részfa között a magasságkülönbség legfeljebb egy.

def kiegyensulyozott(gyoker):
    if gyoker==None:
        return True    
    return (abs(magassag(gyoker.bal)-magassag(gyoker.jobb))<=1 ) 
            and kiegyensulyozott(gyoker.bal) 
            and kiegyensulyozott(gyoker.jobb)

(ezt lehetne okosabban is, mert duplán dolgozunk, magasságot is, kiegyensúlyozottságot is vizsgálunk rekurzívan... Ha pl. -1-et adnánk vissza kiegyensúlyozatlan fa magasságának, akkor O(n) lenne az algoritmus)

Még egy tipp: a rekurzív algoritmus rövid :-).