Algoritmusok

A for vezérlési szerkezet

A for egy vezérlési szerkezet melynek segtségével egy kollekció (mint például lista vagy tuple) elemeit járhatjuk be. A ciklus a ciklus törzsét hajtja végre, oly módon hogy az egyes iterációkban a ciklus változó a kollekció következő elemét veszi fel. Nézzük meg a következő példát:

fruits = ["apple", "banana", "cherry"]
for fruit in fruits:
  print(fruit)

apple
banana
cherry

Feladat

Azonosítsuk a for ciklus elemeit:

• a ciklus változót,

• a kollekciót amit bejárunk, és

• a ciklus törzsét.

Lehetőség van egy számtartományon is végig haladni. A ciklus változója a tartományon végighaladva felveszi a tartomány egyes elemeinek az értékét. Nézzük meg a szintaxist:

for i in range(1, 10):
  print(i)

1
2
3
4
5
6
7
8
9

A range függvény egy range típust ad vissza, ami egy tartományt definiál:

print(range(1, 10))
print(type(range(1, 10)))

range(1, 10)
<class 'range'>

Írjuk ki ennek a tartománynak az elemeit. Hogy ezt megtegyük, a range típust át kell konvertálnunk listává:

print(list(range(1, 10)))

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

A for ciklus ciklus változója ezen lista elemeit fogja bejárni. Vegyük észre, hogy a a range első paramétere a tartomány kezdő értéke, a második paramétere pedig a tartomány határa, amibe a határ értéke nem szerepel. Matematkai kifejezésekkel a range(a, b) a [a,b) tartományt adja meg.

Ha csak egy számot adunk meg a range függvényen belül, akkor a tartomány kezdő értéke a 0, és a tartomány utolsó értéke (nem beleértve azt) a megadott szám:

print(list(range(10)))

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

Lehetőségünk van minden n-edik elem kírására, a range függvény harmadik paraméterén keresztül. A következő példában 1-től 10-ig definiálunk egy tartományt 2 lépésközzel.

print(list(range(1, 10, 2)))

[1, 3, 5, 7, 9]

A ciklusok egymásba ágyazhatóak. Például, írjunk egy függvényt, amely kiírja 1-9-ig a számokat egy mátrixba rendezve.

matrix_str = ''
n = 0
for i in range(0, 3):
  for j in range(0, 3):
    n += 1
    matrix_str += str(n) + ' ' # adjuk meg az i, j, n és matrix_str értékeit az egyes iterációkban ezen sor után
  matrix_str += '\n'           # '\n' a sortörés jele
print(matrix_str)

1 2 3 
4 5 6 
7 8 9 

Feladat

Elemezzük a fenti kódot:

• Mik a for ciklusok blokkjainak (törzseinek) a határai?

• Kövessük végig hogyan alakulnak az i, j, n és matrix_str változó értékeit az egyes iterációkban!

Tipp

A fenti feladat megoldásunk helyességét ellenőrízhejtük ha kiírjuk az egyes változók értékeit a cikluson belül:

matrix_str = ''
n = 0
for i in range(0, 3):
  for j in range(0, 3):
    n += 1
    matrix_str += str(n) + ' '
    print('i=', i, 'j=', j, 'n=', n)
    print(matrix_str)
    print('')
  matrix_str += '\n'

Iterálás listán

Mivel egy lista indexszelhető, ezért a listán úgy is végig tudunk haladni, hogy 0-tól a lista hosszáig indexszeljük:

fruits = ["apple", "banana", "cherry"]
for idx in range(0, len(fruits)):
  print(idx, fruits[idx])

0 apple
1 banana
2 cherry

Vegyük észre, hogy a fenti kódban bemutatott megoldás sokkal komplikáltabb, mint amit az első példában bemutattunk. Akkor miért is lehet rá szükségünk? Az első példában a teljes listán kell végig mennünk; nincs lehetőségünk csak egy részén végigmenni, például a második elemtől kezdve végighaladni a listán. Továbbá, gyakran nem csak az elem értéke fontos számunkra, de az indexsze is, például, amikor egy másik listából akarunk az index alapján értéket kivenni, ahogy azt az alábbi példa is szemlélteti:

