Nevezetes algoritmusok

Néhány elemi algoritmust ismertetünk.

Csere

Előfeltétel: Adott két objektum nevezzük az egyiket A-nak és a másikat B-nek (lehetnek szövegek, számok, bármik).
Utófeltétel: Az A értéke az eredeti B lesz, a B értéke az eredeti A.

Az algoritmus általánosságban: Bevezetünk egy új változót (C), és annak segítségével cseréljük meg a két elemet. Formálisan:

Algoritmus Csere (A,B)
   C:=A
   A:=B
   B:=C
Algoritmus vége

Kérdés: Ha C:=B-vel kezdtük volna, akkor hogyan alakul? Ez a két algoritmus egyenértékű?

Kiválogatás

Előfeltétel: Adott egy N elemű Tömb nevű tömb, melynek elemein értelmezhető egy T tulajdonság. Például A Tömb tartalmazza egy 35 fős osztály év végi átlagait. A T tulajdonság, hogy jeles tanuló, vagyis az átlaga >=4.5)
Utófeltétel: A Tömb T tulajdonságú elemeinek halmaza.

Az algoritmus általánosságban: Végigmegyünk a tömb elemein, és ha az aktuális elem T tulajdonságú, akkor kiírjuk. Formálisan:

Algoritmus Kiválogatás( Tömb, T)
   Ciklus i:=1-től N-ig
        Ha (Tömb[i] T tulajdonságú)
              Akkor Kiír (Tömb[i])
        Elágazás vége
   Ciklus vége
Algoritmus vége

Kérdés: Ha szerettük volna eltárolni T tulajdonságú adatokat, hogyan egészült volna ki az algoritmus?

Megszámolás

Előfeltétel: Adott egy N elemű Tömb nevű tömb, melynek elemein értelmezhető egy T tulajdonság. (Például A Tömb tartalmazza egy 35 fős osztály év végi átlagait. A T tulajdonság, hogy jeles tanuló, vagyis az átlaga >=4.5)
Utófeltétel: Egy szám, ami megadja a Tömb  T tulajdonságú elemeinek számát.

Az algoritmus általánosságban: Bevezetünk egy változót, amelyben tároljuk, hogy hány ilyen elem volt. Ez kezdetben 0. Végigmegyünk a tömb elemein, és ha az aktuális elem T tulajdonságú, akkor növeljük a változó értékét. Formálisan:

Algoritmus Megszámolás( Tömb, T)
   darab:=0.
   Ciklus i:=1-től N-ig
        Ha (Tömb[i] T tulajdonságú)
              Akkor darab:=darab+1
        Elágazás vége
   Ciklus vége
Kiír (darab)
Algoritmus vége

Összegzés

Előfeltétel: Adott egy N elemű számokból álló Tömb nevű tömb.
Utófeltétel: Egy szám, amely megadja a Tömb elemeinek összegét.

Az algoritmus általánosságban: Bevezetünk egy új változót, amelyben tároljuk majd az összeget. Ez az elején 0. Végigmegyünk a tömb elemein, és ha az aktuális elem értékét hozzáadjuk. Formálisan:

Algoritmus Összegzés(Tömb)
   Összeg:=0
   Ciklus i:=1-től N-ig
        Összeg:=Összeg+Tömb[i]
   Ciklus vége
   Kiír(Összeg)
Algoritmus vége

Kérdés: Ha a tömb elemeinek szorzatát szerettük volna megkapni, hogyan változott volna ki az algoritmus?

Eldöntés

Előfeltétel: Adott egy N elemű Tömb nevű tömb, melynek elemein értelmezhető egy T tulajdonság. A Tömbben nem biztos, hogy van T tulajdonságú elem. (Például A Tömb tartalmazza egy 35 fős osztály év végi átlagait. A T tulajdonság, hogy kitűnő tanuló, vagyis az átlaga 5.0)
Utófeltétel: Egy logikai érték, mely IGAZ, ha volt T tulajdonságú elem a  Tömbben, és HAMIS, ha nem.

Az algoritmus általánosságban: Most nem kell (feltétlenül) végigmennünk a tömbben. Ha mázlink van, már az első elem T tulajdonságú. Bevezetünk egy változót, amelyben tároljuk, hogy hányadik elemnél tartunk. Vesszük ezt az elemet, és ha az aktuális elem T tulajdonságú, akkor leállunk, más esetben vesszük a következő elemet. Formálisan:

Algoritmus Eldöntés( Tömb, T)
   holtartunk:=1.
   Ciklus amíg (holtartunk<=N és Tömb[holtartunk] nem T tulajdonságú)
        holtartunk:=holtartunk+1
   Ciklus vége
   Kiír(holtartunk<=N)
Algoritmus vége

A vége kicsit másképpen:

…

   Ciklus vége
   Ha (holtartunk<=N)
          Akkor kiír IGAZ
          Egyébként kiír HAMIS
Algoritmus vége

Kérdés: Mennyi lesz a holtartunk értéke, ha nem találtunk T tulajdonságú elemet? Válasz: N+1.

Megjegyzés: Itt két feltételt vizsgáltunk. Benne vagyunk-e Tömbben (holtartunk<=N), és az aktuális elem Nem T tulajdonságú. Itt a feltételek sorrendje nem mindegy, hiszen ha túlmegyünk a tömbbön, akkor a Tömb[holtartunk] értelmezhetetlen N+1. elemre.

Keresés

