C++ programozás 15. – Alap algoritmusok

Alap algoritmusok, avagy mindenki tud programozni

A programozással sokszor az a baj – főleg ha kötelező tantárgy és nem szeretjük – hogy gondolkodni kell. Igaz, mondhatnám ezt a matematikára, fizikára is, de egyik tantárgy sem annyira szerteágazó a helyes megoldások tekintetében, mint a programozás. Itt ugyanazt a problémát sokféleképp meg lehet oldani, és minden megoldás helyes. Mégis, a megoldások között az árnyalatnyi különbségek azok, amelyek eldöntik azt, hogy helyes-e a megoldás, vagy sem.

Bármilyen bonyolult programot veszünk szemügyre és bontunk részekre, a végén ugyanaz a 4 építőelem marad:

  1. szekvencia (utasítások egymás utáni sorozatának végrehajtása)
  2. változóhasználat
  3. elágazások
  4. ciklusok

A sorrend nem véletlen, ebben a sorrendben kell ezeket megtanulni használni, mert ezek egymásra épülő darabok a programozásnak nevezett kirakó játékban. Ha nem az építőelemeit nézzük a programoknak, akkor is találhatunk olyan sablonokat, olyan már tanult megoldásokat, amelyek újra és újra előfordulnak a programjainkban. Ezeket a sablonokat, kész megoldásokat nevezzük programozási tételeknek.

Ezek valójában betanulható kész algoritmusok, melyek egy adott problémára kész megoldást adnak. Nem mindig fordulnak elő tiszta formában, vagyis néha apró változtatásokra szükség van, hogy ezeket az algoritmusokat egy adott feladathoz igazítsuk, de ha ezeket ismerjük és biztosan használjuk, akkor sokféle programozási feladatot meg tudunk oldani.

Ezek az alap algoritmusok tömbökhöz kapcsolódnak, vagyis sok egyforma adattal végeznek valamit. Megkeresik egy tömbből a legnagyobb értéket, sorba rendezik a számokat, eldöntik, hogy benne van-e egy adott érték a tömbben, megadják két halmaz metszetét, stb. Lássunk akkor néhány alap algoritmust:

  1. Megszámlálás
  2. Összegzés
  3. Eldöntés
  4. Kiválasztás
  5. Keresés
  6. Minimum/maximum keresés
  7. Rendezés
  8. Kiválogatás
  9. Szétválogatás (hiányzik)
  10. Metszet (hiányzik)
  11. Unió (hiányzik)

Ezen algoritmusok mindegyikére igaz, hogy ciklusokhoz kapcsolódnak, hiszen ha tömbökkel dolgozunk, akkor mindenképpen ciklusra van szükség, hogy az elemeket egyenként megvizsgálhassuk, összehasonlíthassuk, stb. Ezek az algoritmusok kicsit leegyszerűsítik a programozást, hiszen ezekkel a megtanulható kész receptekkel sokféle feladatot megoldhatunk. A probléma az, hogy a feladatban fel kell ismerni, hogy valójában mit is akarunk eredményként megkapni, és az melyik algoritmusnak felel meg. Ha ez megvan, onnantól szinte csak gépelési feladattá sikerült egyszerűsíteni a programozási feladatot.

Az alap algoritmusok valamennyi fajtájához létezik pszeudokód, olyan általános leírás, amely programozási nyelvtől független. Ráadásul, mivel 3 fajta ciklus létezik, ezért alapból szerteágazó megoldásokat adhatunk ugyanarra a feladatra. Az alap algoritmusokat nagyon sok helyen ugyanazzal a megoldási formával adják meg, és biztos vagyok benne, hogy több tanár csak így fogadja el megoldásként. Én azt vallom, hogy bármilyen jó megoldás elfogadható, a lényeg, hogy a diák alkalmazni tudja azt, amit tanult. Léteznek lecsupaszított, hatékony és egyszerű megoldások, de sokszor én sem azt alkalmazom, mert nem írunk olyan szintű programokat, hogy ennyire optimalizált és gyors algoritmusra lenne szükség. Aki esetleg az alap algoritmusaimban hibát talál, mondván, hogy ő ezt nem így tanulta, az nem feltétlenül hiba, egyszerűen más a megoldás. Az példáknál sok helyen kész ténynek veszem azt, hogy rendelkezésre áll az a tömb a megfelelő adatokkal, amelyekkel dolgozni kell. Ezeknek a tömböknek a feltöltésével, ellenőrzésével nem foglalkozok. Vegyük akkor sorra ezeket az algoritmusokat:

Megszámlálás

Kezdjük valami egyszerűvel. Az alapfeladat az, hogy számoljuk meg, hogy egy adott tömbben hány darab adott tulajdonságú elem van. Ez jelentheti azt is, hogy nincs ilyen tulajdonságú elem a tömbben, akkor a darabszám nyilván 0. Ennél a feladatnál minden esetben végig kell menni a tömbön, hiszen minden elemről meg kell állapítanom, hogy rendelkezik-e a tulajdonsággal, vagy sem. Mivel megszámolunk, ezért valahol tárolnom kell, hogy éppen hol járok a számolásban, hány olyat találtam, ami megfelelt a feltételemnek. Ehhez szükség van egy úgynevezett gyűjtőváltozóra. Az adott algoritmus egy darabszámot ad eredményül minden esetben, ami a [0;méret] intervallumban lesz, vagyis lehet, hogy egy elem sem felel meg a feltételnek, de az is előfordulhat, hogy mindegyik. Nézzünk pár példát, hogy mikor alkalmazható ez az algoritmus:

  • Hány 180 cm-nél magasabb diák jár az osztályba?
  • Hány napon esett az eső tavaly?
  • Hány férfi tanár tanít az iskolában?

