Programozási tételek II.

1. A minimumkiválasztás tétele

A minimumkiválasztás tétele segítségével egy adatsorozat legkisebb értékű elemét határozzuk meg.

A feladat lényege:

Végigvizsgáljuk az adatsorozat elemeit.
Kiválasztunk egy kezdőértéket minimumnak.
A többi elemet összehasonlítjuk az aktuális minimummal.
Ha kisebb elemet találunk, frissítjük a minimum értékét.
A feldolgozás végén megkapjuk a legkisebb elemet.

Mikor használjuk? Például:

Megkeressük egy osztály legrosszabb dolgozateredményét.
Meghatározzuk egy terméklista legolcsóbb termékét.
Meghatározzuk egy hét legalacsonyabb hőmérsékletét.

Konkrét példa

Adott az alábbi számsorozat:

12, 5, 18, 3, 9, 7

Határozzuk meg a legkisebb számot!

A feldolgozás lépései:

Először feltételezzük, hogy a lista első eleme a legkisebb: => minimum = 12

Ezután sorban összehasonlítjuk a többi elemmel.

Vizsgált elem	Aktuális minimum	Összehasonlítás	Új minimum
12	12	Kezdőérték	12
5	12	5 < 12	5
18	5	18 > 5	5
3	5	3 < 5	3
9	3	9 > 3	3
7	3	7 > 3	3

Az eredmény: 3

Az algoritmus általános felépítése

A minimumkiválasztásnál az egyik legfontosabb szabály, hogy a minimumváltozó kezdőértékének a lista első elemét választjuk.

Mindezt azért tesszük, mert nem tudhatjuk előre, hogy milyen értékek találhatók a listában. Ha például a minimumot 0-ra állítanánk, akkor egy kizárólag pozitív számokat tartalmazó listánál hibás eredményt kapnánk.

Pszeudokód:

Minimumkiválasztás:
    minimum := tömb[0]

    CIKLUS i = 1-től N-1-ig
        HA tömb[i] < minimum AKKOR
            minimum := tömb[i]
        ELÁGAZÁS VÉGE
    CIKLUS VÉGE

    KI: minimum
Minimumkiválasztás vége

Megvalósítás Python nyelven

szamok = [12, 5, 18, 3, 9, 7]

minimum = szamok[0]

for szam in szamok:
    if szam < minimum:
        minimum = szam

print("A legkisebb szám:", minimum)

Eredmény:

A legkisebb szám: 3

A program működése

Létrehozzuk a számlistát.
A minimum változóba eltároljuk a lista első elemét.
A for ciklussal végigmegyünk a lista elemein.
Minden elemet összehasonlítunk az aktuális minimummal.
Ha az aktuális elem kisebb, frissítjük a minimum értékét.
A ciklus végén kiírjuk a legkisebb számot.

Minimum meghatározása beépített függvénnyel

Pythonban létezik egy beépített függvény a legkisebb érték meghatározására. => min()

2. A maximumkeresés tétele

A maximumkeresés segítségével egy adatsorozat legnagyobb értékű elemét határozzuk meg.

Nagyon hasonlít a minimumkiválasztáshoz, de itt nem a legkisebb, hanem a legnagyobb értéket keressük.

A feladat lényege:

A lista első elemét tekintjük kezdeti maximumnak.
Végigvizsgáljuk a lista többi elemét.
Minden elemet összehasonlítunk az aktuális maximummal.
Ha nagyobb elemet találunk, frissítjük a maximum értékét.
A feldolgozás végén megkapjuk a legnagyobb elemet.

Mikor használjuk? Például:

Megkeressük egy osztály legjobb dolgozateredményét.
Meghatározzuk egy terméklista legdrágább termékét.
Meghatározzuk egy hét legmagasabb hőmérsékletét.

Konkrét példa

Adott az alábbi számsorozat:

12, 5, 18, 3, 9, 25, 7

Határozzuk meg a legnagyobb számot!

Kezdetben: maximum = 12

Ezután megvizsgáljuk a többi elemet.

