05. Elemi programozási tételek - egy értéket visszaadó algoritmusok

Olyan tételekről van szó, amelynél egy sorhoz egy értéket rendelünk hozzá. Azaz a kiinduló adatok A[N], N elemű tömbben vannak.

Összegzés tétel

Mekkora az A[N] tömb elemeinek összege. A tömb elemei numerikus típusúak

Osszeg := 0
Ciklus i:=1-től N-ig
     Osszeg := Osszeg+A[i]
Ciklus vége
Ki: Osszeg

Átlagszámítás

Az átlagszámítás visszavezethető az összegzési tételre. Egy dologra kell vigyázni.  Míg a tömb elemei lehetnek egész típusúak, az átlag kiszámításánál vagy valós típust kell alkalmaznunk, vagy egész számok osztását kell használnunk.

Osszeg := 0
Atlag  := 0
Ciklus i:=1-től N-ig    
   Osszeg := Osszeg + A[i]
Ciklus vége
Atlag : = Osszeg / N
Ki: Atlag

Eldöntés

Döntsük el, hogy egy A[N] tetszőleges típusú tömbben, hogy van-e benne T tulajdonságú elem. A keresett elemet a K nevű változó tartalmazza, tehát a keresett tulajdonság : K  A választ a Letezik nevű logikai típusú változó fogja tartalmazni.

Be: K
i:=1
Ciklus amíg NEM ( (i <= N) és ( A[i].T == K ) )
     i := i + 1
Ciklus vége
Letezik := (i <= N)

Itt az utolsó sort meg kell magyarázni. A legtöbb nyelvben az értékadás jobb oldalán álló kifejezést a rendszer először kiértékeli, majd a logikai értéket értékül adja a bal oldalon álló változónak. Ha ezt egy programozási nyelv nem támogatja, akkor a következő kóddal lehet helyettesíteni a sort:

Ha i <= N akkor
    Letezik := Igaz
különben
    Létezik := Hamis

Keresés

Egy A[N] tetszőleges típusú tömbben keresünk egy T tulajdonságú elemet. Ha létezik, akkor visszaadjuk a sorszámát, különben egy olyan sorszámot adunk vissza, amely lehetetlen. A Sorszám nevű változó adja vissza a keresés értékét. A változó kezdőértékét úgy kell megválasztani, hogy a tömb legkisebb indexű eleménél is kisebb legyen.

Lineáris keresés

Be: Elem

Sorszam := -1
i:=1
Ciklus amíg NEM ((i <= N) és ( A[i].T == Elem.T ) )
     i := i + 1
Ciklus vége
Letezik := (i <= N)
Ha (i <= N ) akkor
    Sorszam := i
Különben
    Sorszam := Lehetetlen érték

Ha a fenti eljárást függvényként használjuk, akkor a függvény értékének a lekérdezésénél azt kell vizsgálni, hogy a Sorszámként visszaadott érték benne van-e a tömb értelmezési tartományában.

A lineáris keresés átlagosan N/2-ször fut le, mivel véletlenszerű elemek esetén és nagy számú keresés esetén átlagosan az N/2-ik lesz a keresett elem. Ennél sokkal jobb eredményt ad a bináris keresés.

Bináris keresés

A bináris keresés feltétele, hogy a kiindulási tömb T tulajdonság szerint növekvően vagy csökkenően rendezett legyen. Mi most a növekvő rendezettséget tételezzük fel. Ebben az esetben a keresés elve az, hogy megnézzük a tömb középső elemét. Ha megtaláltuk a keresett elemet, akkor befejeztük a keresést. Ha a középső elem T tulajdonság szerint kisebb, mint a keresett elem, akkor nyilván a felső fél tartományban kell keresni a keresett elemet, ha pedig kisebb, akkor az alsó fél tartományban kell keresni. Ily módon minden egyes összehasonlítás során kizárjuk a maradék elemek felét. Ennek megfelelően log2N keresés alatt megtaláljuk az eredményt, illetve eldönthetjük, hogy az elem benne van-e a keresett elemek között. Például N =1024 esetén 10 összehasonlítás elegendő, mivel log21024 = 10. (log2N jelenti azt a számot, amire emelve 2-őt N-t kapunk eredményül, azaz, ha a:= log2N, akkor 2a=1024. A mi példánkban 210 = 1024.)

Be: K
Also  := 1
Felso := N
Kozepso := ( Also + felso ) / 2
Ciklus amíg ( Also <= Felso ) és (A[Kozepso].T <> K )
    Ha A[Kozepso].T > K Akkor
          Felso := Kozepso - 1
    Különben
          Also  := Kozepso + 1
    Elágazás vége
    Kozepso := int(( Also + Felso ) / 2)
Ciklus vége

Ha (A[Kozepso].T = K) Akkor
      Sorszam := Kozepso
Különben  
    Sorszam :=  -1

A rutinban szereplő osztások természetesen az adott programozási nyelv egész típusú osztásának felelnek meg, és egész típusú eredményt kell visszaadniuk.

Megszámlálás

Egy A[N] tetszőleges típusú tömbben keressük hogy hány db. T tulajdonságú eleme van. Itt az a kérdés, hogy az adott tulajdonság hányszor fordul elő, tehát definiálunk egy Szamlalo nevű egész értékeket felvevő változót, amelynek a kezdő értéke 0. Az fogja tartalmazni a kérdéses elemszámot. A korábbi tételekkel ellentétben itt nyilvánvalóan végig kell nézni a teljes tömböt, ezért nem ciklus amíg, hanem ciklus …-tól …ig típusú ciklust kell használni.

Be: K
Szamlalo := 0
Ciklus (i = 1–től N-ig)
    Ha A[i].T == K akkor Szamlalo := Szamlalo + 1
Ciklus vége
Ha (i <= N ) akkor Sorszam := i

 Maximum kiválasztás (minimum kiválasztás) tétele

Keressük meg egy A[N], N elemű tömb elemei közül egy T tulajdonság szerinti legnagyobb elemet és a sorszámát valamint az értéket magát adjuk meg eredményül. Az Ertek nevű változó tartalmazza majd a legnagyobb elem értékét, és a Hely mutatja meg a legnagyobb érték helyét.

Ertek := A[1]
Hely  := -1
Ciklus i = 1–től N-ig
   Ha A[i].T > Ertek.T akkor
      Ertek := A[i]
      Hely  := i
   Elágazás vége
Ciklus vége
Ki: Ertek, Hely

Nyilván a legkisebb elemet úgy tudjuk kiválasztani, hogyha a relációs jelet megfordítjuk.