Láthatjuk, hogy minden esetben egy darabszámra kíváncsi minden kérdés. Lássuk akkor azt az algoritmust, ami ezekre a kérdésekre választ ad. A példában az első kérdésre keressük a választ.

int szamlalo = 0;

for( int i = 0; i < meret; i++ )
{
    if( tomb[i] > 180 )
    {
        szamlalo = szamlalo + 1;
    }
}

cout << "Az osztalyba " << szamlalo << " db 180 cm-nel "
                   "magasabb diak jar." << endl;

Nézzük akkor részletesebben, mi történik.

  • 1- Deklarálunk egy gyűjtőváltozót, ahol a feltételnek megfelelő elemek darabszámát tároljuk. A gyűjtőváltozót 0 kezdőértékre állítjuk be. Ez egyébként általános szabály, hogy minden gyűjtőváltozót legkésőbb a használata előtt (a ciklus előtt) nullázni kell!
  • 3- Indítunk egy ciklust, ami a tömb összes elemén végigmegy.
  • 5- Megvizsgáljuk, hogy az adott elem megfelel-e a feltételnek
  • 7- Ha megfelel, a számlálót eggyel megnöveljük.
  • A ciklus után kiírjuk az eredményt.

A kiemelt sorban a változó növelését kicserélhetjük a már tanult inkrementáló operátorra. Azért, mert lusták vagyunk, és nem akarunk sokat gépelni 🙂

szamlalo = szamlalo + 1;
// helyett
szamlalo++;

A többi feladatnál gyakorlatilag ugyanezt kell begépelni, igazából az egyetlen dolog ami változik az maga a feltétel, ami alapján megszámolunk.

Összegzés

Az összegzés tétele kísértetiesen hasonlít a megszámlálásra. Egyetlen különbség van csak, a gyűjtőváltozó növelése. A feladatok is hasonlóak, de az összegzés csak számszerű adatokra vonatkozik. Néhány példa ilyen kérdésekre:

  • Mennyi a tömbben található páros számok összege?
  • Mennyi a negatív számok összege?
  • Mennyi a páratlan számok átlaga?

Lássuk akkor mondjuk az első megoldását:

int osszeg = 0;

for( int i = 0; i < meret; i++ )
{
    if( tomb[i] % 2 == 0 )
    {
        osszeg = osszeg + tomb[i];
    }
}

cout << "A tombben levo paros szamok osszege: " << osszeg << endl;

Láthatjuk, hogy az összegzés algoritmusa szinte ugyanaz, mint a megszámlálásé.

  • 1- Deklarálunk egy gyűjtőváltozót, ahol a feltételnek megfelelő elemek összegét tároljuk. A gyűjtőváltozót 0 kezdőértékre állítjuk be.
  • 3- Indítunk egy ciklust, ami a tömb összes elemén végigmegy.
  • 5- Megvizsgáljuk, hogy az adott elem megfelel-e a feltételnek
  • 7- Ha megfelel, az összeghez hozzáadjuk az aktuális elemet.
  • 11 – A ciklus után kiírjuk az eredményt.

A lényegi különbséget kiemeltem. Látható, hogy szinte ugyanaz. Ettől függetlenül ne keverjük a két algoritmust, mert teljesen más a feladatuk!

A kiemelt sorban a változó növelését kicserélhetjük már tanult összeadással kombinált értékadó operátorra. Ismét csak azért, mert lusták vagyunk, és nem akarunk sokat gépelni.

osszeg = osszeg + tomb[i];
// helyett
osszeg += tomb[i];

A harmadik feladat kilóg a többi közül, ez nem csak tiszta összegzés. Itt egyszerre kell az előzőleg ismertetett megszámlálást és összegzést elvégezni. Szükségünk van a páratlan számok összegére, valamint a darabszámára is az átlagoláshoz:

int osszeg = 0;
int db = 0;

for( int i = 0; i < meret; i++ )
{
    if( tomb[i] % 2 != 0 )
    {
        osszeg = osszeg + tomb[i];
        db++;
    }
}
double atlag = (double)osszeg/db;
cout << "A tomb paratlan szamainak atlaga: " << atlag << endl;

Láthatjuk, hogy a ciklussal ugyanúgy végigmegyünk az egész tömbön. Ha találunk egy megfelelő számot, akkor hozzáadjuk az összeghez és növeljük a darabszámot is, hogy azt a kódban kiemeltem. Az átlag már csak egy osztás. De nem egyszerű osztás. Az osszeg és db változók egész típusok. Mi lenne az eredménye annak, ha mondjuk az összeg 11 a darabszám pedig 5? 11/5 = mennyi?

Ne felejtsd el! Ha két egész számot osztunk egymással, az egész osztás! Az eredmény nem a sokszor várt 2,2 lenne, hanem 2,0. Az osztás akkor nem egész osztás, ha legalább az egyik műveletben részt vevő szám nem egész. A példában már mutattam egy trükköt, de írhatnánk így is:

osszeg/(db+0.0)

A darabhoz ha hozzáadunk egy valós számot, akkor annak az eredménye már valós lesz, így az osztásban megjelennek a tizedesjegyek is.

Helyette azonban legyünk elegánsabbak, használjunk típuskényszerítést, amit a véletlen számok témakörben már bemutattam:

