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

Ú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

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.

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

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

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()

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.

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]})

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.

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.

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}%")

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.

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(6)
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)