fruits = ["apple", "banana", "cherry"]
price = [150, 400, 600]
for idx in range(0, len(fruits)):
  print('Price of ' + fruits[idx] + " is ", price[idx])

Price of apple is  150
Price of banana is  400
Price of cherry is  600

A fenti kódhoz hasonló problémákkal, algoritmusokkal gyarkan találkozhatunk, ezért a Python egyszerűsítést ad a kezünkbe az enumerate függvény formájában:

fruits = ["apple", "banana", "cherry"]
price = [150, 400, 600]
for idx, fruit in enumerate(fruits):
  print('Price of ' + fruit + " is ", price[idx])

Price of apple is  150
Price of banana is  400
Price of cherry is  600

Vegyük észre, hogy a fenti kódban két ciklus változónk van: az idx és a fruit. Az fruit az éppen aktuális ciklusban felvett elemet jelöli, míg az idx annak típusát. Nézzük meg közelebről, mit ad vissza az enumerate függvény ha listává alakítjuk:

print(list(enumerate(fruits)))

[(0, 'apple'), (1, 'banana'), (2, 'cherry')]

Látható, hogy az eredmény tuple-k listája, ahol a tuple-k az indexszet és az elemet tárolják. Ezt egyébként láthatjuk is, ha nem oldjuk fel a tuple-t a ciklusváltozókkal:

fruits = ["apple", "banana", "cherry"]
for t in enumerate(fruits):
  print(t)

(0, 'apple')
(1, 'banana')
(2, 'cherry')

Iterálás szótáron

A szótár nem hagyományos értelemben vett kollekció, így önmagában nem bejárható. Azonban szükségünk lehet a szótárban tárolt értékek bejárására. Mivel a szótár értékei megkapható oly módon, hogy kiírjuk az összes kulcshoz tartozó értéket, így elegendő ha ismerjük szótár kulcsait. Ez megkapható a keys() függvény hívásával:

car = {
  "brand": "Ford",
  "model": "Mustang",
  "year": 1964,
}

print(car.keys())

dict_keys(['brand', 'model', 'year'])

Ezek után a szótárban lévő értékek a következőek:

for k in car.keys():
    print(car[k])

Ford
Mustang
1964

Iterálás a kulcs-érték párokon gyakori probléma, ezért a fenti kifejezés egyszerűsíthető, vagy legalábbis szebben nézz ki, ha az items() függvényt használjuk

for k, v in car.items():
    print(k, v)

brand Ford
model Mustang
year 1964

Az items() függvény visszatérési értéke tuple-k listájaként értelmezhető:

print(list(car.items()))

[('brand', 'Ford'), ('model', 'Mustang'), ('year', 1964)]

A while vezérlési szerkezet

A while szerkezet hasonló a for ciklushoz: a while ciklus a ciklus törzsét hajtja végre addig, amíg a ciklus feltétele igaz. Az alábbi példa 0-tól 10-ig írja ki a számokat:

i = 0
n = 10
while i < n:
  print(i)
  i += 1

0
1
2
3
4
5
6
7
8
9

Feladat

Azonosítsuk a while ciklus elemeit:

• a ciklus feltétele,

• a ciklus törzsét.

Figyelem

A while esetén könnyen végtelen ciklust kaphatunk, nézzük meg és próbáljuk ki az alábbi kódot. Végtelen ciklus esetén a program kód soha nem áll le, ezért kézzel kell leállítani a futást. A futást cella oldalsó részében ⏹ gombra kattintva tudjuk megállítani.

i = 1
while i > 0:
  i = i + 1 

A break parancs

A break parancs segítségével kiugorhatunk while és for ciklus törzséből, így megszakítva a ciklust. Nézzük meg az alábbi kódot, mely 1-től 10-ig kiírja a számokat:

i = 0
while True:
  print(i)
  i = i + 1
  if i > 9:
    break

0
1
2
3
4
5
6
7
8
9

Vegyük észre, hogy a while ciklus feltétele mindig igaz, tehát végtelen ciklus lenne, azonban a break használatával kiugrunk a ciklusból, amikor az i változó értéke nagyobbá válik mint 9.