Előfeltétel: Adott egy N elemű Tömb nevű tömb, melynek elemein értelmezhető egy T tulajdonság. A Tömbben van T tulajdonságú elem.
Utófeltétel: Egy szám, amely megadja a Tömb T tulajdonságú elemének sorszámát.

Az algoritmus általánosságban: Bevezetünk egy új változót, amelyben tároljuk, hogy hányadik elemnél tartunk Ez az elején 1. Addig növeljük ennek a változónak az értékét amíg el nem értük  a T tulajdonságú elemet.. Formálisan:

Algoritmus Keresés(Tömb,T)
   holtartunk:=1
   Ciklus amíg Tömb[holtartunk] nem T tulajdonságú
        holtartunk:=holtartunk+1
   Ciklus vége
   Kiír(holtartunk)
Algoritmus vége

Kérdés: Melyik T tulajdonságú elemet találja meg ez algoritmus? Az elsőt? Az utolsót? Az összeset? Természetesen az elsőt. Hogyan kellene változtatni rajta, ha az utolsót keressük. Az az algoritmus, amelyik T tulajdonságú elemet “keresett” a Tömbben úgy, hogy nem biztos, hogy volt benne, az Eldöntés. Hogyan kellene változtatni az algoritmuson ahhoz, hogy ha van, akkor az elem sorszámát adja ki? Akkor az utófeltételen is változtatni kellene, mert immár egy számot ad ki. Milyen számot adjon ki, ha nincs ilyen elem?

Maximumkiválasztás

Előfeltétel: Adott egy N elemű Tömb nevű tömb, melynek elemei összehasonlíthatóak.
Utófeltétel: Egy érték a Tömb elemei közül, melyre igaz, hogy nincs nála nagyobb a tömbben.

Az algoritmus általánosságban: Bevezetünk egy változót, amelyben tároljuk, hogy melyik a legnagyobb elem. Ez kezdetben az első elem. Végigmegyünk a tömb elemein, és ha az aktuális elem nagyobb, mint az eddigi legnagyobb, akkor az lesz a változó értéke. Formálisan:

Algoritmus Maximum( Tömb)
   legnagyobb:=Tömb[1].
   Ciklus i:=2-től N-ig
        Ha (Tömb[i]>legnagyobb)
              Akkor legnagyobb:=Tömb[i]
        Elágazás vége
   Ciklus vége
   Kiír (legnagyobb)
Algoritmus vége

MaximumHely kiválasztása

Előfeltétel: Adott egy N elemű Tömb nevű tömb, melynek elemei összehasonlíthatóak.
Utófeltétel: Egy szám 1 és N között, melyre igaz, hogy a Tömb annyiadik elemének értékénél nincs nagyobb a tömbben.

Az algoritmus általánosságban: Bevezetünk egy változót, amelyben tároljuk, hogy hányadik a legnagyobb elem. Ez kezdetben az első. Végigmegyünk a tömb elemein, és ha az aktuális elem nagyobb, mint az eddigi legnagyobb, akkor az lesz a változó értéke. Formálisan:

Algoritmus MaximumHely( Tömb)
   legnagyobbHelye:=1.
   Ciklus i:=2-től N-ig
        Ha (Tömb[i]>Tömb[legnagyobbHelye])
              Akkor legnagyobbHelye:=i
        Elágazás vége
   Ciklus vége
   Kiír (legnagyobbHelye)
Algoritmus vége

Kérdés: Ha ismerjük a Maximumhelyet, meg tudjuk-e mondani a maximumot? Hogyan kellene változtatni az algoritmuson, hogy a legkisebbet adja meg? Hogyan kellene változtatni az algoritmuson, hogy a legutolsó legnagyobbat találja meg?

Rendezések

Maximumkiválasztásos rendezés

A rendezés lényege: Válasszuk ki teljes sorozatunkból a legnagyobb értéket, és azt tegyük a sorozat végére. Aztán a maradék sorozatból válasszuk ki legnagyobbat, és a maradék sorozat végére tesszük, és így tovább, egyre kisebb sorozattal.

Formálisan:

Algoritmus Maximumkiválasztásos_Rendezés(Tömb)
     Ciklus (j=N-től 2-ig -1-esével)
        maxhely=1
        Ciklus (i=2-től j-ig)
           Ha (Tömb[maxhely]<Tömb[i])
                Akkor maxhely:=i
           Ha vége
      Ciklus vége
      Csere(Tömb[maxhely], Tömb[j])
   Ciklus vége
Algoritmus vége

Milyen irányba rendez ez az algoritmus? Növekvően. Mit kellene változtatni, hogy csökkenően rendezzen?

Buborékos rendezés

A rendezés lényege: Összehasonlítjuk a teljes sorozatban az egymás mellett lévőket, és ha a baloldali nagyobb, akkor megcseréljük. Aztán ugyanezt ismételjük eggyel kisebb sorozattal, így mint egy buborék, minden ciklusban “felszáll” a legnagyobb.

Formálisan:

Algoritmus Buborékos_Rendezés(Tömb)
     Ciklus (j=N-től 2-ig -1-esével)
       Ciklus (i=1-től j-1-ig)
           Ha (Tömb[i]>Tömb[i+1])
                Akkor Csere(Tömb[i], Tömb[i+1])
           Ha vége
      Ciklus vége
  Ciklus vége
Algoritmus vége

Milyen irányba rendez ez az algoritmus? Növekvően. Mit kellene változtatni, hogy csökkenően rendezzen?