Vizsgált elem	Aktuális maximum	Összehasonlítás	Új maximum
12	12	Kezdőérték	12
5	12	5 < 12	12
18	12	18 > 12	18
3	18	3 < 18	18
9	18	9 < 18	18
25	18	25 > 18	25
7	25	7 < 25	25

Az eredmény: 25

Az algoritmus általános felépítése

Pszeudokód:

Maximumkeresés:
    maximum := tömb[0]

    CIKLUS i = 1-től N-1-ig
        HA tömb[i] > maximum AKKOR
            maximum := tömb[i]
        ELÁGAZÁS VÉGE
    CIKLUS VÉGE

    KI: maximum
Maximumkeresés vége

Megvalósítás Python nyelven

szamok = [12, 5, 18, 3, 9, 25, 7]

maximum = szamok[0]

for szam in szamok:
    if szam > maximum:
        maximum = szam

print("A legnagyobb szám:", maximum)

Eredmény:

A legnagyobb szám: 25

A program működése

Létrehozzuk a listát.
A maximum változóba eltároljuk az első elemet.
Végigmegyünk a lista elemein.
Minden számot összehasonlítunk a jelenlegi maximummal.
Ha nagyobb számot találunk, frissítjük a maximumot.
A ciklus után kiírjuk a legnagyobb értéket.

Maximum meghatározása beépített függvénnyel

Pythonban a max() függvény segítségével is meghatározhatjuk a legnagyobb értéket.

Minimum és maximum együttes meghatározása

A két algoritmus akár egyetlen ciklusban is megvalósítható.

Feladat: Határozzuk meg egy lista legkisebb és legnagyobb elemét!

szamok = [12, 5, 18, 3, 9, 25, 7]

minimum = szamok[0]
maximum = szamok[0]

for szam in szamok:
    if szam < minimum:
        minimum = szam

    if szam > maximum:
        maximum = szam

print("Minimum:", minimum)
print("Maximum:", maximum)

Eredmény:

Minimum: 3
Maximum: 25

3. A kiválasztás tétele

A kiválasztás tétele segítségével megkeresünk egy olyan elemet egy adatsorozatban, amely megfelel egy adott feltételnek, és meghatározzuk annak helyét, vagyis indexét.

A legfontosabb különbség az eldöntés és a kiválasztás között:

Eldöntés: Csak arra vagyunk kíváncsiak, hogy létezik-e megfelelő elem.
Kiválasztás: Tudjuk, hogy létezik megfelelő elem, és meg szeretnénk határozni a helyét.

Mikor használjuk? Például:

Megkeressük, hogy egy listában melyik helyen található a 20-as szám.
Megkeressük egy dolgozatpontszám-listában az első 100 pontos eredmény helyét.
Meghatározzuk egy terméklista adott termékének indexét.

Konkrét példa

Adott a következő lista:

12, 5, 18, 3, 9, 25, 7

Feladat: Keressük meg, hogy hányadik helyen található a 18-as szám!

A lista indexei:

Index	Érték
0	12
1	5
2	18
3	3
4	9
5	25
6	7

A 18-as szám indexe: 2

📌 Fontos: A programozásban a lista indexelése általában 0-tól kezdődik, ezért a 18-as szám a 2-es indexen található, de emberi megfogalmazásban a harmadik elem.

Az algoritmus általános felépítése

A kiválasztásnál egy indexváltozóval követjük, hogy éppen melyik elemet vizsgáljuk.

Pszeudokód:

Kiválasztás:
    i := 0

    CIKLUS AMÍG tömb[i] nem felel meg a feltételnek
        i := i + 1
    CIKLUS VÉGE

    KI: i
Kiválasztás vége

A ciklus addig fut, amíg meg nem találjuk a megfelelő elemet.

Megvalósítás Python nyelven

szamok = [12, 5, 18, 3, 9, 25, 7]

i = 0

while szamok[i] != 18:
    i += 1

print("A keresett szám indexe:", i)
print("A keresett szám helye:", i + 1)

Eredmény:

A keresett szám indexe: 2
A keresett szám helye: 3

A program működése