A break lehetővé teszi, hogy egy for ciklusból feltétellel ugorjunk ki, például az alábbi kódban, a ciklus 0-tól 100-ig menne, de a 6-ik iteráció után kilépünk:

for k in range(1, 100):
    print(k)
    if k > 5:
        break

1
2
3
4
5
6

Nézzük meg az alábbi példát, mely probléma gyakran előfodul a gyakorlatban:

cars = [{
  "brand": "Ford",
  "model": "Mustang",
  "year": 1964,
}, {
  "brand": "Ford",
  "model": "Focus",
  "year": 2018,
}]

for car in cars:
    if car['year'] == 2018:
        break

print(car)

{'brand': 'Ford', 'model': 'Focus', 'year': 2018}

A fenti példában az autókat egy szótárként reprezentáljuk, melynek különböző kulcsai vannak (brand, model és year). Ezen szótárak a car listában vannak. A kód megkeresi az első olyan autót, melynek a year kulcsához tartozó érték 2018.

Programozási tételek

A programozás során megoldandó algoritmikus feladatok gyakran nagyon hasonlóak. Az algoritmikus képességek fejlesztése érdekében érdemes néhány jól definiált megoldást megtanulni, melyeket ezután kis átalakítással más problémákra tudunk alkalmazni. Ezen általános algoritmusokat hívjuk programozási tételeknek, a folyamatot, melynek során egy tételt alkalmazzunk az adott problémára program transzformációnak nevezzük.

Az összegzés

• Feladat: Adjuk össze a számot a-tól b-ig.

• Bemenet: A tartomány kezdő és vég értéke: a, b

• Kimenet: A számok összege a bemenet alapján: s

s = 0                     # Az összegzés változója
for k in range(a, b):     # from, to a tartomány kezdő és záró eleme  
    s += k                # Az összegzés változójához hozzáadjuk az épp aktuális elemet
                          # A ciklus végén az s változó tartalmazza a számok összegét a és b között

Ezek után írjunk for ciklus ami összeadja a számokat 1-től 10-ig:

s = 0
for k in range(1, 11):
    s += k
print('Eredmény:', s)

Eredmény: 55

Feladat

Az összegzés programozási tételét használva, írjunk programot az alábbi problémák megoldására:

• Adjuk össze a páros számokat 50-ig!

• Írjunk egy ciklust amely kiszámítja a 8 faktoriálisát!

• Írjunk függvényt amely a sin függvény Taylor közelítését adja meg 3-ik fokszámig!

• Füzzük egy karakterlánccá a számokat 0-tól 10-ig! (eredmény: "1, 2, 3, 4, 5, 6, 7, 8, 9, 10")

Az összegzés megadható úgy, hogy egy lista elemein végezzük el a feladatot:

• Feladat: Adjuk össze egy list elemeit.

• Bemenet: Az l lista.

• Kimenet: Az l lista elemeinek az összege: s

s = 0                     # Az összegzés változója
for elem in l:            # Végig haladunk a lista minden egyes elemén
    s += elem             # Az összegzés változójához hozzáadjuk az épp aktuális elemet
                          # A ciklus végén az s változó tartalmazza a számok összegét a és b között

Nézzünk egy példát:

# Bemenet:
l = [5, 10, 8, 10, 2]

# Program
s = 0
for elem in l:
    s += elem

# Eredmény:
print('Eredmény:', s)

Eredmény: 35

Kiegészítő anyag

Vizsgáljuk meg az algoritmus futási idejét (komplexszítását). A komplexszítás alatt itt azt értjük, hogy a ciklus törzse hányszor fog végrehajtódni. Könnyen látható, hogy a ciklus törzse \(n\)-szer fog végrehajtódni, ahol \(n\) a list hossza. Ezt lineáris komplexszításnak nevezzük, mivel a list hosszának növelésével lineáris arányban fog megnőni a futási idő.

Feladat

Az összegzés programozási tételét használva, írjunk programot az alábbi problémák megoldására:

• Adott egy szövegeket tartalmazó lista. Fűzzük őket össze egyetlen szöveggé.