(double)osszeg/db

A típuskényszerítés során az összeg változóból kiolvasott értéket lebegőpontos számmá alakítjuk, majd osztjuk egy egésszel. Ennek eredménye már megfelelő: 2,2.

Fontos, hogy ez a típuskényszerítés nem az eredeti összegváltozóban tárolt értéket változtatja meg, nincs értékadás! Nem is változtathatja meg az összegváltozó tartalmát, mivel annak típusa egész. Csak a változóból felhasznált értékét alakítja át a megadott típusra.

Eldöntés

Ennél a feladattípusnál azt vizsgáljuk, hogy egy tömbben található-e egy bizonyos tulajdonságú elem. Nem érdekel, hogy hány ilyen elem van, csak az a fontos, hogy van-e benne ilyen. Itt logikai eredményt kapunk, vagyis a válasz igaz vagy hamis lehet. Lássunk pár példát olyan kérdésekre, amelyekre ezzel az algoritmussal kaphatunk választ:

  • Van-e az osztályban lány?
  • Van-e az osztályban 190 cm-nél magasabb diák?
  • Volt-e melegebb 38 foknál tavaly nyáron?
  • Van-e 30 évnél fiatalabb tanár az iskolában?

Ezekhez a feladatokhoz természetesen szükség van tömbökre, melyek azokat az adatokat tárolják, amelyek között keressük azt a bizonyos tulajdonságú elemet, azok közül is a legelsőt. Emlékezz, nem érdekel hány ilyen elem van, csak az számít, hogy van-e ilyen, és ez nyilván a legelső megtalált elem lesz. Az első példához szükség van egy tömbre, amely a tanulók nemét tárolja, akár logikai típusként (lány – true, fiú – false). A második esetben kell egy tömb, ami az osztályba járó diákok magasságait tartalmazza, a harmadikban egy tömb, ami a nyári napok maximum hőmérsékletét tartalmazza, a negyediknél egy tömb, amiben benne van az iskolában tanító tanárok életkora. Maradjunk a második példánál, és vegyük úgy, hogy rendelkezésre áll egy „tomb” nevű tömb, ami az osztályba járó diákok magasságait rögzíti.

int i = 0;

while( i < meret && !(tomb[i] > 190) )
{
    i++;
}

if( i < meret )
{
    cout << "Van az osztalyban 190 cm-nel magasabb diak." << endl;
}

Na de mit is csinál ez pontosan?

  • 1 – Először deklarálunk egy ciklusváltozót, amit arra fogunk használni, hogy indexelhessünk (hivatkozhassunk) az egyes tömbelemekre, jelen esetben a diákok magassági adataira. Ez a sorszám természetesen 0-tól indul, mert a Java nyelvben a tömbök indexei 0 számmal kezdődnek.
  • 3 – Aztán indítunk egy ciklust, melynek az a feladata, hogy végigmehessünk egyenként a tömb elemein. A ciklus feje viszont egy összetett feltételt tartalmaz. Ennek első fele azt vizsgálja, hogy végigértünk-e már a tömbön – vagyis, hogy az index kisebb-e, mint a tömb mérete. Ha az i egyenlő lenne a tömbmérettel, az már azt jelentené, hogy túljutottunk az utolsó elemen, tehát a ciklus megáll. Mivel a tömbök indexe 0-val kezdődik, ebből következik, hogy az utolsó elem indexe tömbméret-1. A feltétel másik része a tulajdonság vizsgálat, amelyre csak akkor kerül sor, ha még nem értünk a tömb végére. Ezzel kihasználjuk a logikai rövidzár lehetőségét. Itt azt vizsgáljuk, hogy a tomb[i] – vagyis az aktuális diák magassága – NEM RENDELKEZIK a keresett tulajdonsággal. Ez fura, nem pont ennek a fordítottját keressük? De igen, ez az algoritmus lényege. Addig kell keresni, amíg NEM találtuk meg, amit kerestünk, hiszen ha megvan, akkor megállhatunk. Ha ez a két feltétel egyszerre igaz (nem értünk még a tömb végére ÉS nem rendelkezik az aktuális diák a keresett tulajdonsággal), akkor lépünk be a ciklusba, ami semmi mást nem csinál, csak lépteti a számlálót, vagyis jöhet a következő vizsgálandó diák. Az algoritmus nagyon fontos része az, hogy a ciklus két feltételének sorrendje kötött! Először kell azt vizsgálni, hogy nem értünk-e a végére, és ha nem, csak akkor szabad megvizsgálni, hogy az aktuális elem nem rendelkezik-e a keresett tulajdonsággal. Hiszen ha már végignéztük a tömböt, akkor már nincs mit vizsgálni.
  • 8 – A ciklus befejeződése után már csak értelmeznünk kell a kapott eredményt. Az i változó értéke az, ami a megoldást tartalmazza. Ha találtunk olyan diákot, aki rendelkezett a keresett tulajdonsággal, akkor a ciklus idő előtt megállt, vagyis az i értéke kisebb, mint a tömb mérete. Ha egyetlen diák sem volt 190 cm-nél magasabb, akkor a ciklus azért állt meg, mert az i változó már nem kisebb a tömb méreténél (vagyis egyenlő), tehát nem találtunk olyat, aki a feltételnek megfelelt volna.

Természetesen a többi feladatra is hasonló a megoldás, lássuk mondjuk a negyedik feladatot:

int i = 0;

while( i < meret && tomb[i] >= 30 )
{
    i++;
}