Létrehozzuk a listát.
Az i változót 0-ra állítjuk.
Megvizsgáljuk a lista aktuális elemét.
Ha az aktuális elem nem 18, növeljük az indexet.
Ha megtaláltuk a 18-at, a ciklus leáll.
Kiírjuk az indexet és az emberi értelemben vett sorszámot.

Miért a while ciklust használtuk?

A kiválasztásnál nem feltétlenül tudjuk előre, hogy hányadik helyen található a keresett elem.

Ezért célszerű olyan ciklust használni, amely addig ismétlődik, amíg a keresett feltétel nem teljesül.

4. A keresés tétele

A keresés tétele segítségével megvizsgáljuk, hogy egy adatsorozatban megtalálható-e egy adott feltételnek megfelelő elem.

Ha megtaláljuk, meghatározzuk annak helyét is.

Ha nem találjuk meg, akkor ezt is jelezzük.

A keresés tehát az eldöntés és a kiválasztás egyfajta kombinációja.

A keresés eredménye:

Ha megtaláltuk az elemet: a keresett elem indexe.
Ha nem találtuk meg: jelzés arról, hogy nincs ilyen elem.

Mikor használjuk? Például:

Megkeressük egy tanuló nevét az osztálynévsorban.
Megkeresünk egy adott számot egy listában.

Konkrét példa

Adott a következő lista:

12, 5, 18, 3, 9, 25, 7

Feladat: Keressük meg a 9-es szám helyét!

A lista elemeit sorban vizsgáljuk:

Index	Aktuális elem	Megfelel a feltételnek?
0	12	Nem
1	5	Nem
2	18	Nem
3	3	Nem
4	9	Igen

A 9-es szám indexe: 4

Mi történik, ha a keresett szám például 100!

A program végigvizsgálja a listát, de nem talál megfelelő elemet.

Ebben az esetben azt kell jeleznie, hogy a szám nem szerepel a listában.

Az algoritmus általános felépítése

A keresésnél szükségünk van:

Egy indexváltozóra.
Egy logikai változóra, amely jelzi, hogy találtunk-e megfelelő elemet.

Pszeudokód:

Keresés:
    i := 0
    van := HAMIS

    CIKLUS AMÍG i < N ÉS van = HAMIS
        HA tömb[i] megfelel a feltételnek AKKOR
            van := IGAZ
        KÜLÖNBEN
            i := i + 1
        ELÁGAZÁS VÉGE
    CIKLUS VÉGE

    HA van = IGAZ AKKOR
        KI: i
    KÜLÖNBEN
        KI: NINCS TALÁLAT
    ELÁGAZÁS VÉGE
Keresés vége

Megvalósítás Python nyelven

szamok = [12, 5, 18, 3, 9, 25, 7]

keresett = 9

i = 0
van = False

while i < len(szamok) and not van:
    if szamok[i] == keresett:
        van = True
    else:
        i += 1

if van:
    print("A keresett szám indexe:", i)
    print("A keresett szám helye:", i + 1)
else:
    print("A keresett szám nem szerepel a listában.")

Eredmény:

A keresett szám indexe: 4
A keresett szám helye: 5

Mi történik, ha nincs találat?

Próbáljuk ki a programot a 100-as számmal!

szamok = [12, 5, 18, 3, 9, 25, 7]

keresett = 100

i = 0
van = False

while i < len(szamok) and not van:
    if szamok[i] == keresett:
        van = True
    else:
        i += 1

if van:
    print("A keresett szám indexe:", i)
else:
    print("Nincs ilyen szám a listában.")

Eredmény:

Nincs ilyen szám a listában.

Keresés Python beépített függvénnyel

Pythonban a lista index() metódusa segítségével is megkereshetjük egy elem helyét.

szamok = [12, 5, 18, 3, 9, 25, 7]

keresett = 9

if keresett in szamok:
    index = szamok.index(keresett)
    print("A keresett szám indexe:", index)
else:
    print("Nincs ilyen szám a listában.")

Fontos:

Az in operátor ellenőrzi, hogy az elem szerepel-e a listában.
Az index() metódus visszaadja az első előfordulás indexét.
Ha az elem nincs a listában, az index() kivételt okoz. Ezért ellenőrzés nélkül nem célszerű meghívni.