• Adott egy lista, mely távolságmérések eredményeit tartalmazza. Számoljuk ki a lista elemeinek átlagát és szórását.

A megszámlálás

• Feladat: Számoljuk egy adott elem hányszor fordul elő egy listában.

• Bemenet: A v elem és az l lista.

• Kimenet: Egy szám, mely megadja, hogy az adott elem hányszor fordul elő.

count = 0           # A változó melyben tároljuk az elem előfordulásának számosságát
for elem in l:      # Végig megyünk a list elemein
  if elem == v:     # Ha az épp aktuális elem megegyezik a keresettel, akkor...
    count += 1      # ... növeljük a számláló váltolzó értékét.
                    # Végül a count változó tartalmazza az előfordulás számosságát.

# Bemenetek:
l = [5, 10, 8, 10, 2]
v = 10

# Program:
count = 0
for elem in l:
  if elem == v:   
    count += 1

# Eredmény kiírása:
print('Eredmény:', count)

Eredmény: 2

Feladat

A megszámlálást programozási tételét változtassuk megy úgy, hogy a program az alábbi problémákat oldja meg:

• Adott egy számokat tartalmazó lista. Számoljuk meg hány elem nagyobb mint 10!

• Adott egy számokat tartalmazó lista. Számoljuk meg hány elem nagyobb mint az előző elem!

• Adott egy lista, mely távolságmérések eredményeit tartalmazza. Ismert a távolságmérések szórása. Számoljuk meg hány darab durva hibás mérés van! Egy mérést akkor tekintünk durva hibás mérésnek, ha annak értéke nagyobb, mint a szórás háromszorosa (3 szigma szabály).

• Egy repülőgépről egy altiméter segítségével mérjük a földfelszín magasságát. Ahogy a repülőgép halad, a földfelszín magasságait egy listába gyűjtük, például: heights = [800, 812, 925, 810, 740, 700, 720, 752, 651]. Számoljuk meg hány darab hegycsúcs látszik az adatokból! Egy hegycsúcs, egy olyan elem a listában, melynek értéke nagyobb az előtte és az utána lévő értéknél.

Az eldöntés

• Feladat: Döntsük el, hogy egy adott v elem benne van-e a listában.

• Bemenet: A v elem és az l lista.

• Kimenet: Igaz érték, ha a v elem benne van a listában, és hamis különben.

A megoldás megadható for ciklussal is, azonban while ciklussal elegáns illetve didaktikai szempontból hasznosabb. Először bevezetünk egy változót, mellyel bejárjuk a list indexszeit. A while ciklus feltétlében két dolgot kell vizsgálnunk: azt hogy elértük-e már a lista végét, illetve, hogy megtaláltuk-e az elemet. Amennyiben még nem értük el a lista végét és a jelenlegi indexszen lévő elem nem a keresett elem, léptetjük a változót. A ciklus végén, ha az i változó értéke kisebb mint a list hossza akkor létezik az elem a listában, máskülönben nem létezik:

i = 0                             # Egy változó, mely a list elemein fog végig haladni
while i < len(l) and l[i] != v:   # Addig megyünk végig a listán, amíg nem értünk a végére, vagy megtaláltuk ez elemet
    i = i + 1                     # A ciklus törtzsében csupán a lista elemeit bejáró változót kell léptetni.
exists = i < len(l)               # Ha az i változó kisebb mint a list hossza, akkor találtunk egy elemet, máskülönben nem

Nézzünk egy példát:

# Bemenetek:
l = [10, 5, 8, 10, 2]
v = -6

# Algoritmus:
i = 0
while i < len(l) and l[i] != v:
    i = i + 1

# Eredmény:
print('Eredmény:', i < len(l))

Eredmény: False

Kiegészítő anyag

Vizsgáljuk meg az algoritmus futás idejét (komplexszítását), vagyis hányszor fog a ciklus törzse végrehajtódni. Vegyük észre, hogy az algoritmusnak nem feltétlenül kell a lista összes elemén végigmennie. A legjobb esetben, amikor a lista első eleme a keresett elem, akkor csak egy ciklus fog végrehajtódni. A legrosszabb esetben a keresett elem az utolsó, és ilyenkor minden elemen végig kell menni. Ha az átlagos futás időről beszélünk akkor, mondhatjuk, hogy átlagosan az algoritmus \(n/2\) ciklust fog végrehajtani, ahol \(n\) a list hossza.