if( i < meret )
{
    cout << "Van az iskolaban 30 evnel fiatalabb tanar." << endl;
}

Nagyon fontos eleme tehát az eldöntésnek, hogy második részfeltételnek azt adjuk meg, hogy az aktuális elem a keresett tulajdonsággal nem rendelkezik! Mivel a feltételek többsége relációt tartalmaz, itt a relációk ellentettjét kell használni!

// 30 évnél fiatalabbat keresünk
while( ... && tomb[i] < 30 )

helyett

// 30 évnél nem fiatalabb kell a feltételbe
while( ... && tomb[i] >= 30 )

Írhatnám úgy is, hogy valóban tagadom az eredeti állítást:

// 30 évnél nem fiatalabb
while( ... && !(tomb[i] < 30)

Az eredeti állítás valódi tagadását tomb[i] < 30 -> !( tomb[i] < 30) én inkább a reláció ellentettjével helyettesíteném, mivel ott egy reláció marad csak, így csak egy műveletet kell végrehajtani. Valódi tagadás esetén ott marad az eredeti reláció, majd a reláció logikai értékének tagadása is kell, ami két művelet, de ezekből az egyik megspórolható.

Itt visszautalnék a relációs operátoroknál arra a táblázatra, ahol ismertettem a relációk tagadásait. Ne feledd: a kisebb tagadása nem a nagyobb!

Mi az, amit még észrevehettél ebben az algoritmusban? Ezzel vissza is kanyarodtunk egy nagyon fontos részhez, a logikai kifejezéseknél. Láthatod, hogy a while ciklus fejében egy összetett kifejezés szerepel. Ennek az első fele az, hogy elértünk-e már a tömb végéig, a második pedig az, hogy az aktuális elem nem rendelkezik a keresett tulajdonsággal. Látható, hogy a második feltétel kész tényként veszi azt, hogy ott csak valódi elemet vizsgálhatok. Egy tömbnek, ha emlékszel, fix tulajdonsága a mérete. Vagyis csak akkora indexet lehet használni, amilyen elem még szerepel a tömbben. Egy 10 elemű tömbben nem lehet pl a tomb[12] elemre hivatkozni, mert ilyen elem nem létezik.

Ez futási hibát eredményez. Na de itt hol ellenőrzöm azt, hogy nehogy túl nagy indexet használjak? Az első feltételben. Ez egy logikai rövidzár. Ha az első részfeltétel, hogy az i számláló kisebb, mint a tömbméret (vagyis az i lehet a tömb egy indexe) teljesül, csak akkor vizsgálja meg a második részfeltételt, az adott elem keresett tulajdonságának hiányát. Ha az i elérte a tömbméretet (vagyis nem kisebb), akkor a logikai rövidzár miatt a második feltételt logikai és esetén már meg sem vizsgálja. Nem fog olyan elemet vizsgálni, ami nem létezik! Nagyon fontos eleme az algoritmusnak az, hogy a két részfeltételnek pontosan ilyen sorrendben kell szerepelnie, mert így oldja meg a rövidzár azt az ellenőrzést is, hogy csak valódi emelet vizsgáljunk meg, és ne kapjunk futási hibát.

Kiválasztás

Ezzel az algoritmussal azt adhatjuk meg, hogy egy adott elem pontosan hol szerepel a tömbben. Ez természetesen az adott elem indexét jelenti, amellyel a tömbben hivatkozunk rá. Ez az algoritmus feltételezi azt, hogy az elem tényleg benne van a tömbben, ez ugyanis nem keverendő össze a keresés algoritmusával, amit következőként fogok ismertetni. Lássunk erre egy pár kérdést.

  • Válasszuk ki a tömbből az 50-es számot (nem index, hanem érték!).
  • Hányadik a sorban az a diák, akinek a magassága 190 cm-nél nagyobb.

Lássuk az első példa megoldását:

int i = 0;

while( tomb[i] != 50 )
{
    i++;
}

cout << "Az 50-es szám indexe: " << i << endl;

Ha megnézzük, ez egy lecsupaszított eldöntés algoritmusnak tűnik, amikor ciklusban működési feltételként furcsa módon azt adjuk meg, hogy a ciklus addig menjen, amíg az aktuális elem NEM rendelkezik a tulajdonsággal. Vagyis addig megyünk, amíg meg nem találjuk. Hiányzik viszont a eldöntéses algoritmus összetett feltételének első része, ami azt vizsgálja, hogy túlszaladtunk-e a tömb végén. Itt erre nincs is szükség, mivel abból indultunk ki, hogy a kiválasztandó elem biztosan benne van a tömbben.

Kiválasztásnál lehetséges, hogy több elem is megfelel a feltételnek, ez az algoritmus a legelső olyan elemet választja ki, akire a feltételünk igaz lesz. Viszonylag könnyen megoldható az is, hogy a legutolsó olyat válasszuk ki, ez csak a ciklus haladási irányától és az i kezdőértékétől függ.

Keresés

A keresés algoritmusa gyakorlatilag szinte ugyanaz, mint az eldöntés algoritmusa, mindössze az i változó ciklus utáni értelmezésénél van különbség. Azért szerepeljen itt újra az algoritmus egy konkrét példával. A feladatban azt keressük, hogy van-e 190 cm-nél magasabb diák és hogy ő hányadik a tömbben:

int i = 0;

while( i < meret && tomb[i] <= 190 )
{
    i++;
}

if( i < meret )
{
    cout << "A 190 cm-nél magasabb diák helye: " << i << endl;
}
else
{
    cout << "Nincs ilyen diák." << endl;
}

Látható az, hogy ez biztonságosabb algoritmus az előzőnél. Ez akkor is használható, ha nem tudjuk, hogy egyáltalán létezik-e ilyen diák, ezért eggyel több a feltétel is, mert azt is figyelni kell, hogy a tömb végén ne szaladjunk túl. A ciklus után pedig az i értékéből határozhatjuk meg a keresett elem helyét, ha ugyanis az i kisebb a tömb méreténél (vagyis nem szaladtunk túl rajta, tehát benne van), akkor az i már a keresett elem helyét jelenti. Ha nem így van, akkor nincs benne. Itt is logikai rövidzárat használunk, tehát a két feltétel sorrendje nagyon fontos. Az első feltétel biztosítja azt, hogy a második nem lehet hibás. Keresési algoritmusból többféle létezik, ez csak a legegyszerűbb lineáris keresés algoritmusa.

Minimum/maximum keresés

Nagyon gyakori feladat az, amikor egy tömbből meg kell határozni a legkisebb/legnagyobb elemet. Ez nem csak egyszerű típusoknál használható, akár objektumok (több tulajdonsággal rendelkező adattárolók) közül is kiválaszthatjuk a legkisebb/legnagyobb tulajdonságút. Technikailag az, hogy a minimum vagy maximum értéket keressük csak egy reláció megfordítását jelenti. Nézzük akkor, hogy néz ki ez az algoritmus. Keressük meg a tomb nevű tömbben a legnagyobb értéket!

int max = 0;

for( int i = 1; i < meret; i++ )
{
    if( tomb[i] > tomb[max] )
    {
        max = i;
    }
}

cout << "A tombben levo legnagyobb szam: " << tomb[max] << endl;

Nézzük akkor részenként a programot. Először is deklarálunk egy max nevű változót, amelynek azonnal adunk is egy 0 kezdőértéket. Fontos, hogy ez nem egy változó nullázás, mint a megszámlálás vagy összegzés algoritmusánál tettük. Ennek a 0 értéknek jelentése van. Azt jelenti, hogy a legnagyobb elem a legelső, vagyis a 0 indexű! A max változóban tehát nem a legnagyobb elem értékét, hanem a helyét (indexét) tároljuk. Mindjárt világos lesz, miért. Azt mondjuk tehát, hogy a legnagyobb elem a 0. helyen van, vagyis ez az első elem. Ez teljesen egyértelmű, hiszen amíg meg nem vizsgálom a tömböt, az első elem tekinthető a legnagyobbnak, mivel a többit még nem ismerem. A ciklust, amivel végigmegyek az egész tömbön természetesen a 2. elemtől indul (indexe 1) és a tömbméret-1 indexű az utolsó, amit vizsgálnom kell. Ha az éppen vizsgált elem (tomb[i]) nagyobb, mint az eddigi legnagyobb tomb[max], akkor az új maximum helye megváltozik az aktuálisra -> max = i.

Fura lehet, hogy miért a legnagyobb elem helyét tároljuk és nem az értékét. Mi van akkor, ha ez a kérdés: Hányadik elem a legnagyobb a tömbben? Ha a maximumban a legnagyobb elem értékét tárolnánk, abból nem tudnánk megmondani, hogy az pontosan hol van. Az összes olyan kérdésre nem tudnánk válaszolni, ami a legnagyobb elem helyére kíváncsi.

Ha a legkisebb elemet keressük (minimumkeresés), akkor a kiemelt sorban fordul meg a relációs jel, és máris a legkisebb elemet kapjuk meg a végén. Természetesen minimum keresésnél célszerű a max változó nevét min-re változtatni, hogy utaljon arra, mit is keresek.

Ne felejtsd el tehát, minimum és maximum keresésnél a helyet tároló változó kezdőértéke 0, mivel az első elem lesz először a legkisebb vagy legnagyobb, ha elkezdem a keresést.

Más oka is van annak, hogy a helyet és nem az értéket tároljuk. Tételezzük fel, hogy csak negatív számokat tartalmaz a tömbünk és a legnagyobbat keressük közülük. Létrehozunk egy max változót, azt nullázzuk, de ez most a legnagyobb elem értékét jelentené. Találhatunk negatív számok között olyat, ami nagyobb, mint 0? Könnyen belátható, hogy csak pozitív számokat tartalmaz a tömb és a legkisebbet keressük, akkor sem állja meg a helyét a nullázás. A nulla nem pozitív, tehát nem találsz ettől kisebb pozitív számot, vagyis a tömb egyik eleme sem kerülhet a helyére.

Rendezés

Nagyon gyakori a programjainkban az a típusfeladat, hogy sorba kell rendezni egy tömb elemeit. Rendezési algoritmusból nagyon sokféle létezik, vannak egyszerűbb, de lassabb típusok, és vannak nagyon hatékonyak. A valódi helyzet az, hogy a rendezendő adatoktól mennyiségétől is függ az, hogy melyik rendezési algoritmus a hatékony, de középiskolai szinten mindegy hogyan rendezünk, csak oldjuk meg a feladatot. Két rendezési algoritmust fogok megmutatni, amelyeket használni/tanítani szoktam, ha ezeket tudod, akkor bármilyen típusú tömböt rendezni tudsz.

A rendezések legtöbbje összehasonlításokon és cseréken alapul. Összehasonlítunk két elemet, és ha azok sorrendje nem megfelelő, akkor megcseréljük őket. Az algoritmusok sokszor abban különböznek, hogy melyik kettőt hasonlítjuk össze és utána melyik kettőt, stb. Létezik olyan speciális rendezés is, amelyik nem használ összehasonlításokat és cseréket, de ezek csak bizonyos esetekben használhatóak, akkor viszont hihetetlen gyorsak.

A rendezés esetén már összetettebb módon kell bejárni a tömböt, amelynek elemeit rendezni szeretnénk. Itt is igaz az, hogy nem csak egyszerű típusú értékeket tartalmazó tömböket lehet rendezni, az elemek lehetnek összetett objektumok is, melyek többféle típusú értéket tartalmazhatnak.

A tömbök kezelésekor, és az alap algoritmusok használatakor minden esetben ciklusokat használunk arra, hogy bejárjuk az adott tömböt, és annak értékeihez egymás után hozzáférjünk. Abban vannak csak különbségek, hogy ténylegesen bejárjuk-e az egészet, vagy sem, esetleg a bejárás iránya változik. Itt azonban másról lesz szó. Itt találkozunk először az egymásba ágyazott ciklusokkal.

A rendezések, melyeket jellemzően használunk minden esetben azt az elvet követik, hogy a tömb bizonyos elemeit hasonlítják össze, hogy azok egymáshoz képest a kívánt sorrendben helyezkednek-e el. Ha ez nem így van, akkor ezt a két elemet meg kell cserélni. Itt azonban nem csak az egymás melletti szomszédokat vizsgáljuk,

Egyszerű cserés rendezés

Ezt a rendezést több néven is megtalálhatjuk az alap algoritmusok között, én ezt a nevet használom. Az elv, ami alapján dolgozik az az, hogy minden elemet összehasonlít az összes mögötte lévővel, és ha azok sorrendje nem megfelelő, akkor megcseréli őket. Két egymásba ágyazott ciklust igényel, ezeket tradicionálisan i és j ciklusváltozókkal használjuk. Lássuk akkor magát az algoritmust, ahol feltételezzük, hogy van egy tomb nevű tömbünk, amely véletlen számokkal van feltöltve és a meret nevű változóban a tömb méretét találjuk meg:

int csere;
for( int i = 0; i < meret-1; i++ )
{
    for( int j = i+1; j < meret; j++ )
    {
        if( tomb[i] > tomb[j] )
        {
            csere = tomb[i];
            tomb[i] = tomb[j];
            tomb[j] = csere;
        }
    }
}

A ciklus úgy dolgozik, hogy a j változó mindig az i utáni helyet jelöl, mivel a j kezdőértéke minden esetben i+1-ről indul. Éppen ezért az i soha nem mehet el a tömb végéig, mert akkor az utolsó elem utáni összehasonlítást is elvégezne, ami mindenképp hibás.

Tehát még egyszer a lényeg: az i van elöl, a j van hátul!

Lássuk a kiemelt részek magyarázatát:

  • 1 – Kell egy csere változó az esetleges cserékhez segédváltozónak. A változó típusának meg kell egyezni a tömb elemeinek típusával, hiszen azon közül fogjuk az egyiket eltárolni benne.
  • 2 – Az i változó soha nem mehet el a tömb végéig, vagyis i < meret-1;
  • 4 – A j mindig az i után áll, ezért int j = i+1;
  • 6 – Mindig összehasonlítjuk az elöl és hátul lévő elemeket, és ha ezek sorrendje nem megfelelő…
  • 8-10 – Akkor jön az elemek cseréje.

A rendezés iránya csak és kizárólag a 6. sorban megadott relációs jeltől függ. Ha az elöl lévő nagyobb és akkor cserélünk, akkor a nagyok kerülnek hátra, vagyis növekvő rendezést alkalmazunk. Ha az elől lévő kisebb és akkor cserélünk, akkor a kicsik kerülnek hátra, és csökkenő rendezést írunk. A fenti példa tehát növekvő rendezést valósít meg, mivel az első esetnek megfelelő a relációs jel.

A csökkenő rendezés ehhez képest tehát minimális változtatással jár:

int csere;
for( int i = 0; i < meret-1; i++ )
{
    for( int j = i+1; j < meret; j++ )
    {
        if( tomb[i] < tomb[j] )
        {
            csere = tomb[i];
            tomb[i] = tomb[j];
            tomb[j] = csere;
        }
    }
}

Minimum/maximum kiválasztásos rendezés

Ez a rendezés az előző továbbfejlesztett változata. Az előző algoritmus úgy dolgozik, hogy minden esetben megcseréli a két elemet, ha az aktuális két elem helyzete nem megfelelő. Ez azt eredményezi, hogy több csere is lesz, mire a legkisebb a tömb elejére kerül növekvő rendezés esetén. De ha már egyszer növekvő rendezést akarunk megvalósítani, akkor nem lenne jobb, hogy ha először megkeresnénk a legkisebb elemet, majd azt helyeznénk a lista elejére, majd utána megkeresnék a második legkisebbet, azt beraknánk az első után, és így tovább? Jóval kevesebb cserével járna, mint az előző. Természetesen megoldható, az előző rendezési algoritmusa tökéletesen kombinálható a már tanult minimum/maximumkeresési algoritmusokkal. Lássuk akkor hogyan:

int csere;
int min;
for( int i = 0; i < meret-1; i++ )
{
    min = i;
    for( int j = i+1; j < meret; j++ )
    {
        if( tomb[j] < tomb[min] )
        {
            min = j;
        }
    }
    if( min != i )
    {
        csere = tomb[i];
        tomb[i] = tomb[min];
        tomb[min] = csere;
    }
}

Lássuk akkor a magyarázatot:

  • 1 – Kell egy csere változó az esetleges cserékhez segédváltozónak. A változó típusának meg kell egyezni a tömb elemeinek típusával, hiszen azon közül fogjuk az egyiket eltárolni benne.
  • 2 – Kell egy változó, ahol a legkisebb elem helyét tároljuk (mint a minimumkiválasztásnál), de ennek itt még nem adunk kezdőértéket.
  • 5 – Mielőtt elkezdjük a belső ciklust, ami az elöl lévő elem mögöttiek indexén megy végig, az elöl lévő elemet feltételezzük a legkisebbnek. Itt a belső ciklus futását gyakorlatilag egy minimum kiválasztásnak írtuk meg. A tomb[i] az első elem, ezért ennek a helyét feltételezzük a legkisebb elem helyének,
  • 8 – majd, ha az eddigi minimumtól valamelyik mögötte lévő (tomb[j]) tőle kisebb,
  • 10 – akkor a hátul lévő elem helyét (j) jegyezzük meg, mint aktuális legkisebbet.
  • 13 – Ha a belső ciklussal végeztünk, akkor a min változóban benne van a hátul lévő elemek közül a legkisebbnek a helye. Ha ez a hely nem egyenlő az elöl lévővel (vagyis nem önmaga a legkisebb), akkor találtunk az elöl lévő (i) elem mögött tőle kisebbet, melynek helyet a min változóban tároljuk.
  • 15-17 – Ebben az esetben a két elemet (i és min helyen lévőket) megcseréljük.

Ezt az algoritmust inkább csak érdekességképp mutattam meg, érettségire tökéletesen elég, ha az egyszerű cserés rendezést megtanulod, mert csak az a követelmény, hogy rendezni tudj, teljesen mindegy, melyik algoritmussal. Nyilván a legegyszerűbbet célszerű megtanulni, a hatékonyság nem követelmény.

Kiválogatás

Szintén az alap algoritmusok közé tartozik az a feladattípus, amikor bizonyos tulajdonságnak, vagy tulajdonságoknak megfelelő elemeket kell egy tömbből egy másik tömbbe kiválogatni. Tegyük fel, van egy egészeket tartalmazó tömbünk, melyet a [-9;9] intervallumból töltöttünk fel. Hogyan oldhatjuk meg, hogy ebből a tömbből egy másik tömbbe kigyűjtjük a negatív számokat? Minden esetben létre kell hozni egy másik tömböt, amibe a megfelelő elemeket másoljuk. De mekkora legyen ez a tömb? Ez az ami alapvetően meghatározza, hogy milyen megoldási módot alkalmazunk. Kétféle esetet különböztetünk meg:

  1. Létrehozunk egy eredeti tömbnek megfelelő méretű tömböt, azt feltételezve, hogy akár az összes elem lehet negatív, így mindet át kell másolni. Ha azonban nem minden elem negatív, akkor az új tömbben maradnak üres helyek, ahova nem rakunk át semmit. Így nyilván kell tartanunk, hogy hány elemet másoltunk át az új tömbbe, és mennyi maradt “üresen” a végén.
  2. Megoldhatjuk úgy is, hogy először megszámoljuk, hogy hány elem felel meg a feltételnek, ami alapján a kiválogatást el akarjuk végezni, és az új tömböt pontosan akkorának állítjuk be. Így a megoldás végén az új tömbben csak azok az elemek lesznek benne, amelyeket mi helyeztünk el benne.

A két megoldásból a második nyilván picivel több munkával jár, mert kapcsolódik hozzá egy megszámlálás is, viszont utána már nem kell attól tartanunk, hogy az eredmény tömbben olyan elem is előfordul, ami nem felel meg a kiválogatás feltételének.

Lássuk akkor a két különböző megoldást. Mindkét esetben feltételezzük, hogy van egy tomb nevű tömbünk, amely véletlen számokkal van feltöltve, és a meret nevű változóban a tömb méretét találjuk meg. Az új tömbbe a páratlan számokat szeretnénk kiválogatni:

int paratlan[meret] = {0};

int db = 0;
for( int i = 0; i < meret; i++ )
{
    if( tomb[i] % 2 != 0 )
    {
        paratlan[db] = tomb[i];
        db++;
    }
}

Lássuk akkor a kiemelt sorok magyarázatát:

  • 1 – Létrehozok egy ugyanakkora tömböt, mint az eredeti, lehetőséget adva arra, hogy akár minden elemet kiválogathassak.
  • 3 – Létrehozok egy db nevű változót, ami jelen esetben az első üres helyet fogja tárolni, ahova a következő kiválogatott elemet elhelyezhetem, a kiválogatás végeztével pedig tárolni fogja, hogy az új tömbbe hány elem került bele.
  • 4 – Végigmegyek az eredeti tömbön,
  • 6 – és ha az eredeti tömbben páratlan számot találunk,
  • 8 – akkor az új tömbben a első üres helyre (db) elhelyezem az elemet,
  • 9 – majd megnövelem a db-ot, hogy az esetleges következő átmásolt elem ne írja felül az előzőt.

Látható, hogy nem olyan bonyolult algoritmusról van szó, a kulcs az, hogy mindig tárolom egy változóban, hogy hol van az új tömbben az első üres hely, mert csak oda rakhatok bele a kiválogatás során elemeket. A gond csak annyi, hogy ha van egy 1000 méretű tömböm, amibe 3 elemet kellene csak kiválogatni, akkor is a memóriában foglalja az 1000 elemnyi helyet a 3 kedvéért.

Lássuk akkor a másik megoldást:

int db = 0;
for( int i = 0; i < meret; i++ )
{
    if( tomb[i] % 2 != 0 )
    {
        db++;
    }
}

int paratlan[db] = {0};

db = 0;
for( int i = 0; i < meret; i++ )
{
    if( tomb[i] % 2 != 0 )
    {
        paratlan[db] = tomb[i];
        db++;
    }
}

Ha jól megnézed nem sokkal bonyolultabb, picit többet kell gépelni, és ki kellett egészíteni a megszámlálás alap algoritmusával:

  • 1-8 – Megszámoljuk, hány elemet kell majd kiválogatni az új tömbbe.
  • 10 – Létrehozunk egy pontosan akkora tömböt, és feltöltjük 0 értékekkel. (ez a lépés valójában felesleges, de nem baj ha megszokjuk, hogy egy létrehozott tömböt illik 0 kezdőértékekkel feltölteni)
  • 12-20 – Ez pontosan az első megoldás.

Az egész algoritmus kulcs momentuma a db változó használata! Ennek több szerepe is van. Először a kiválogatandó elemek darabszámát gyűjtjük bele, utána a következő üres helyet jelöli az új tömbben, végül a kiválogatás végeztével az új tömb méretét jelenti, amit az új tömb kezelésekor (kiíratás, rendezés, stb) természetesen felhasználhatunk.

Komplex feladat

Lássunk egy komplexebb feladatot. Adott egy 10 elemű tömb melyet véletlen számokkal töltöttünk fel a [-9;9] intervallumból. Írjuk ki növekvő sorrendben a tömbben szereplő páros számokat.

#include <iostream>
#include <ctime>
#include <cstdlib>

using namespace std;

int main()
{
    srand(time(0));

    int meret = 10;
    int tomb[meret];

    for( int i = 0; i < meret; i++ )
    {
        tomb[i] = rand() % 19 - 9;
    }

    for( int i = 0; i < meret; i++ )
    {
        cout << tomb[i] << " ";
    }

    cout << endl << endl;

    int db = 0;
    for( int i = 0; i < meret; i++ )
    {
        if( tomb[i] % 2 == 0 )
        {
            db++;
        }
    }

    int paros[db] = {0};

    db = 0;
    for( int i = 0; i < meret; i++ )
    {
        if( tomb[i] % 2 == 0 )
        {
            paros[db] = tomb[i];
            db++;
        }
    }

    int csere;
    for( int i = 0; i < db-1; i++ )
    {
        for( int j = i+1; j < db; j++ )
        {
            if( paros[i] > paros[j] )
            {
                csere = paros[i];
                paros[i] = paros[j];
                paros[j] = csere;
            }
        }
    }

    for( int i = 0; i < db; i++ )
    {
        cout << paros[i] << " ";
    }

    cout << endl;

    return 0;
}

Ez egy tökéletes feladat arra, hogy az eddig tanultakat összefoglalja. Sok ismerős részletet láthatunk benne, de lássuk akkor részenként:

  • 2-3 – Szükséges kódok beillesztése a véletlen szám sorsoláshoz.
  • 9 – Belekeverünk a véletlen szám sorsolásba.
  • 11-17 – Adott méretű tömb létrehozása 0 kezdőértékekkel, majd feltöltése véletlen számokkal.
  • 19-22 – A kisorsolt tömb kiíratása.
  • 24 – Sordobás a sorsolt tömb kiíratása után, hogy ne folyjon egybe majd a rendezett tömb kiíratásával.
  • 26-33 – A kiválogatáshoz megszámoljuk, hány elemet kell majd átrakni az új tömbbe.
  • 35 – Létrehozzuk az új tömböt 0 kezdőértékekkel.
  • 37-45 – Kiválogatjuki (átmásoljuk) a páros számokat az új tömbbe.
  • 47-59 – Rendezzük az új tömböt.
  • 61-64 – Kiírjuk a kiválogatott és rendezett új tömböt.
  • 66 – Egy bónusz sordobás a végére, hogy ha bővíteném a programot, akkor az új kiíratás új sorban kezdődjön.

Adott tehát egy elsőre bonyolultnak tűnő feladat, amit szétbontottuk olyan részekre, melyeket már külön-külön meg tudunk oldani. Ezeket a kész megoldásokat (tömb feltöltés, kiíratás, megszámlálás, kiválogatás, rendezés, stb) megfelelő sorrendben hibátlanul összerakjuk, és kész a feladat teljes megoldása. Ugye így jobban belegondolva nem is olyan nehéz? Feltéve hogy az eddigi tananyagokat már készségszinten alkalmazni tudod. Sokszor az a legnehezebb feladat, hogy felismerjük azt, hogy az aktuális feladat milyen kisebb alkotóelemekre bontható, melyekre már kész megoldásaink vannak. Ha ez a részekre bontás megy, akkor gyakorlatilag sokszor gépelési feladattá tudjuk egyszerűsíteni a feladatok nagy részének megoldását.

Következő lecke: String

Vélemény, hozzászólás?

Az e-mail címet nem tesszük közzé. A kötelező mezőket * karakterrel jelöltük

*

Ez az oldal az Akismet szolgáltatást használja a spam csökkentésére. Ismerje meg a hozzászólás adatainak feldolgozását .