5. A négy programozási tétel összehasonlítása

A minimumkiválasztás, maximumkeresés, kiválasztás és keresés elsőre nagyon hasonlónak tűnhet, de más-más feladatot oldanak meg.

Tétel	Feladata	Eredménye
Minimumkiválasztás	Legkisebb érték meghatározása	Minimumérték
Maximumkeresés	Legnagyobb érték meghatározása	Maximumérték
Kiválasztás	Egy biztosan létező, megfelelő elem megkeresése	Index
Keresés	Egy esetlegesen létező, megfelelő elem megkeresése	Találat és index vagy nincs találat

Hogyan ismerjük fel, melyik tételt kell alkalmazni?

Feladatban szereplő kérdés	Alkalmazandó tétel
Melyik a legolcsóbb termék?	Minimumkiválasztás
Melyik a legmagasabb pontszám?	Maximumkeresés
Hol található az első 100 pontos eredmény, ha biztosan van ilyen?	Kiválasztás
Szerepel-e a keresett termék, és ha igen, hol?	Keresés
Melyik a leghidegebb nap?	Minimumkiválasztás
Melyik napon volt a legnagyobb bevétel?	Maximumkeresés

Fontos megkülönböztetés

A kiválasztás és a keresés közötti legfontosabb különbség:

Kiválasztás: Tudjuk, hogy létezik megfelelő elem.
Keresés: Nem tudjuk, hogy létezik-e megfelelő elem, ezért a hiányzó találatot is kezelnünk kell.

6. A négy tétel legfontosabb mintakódjai

1. Minimumkiválasztás

minimum = lista[0]

for elem in lista:
    if elem < minimum:
        minimum = elem

2. Maximumkeresés

maximum = lista[0]

for elem in lista:
    if elem > maximum:
        maximum = elem

3. Kiválasztás

i = 0

while lista[i] != keresett:
    i += 1

Feltétel: biztosan létezik megfelelő elem.

4. Keresés

i = 0
van = False

while i < len(lista) and not van:
    if lista[i] == keresett:
        van = True
    else:
        i += 1

if van:
    print("Találat:", i)
else:
    print("Nincs találat.")

7. Gyakori hibák, amelyekre érdemes figyelni

Hiba	Miért probléma?	Helyes megoldás
A minimum kezdőértéke 0.	Pozitív számoknál hibás lehet.	`minimum = lista[0]`
A maximum kezdőértéke 0.	Negatív számoknál hibás lehet.	`maximum = lista[0]`
Minimumkeresésnél `>` szerepel `<` helyett.	Nem a kisebb elemet választjuk.	`if elem < minimum`
Maximumkeresésnél `<` szerepel `>` helyett.	Nem a nagyobb elemet választjuk.	`if elem > maximum`
Kiválasztásnál nincs létezési garancia.	Indexelési hiba keletkezhet.	Biztosítani kell, hogy legyen találat.
Keresésnél nincs indexhatár-ellenőrzés.	A lista végén indexelési hiba keletkezhet.	`i < len(lista)`
Keresésnél elmarad az index növelése.	Végtelen ciklus keletkezhet.	`i += 1`
Az indexet és a sorszámot összekeverjük.	Egy hellyel eltérő eredményt kapunk.	Index: `i`, sorszám: `i + 1`

8. Összefoglalás – A négy programozási tétel egy táblázatban

Tétel	Mit csinál?	Kezdőérték	Eredmény
Minimumkiválasztás	Megkeresi a legkisebb elemet	Első elem	Minimum
Maximumkeresés	Megkeresi a legnagyobb elemet	Első elem	Maximum
Kiválasztás	Megkeresi a biztosan létező megfelelő elemet	`i = 0`	Index
Keresés	Megkeresi az esetlegesen létező megfelelő elemet	`i = 0`, `van = False`	Index vagy nincs találat

Jegyezd meg!

Minimum: Melyik a legkisebb?
Maximum: Melyik a legnagyobb?
Kiválasztás: Hol van a biztosan létező elem?
Keresés: Van-e ilyen elem, és ha igen, hol?