A tétel for ciklussal a következő módon adható meg:

# Bemenetek
l = [10, 5, 8, 10, 2]
v = -6

# Program
exists = False
for elem in l:
    if elem == v:
        exists = True
        break

# Eredmény:
print('Eredmény:', exists)

Eredmény: False

Látható, hogy ebben a megoldásban szükségünk volt, egy exists változó bevezetésére, illetve 3 sor helyett, 5 soros lett a programunk.

Pythonban támogatja ennek a feladatnak a megoldását az in kulcsszó segítségével:

l = [10, 5, 8, 10, 2]
v = -6

found = v in l
print('Eredmény:', found)

Eredmény: False

Feladat

A eldöntés programozási tételét változtassuk megy úgy, hogy a program az alábbi problémákat oldja meg:

• Adott egy számokat tartalmazó lista. Döntsük el, hogy a lista tartalmaz-e negatív számot.

• Adott egy állat neveket szövegesen tartalmazó lista. Döntsük el, hogy a cica benne van-e a listában,

• Egy repülőgépről egy altiméter segítségével mérjük a földfelszín magasságát. Ahogy a repülőgép halad, a földfelszín magasságait egy listába gyűjtjük, például: heights = [800, 812, 0, 810, 740, 0, 720, 752, 651]. A 0-s érték hibás mérést jelent. Döntsük el, hogy a mérésein tartalmaznak-e hibás mérést.

• Adott egy lista, mely távolságmérések eredményeit tartalmazza. Ismert a távolságmérések szórása. Döntsük el, hogy van-e durva hibás mérésünk az eldöntés programozási tételét használva. Egy mérést akkor tekintünk durva hibás mérésnek, ha annak értéke nagyobb, mint a szórás háromszorosa (3 szigma szabály).

A kiválasztás

• Feladat: Adott egy lista és egy elem. Tudjuk hogy az elem benne van a listába, de szeretnénk megkapni, az elem indexszét.

• Bemenet: A v elem és az l lista.

• Kimenet: Az elem indexsze a listában: i

A megoldás megadható for ciklussal is, azonban while ciklussal elegáns, illetve didaktikai szempontból hasznosabb. A megoldás ötelete, hogy egy változó segítségével bejárjuk a listát, és a while ciklus feltételében megnézzük, hogy az adott elem, megegyezik-e a keresett elemmel. Ha nem, akkor a ciklus törzsében léptetjük a vátozót. Ha megegyezik a keresett elemmel, akkor kilépünk és a változó értéke tartalmazni fogja a keresett elem indexszét.

i = 0                             # Egy változó, mely a list elemein fog végig haladni
while l[i] != v:                  # A ciklus addig megy, amíg meg nem találjuk az egyik elemet
    i = i + 1                     # Az elemre mutató változó léptetése

Nézzünk egy példát:

# Bemenetek:
l = [5, 10, 8, 10, 2]
v = 10

# Program:
i = 0
while l[i] != v:
    i = i + 1

#Eredmény:
print('Eredmény:', i)

Eredmény: 1

Vegyük észre, hogy az algoritmus az első előfordulást fogja megadni.

Kiegészítő anyag

Az algoritmus futás ideje megegyezik az eldöntés algoritmusáéval.

Figyelem

A tétel azzal az előfeltételezéssel él, hogy a keresett elem benne van a listában. Így, ha nincs benne a listában hibát fogunk kapni.

l = [5, 10, 8, 10, 2]
v = -6

i = 0
while l[i] != v: # IndexError: list index out of range
    i = i + 1

A tétel for ciklussal a következő módon adható meg:

# Bemenetek:
l = [5, 10, 8, 10, 2]
v = 10

# Program:
for idx, elem in enumerate(l):
    if elem == v:
        break

#Eredmény:
print('Eredmény:', idx)

Eredmény: 1

