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<br />
Ciklus i:=1-től N-ig<br />
&nbsp;&nbsp;&nbsp;&nbsp; Osszeg := Osszeg+A[i]<br />
Ciklus vége<br />
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<br />
Atlag&nbsp; := 0<br />
Ciklus i:=1-től N-ig &nbsp;&nbsp;&nbsp;<br />
&nbsp;&nbsp; Osszeg := Osszeg + A[i]<br />
Ciklus vége<br />
Atlag : = Osszeg / N<br />
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<br />
i:=1<br />
Ciklus amíg NEM ( (i &lt;= N) és ( A[i].T == K ) )<br />
&nbsp;&nbsp;&nbsp;&nbsp; i := i + 1<br />
Ciklus vége<br />
Letezik := (i &lt;= 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 &lt;= N akkor<br />
&nbsp;&nbsp;&nbsp; Letezik := Igaz<br />
különben<br />
&nbsp;&nbsp;&nbsp; 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<br />
i:=1<br />
Ciklus amíg NEM ((i &lt;= N) és ( A[i].T == Elem.T ) )<br />
&nbsp;&nbsp;&nbsp;&nbsp; i := i + 1<br />
Ciklus vége<br />
Letezik := (i &lt;= N)<br />
Ha (i &lt;= N ) akkor<br />
&nbsp;&nbsp;&nbsp; Sorszam := i<br />
Különben<br />
&nbsp;&nbsp;&nbsp; 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<br />
Also&nbsp; := 1<br />
Felso := N<br />
Kozepso := ( Also + felso ) / 2<br />
Ciklus amíg ( Also &lt;= Felso ) és (A[Kozepso].T &lt;&gt; K )<br />
&nbsp;&nbsp;&nbsp; Ha A[Kozepso].T &gt; K Akkor<br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Felso := Kozepso - 1<br />
&nbsp;&nbsp;&nbsp; Különben<br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Also&nbsp; := Kozepso + 1<br />
&nbsp;&nbsp;&nbsp; Elágazás vége<br />
&nbsp;&nbsp;&nbsp; Kozepso := int(( Also + Felso ) / 2)<br />
Ciklus vége<br />
<br />
Ha (A[Kozepso].T = K) Akkor<br />
&nbsp;&nbsp; &nbsp;&nbsp; Sorszam := Kozepso<br />
Különben&nbsp;&nbsp;<br />
&nbsp;&nbsp;&nbsp; Sorszam :=&nbsp; -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<br />
Szamlalo := 0<br />
Ciklus (i = 1–től N-ig)<br />
&nbsp;&nbsp;&nbsp; Ha A[i].T == K akkor Szamlalo := Szamlalo + 1<br />
Ciklus vége<br />
Ha (i &lt;= 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]<br />
Hely&nbsp; := -1<br />
Ciklus i = 1–től N-ig<br />
&nbsp;&nbsp; Ha A[i].T &gt; Ertek.T akkor<br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Ertek := A[i]<br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Hely&nbsp; := i<br />
&nbsp;&nbsp; Elágazás vége<br />
Ciklus vége<br />
Ki: Ertek, Hely

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