Ez a kód is 3 soros, azonban bonyolultabb, mivel az enumerate használatát igényli.

Pythonban támogatja ennek a feladatnak a megoldását az index függvényen keresztül:

l = [5, 10, 8, 10, 2]
print('Eredmény:', l.index(10))

Eredmény: 1

Figyelem

A tétel azzal az előfeltételezéssel él, hogy a keresett elem benne van a listában, ezért a Python verzió esetén is hibát kapunk, ha nem létező elem indexszét szeretnénk megkapni:

l = [5, 10, 8, 10, 2]
print(l.index(-6)) # ValueError: -6 is not in list

Feladat

A kiválasztás programozási tételét alakítsuk át úgy, hogy a program az alábbi problémákat oldja meg:

• Egy listában adjuk meg az első negatív elem indexszét, ha tudjuk hogy van ilyen elem a listában.

• Egy listában adjuk meg a második negatív elem indexszét, ha tudjuk hogy van ilyen elem a listában.

• Egy listában adjuk meg az utolsó negatív elem indexszét, ha tudjuk hogy van ilyen elem a listában.

• Adott egy állat neveket szövegesen tartalmazó lista. Adjuk meg cica szöveg inexszét a listában, ha tudjuk, hogy van ilyen lista elem.

A keresés

• Feladat: Döntsük el, hogy egy adott v elem benne van-e a listában, és ha benne van, adjuk meg annak indexszét.

• Bemenet: A v elem és az l lista.

• Kimenet: Az algoritmusnak két kimenete van: létezik-e az elem a listában, és ha igen, akkor melyik indexszű helyen.

Az algoritmus meg fog egyezni az eldöntés algoritmusával, hiszen ha az elem létezik, azzok a változó, mellyel bejárjuk a listát arra az indexszre fog mutatni, amely a keresett elem:

i = 0                             # Egy változó, mely a list elemein fog végig haladni
while i < len(l) and l[i] != v:   # Addig megyünk végig a listán, amíg nem értünk a végére, vagy megtaláltuk ez elemet
    i = i + 1                     # A ciklus törtzsében csupán a lista elemeit bejáró változót kell léptetni.

if i < len(l):                    # Ha az i változó kisebb mint a list hossza, akkor találtunk egy elemet,
    index = i                     # ... és az elem indexsze az i-ben van

Nézzünk egy példát:

# Bemenetek:
l = [5, 10, 8, 10, 2]
v = 10

# Program:
i = 0                             
while i < len(l) and l[i] != v:   
    i = i + 1

# Kimenetek:
print('Az elem a listában van? ', i < len(l))
if i < len(l):
    print('Az elem indexe: ', i)

Az elem a listában van?  True
Az elem indexe:  1

Ebben az esetben is az első előfordulás indexszét kaptuk meg.

A tétel for ciklussal a következő módon adható meg:

# Bemenetek:
l = [5, 10, 8, 10, 2]
v = 10

# Program:
found = False
for idx, elem in enumerate(l):
  if (elem == v):
    found = True
    break

# Kimenetek:
print('Az elem a listában van: ', found)
if found:
    print('Az elem indexe: ', idx)

Az elem a listában van:  True
Az elem indexe:  1

Feladat

Az autókat egy szótár reprezentál brand, model és year kulcsokkal. Egy példát láthatunk alább. Adjunk algoritmust a keresés algortimusának használatával, mely a következő feladatokat oldja meg. Szabadon használhatjuk a for vagy while verziót:

• Keressünk meg egy Ford típusú autót.

• Keressünk meg egy Ford típusú autót, és írjuk ki annak a modeljét.

• Keressük meg egy autót ami öregebb mint 1990.

• Keressük meg az utolsó autót, amely Ford.

cars = [{
  "brand": "Ford",
  "model": "Mustang",
  "year": 1964,
}, {
  "brand": "Ford",
  "model": "Focus",
  "year": 2018,
}]

A maximum kiválasztás

• Feladat: Adjuk meg a legnagyobb elemet egy listában.

• Bemenet: Az l lista.

• Kimenet: Az algoritmusnak kimenete a legnagyobb elem értéke.

A megoldásban először létrehozunk egy változót, amiben a maximális elemet tároljuk. Ezután a végig megyünk a listán, és ha találunk egy elemet ami nagyobb mint az épp aktuális maximális elem, akkor felülírjuk azt a jelenlegi értékkel. Az bejárást követően a maximális értéket fogja tárolni a változó. Még egy kérdés, hogy hogy mi legyen a maximális értéket tartalmazó változó kezdő értéke: ennek egy olyan értéknek kell lennie, melynél bármilyen a listát tartalmazó érték nagyobb lehet. Ez egy számokat tartalmazó lista esetén például a negatív végtelen lehet. Ha a list üres, akkor a változó ezt az értéket fogja tartalmazni. Ha tudjuk, hogy a lista nem üres, akkor bármely elem, például az első elemet megadhatjuk mint kezdő értéket.

max_elem = float('-inf')    # A maximális elemet tároló változó kezdő értéke negatív végtelen
max_elem = l[0]             # Ha a lista nem üres, akkor az első index is használható mint kezdő érték
for elem in l:              # Végig megyünk a list elemein
    if elem > max_elem:     # Ha nagyobb az aktuális elem mint maximális elemet tároló kezdő értéke...
        max_elem = elem     # ... akkor felülírjuk.
                            # Végén a max_elem tartalmazza a legnagyobb elemet.

Nézzünk egy példát:

# Bemenet:
l = [5, 10, 8, 10, 2]

# Program:
max_elem = float('-inf')
for elem in l:
    if elem > max_elem:
        max_elem = elem

# Kimenet:
print('Eredmény:', max_elem)

Eredmény: 10

Gyakran van szükségünk arra, hogy a maximális elem indexszét kapjuk meg. Ezt matematikában a \(argmax(x)\) függvény ad meg.

• Feladat: Adjuk meg a legnagyobb elem indexszét egy listában. A lista nem üres.

• Bemenet: Az l lista.

• Kimenet: Az algoritmusnak kimenete a legnagyobb elem értékének indexsze.

A megoldásban először létrehozunk egy változót, amiben a maximális elem indexszét fogjuk tárolni. Tudjuk, hogy a lista nem üres, így legalább egy eleme van, ezért kezdőértékként a 0-t adhatjuk. Ezután a végig megyünk a listán az index használatával, ha találunk egy elemet, ami nagyobb mint az épp aktuális maximális elem, akkor felülírjuk az indexszet a jelenlegi értékkel:

max_idx = 0
for idx, elem in enumerate(l):
    if elem > l[max_idx]:
        max_idx = idx

Nézzünk egy példát:

# Bemenet:
l = [5, 10, 8, 10, 2]

# Program:
max_idx = 0
for idx, elem in enumerate(l):
    if elem > l[max_idx]:
        max_idx = idx

# Kimenet:
print('Eredmény:', max_idx)
print('Érték:', l[max_idx])

Eredmény: 1
Érték: 10

Feladat

A maximum kiválsztás programozási tételét alakítsuk át úgy, hogy a program az alábbi problémákat oldja meg:

• Adott egy lista számokkal. Adjuk meg a legkisebb elemet a listában.

• Adott egy lista számokkal. Adjuk meg a legkisebb pozitív elemet.

• Adott egy list mely szövegeket tartalmaz. Adjuk meg a leghoszabb szöveget a listában.

• Egy repülőgépről egy altiméter segítségével mérjük a földfelszín magasságát. Ahogy a repülőgép halad, a földfelszín magasságait egy listába gyűjtjük, például: heights = [800, 812, 925, 810, 740, 700, 720, 752, 651]. Egy hegycsúcs, egy olyan elem a listában, melynek értéke nagyobb az előtte és az utána lévő értéknél. Adjuk meg a legmagasabb hegycsúcs magasságát!

Pythonban használhatjuk a min és max függvényeket, hogy megkapjuk egy lista legkisebb és legnagyobb elemét.

l = [5, 10, 8, 10, 2]
print('Legnagyobb elem: ', max(l))
print('Legkisebb elem: ', min(l))

Legnagyobb elem:  10
Legkisebb elem:  2