Programozási tételek
Idővel, ha egyre több algoritmust készítenénk, tapasztalnánk azt, hogy bizonyos részfeladatok tipizálhatók, lényegében ugyanazon algoritmusok szükségesek a megoldásukhoz. Ezután néhány ún. típusalgoritmussal fogunk megismerkedni, melyeket "programozási tételeknek" is nevezhetünk. (akár a matematikában)
Ezen tételek ismeretében már a legtöbb feladat megoldása során nincs más dolgunk mint meghatározni, hogy milyen típusú feladatról van szó és alkalmazni a megfelelő algoritmust, a megfelelő programozási tételt. Persze el kell végezni a megfeleltetéseket. Ha nem használnánk programozási tételeket programjaink áttekinthetetlenekké válnának, oly módon oldanánk meg feladatot, mintha mindig fel kellene fedeznünk a megoldóképetet.
Az alábbiak során az egyes tételeknél mindig megnézünk egy általános feladatot, annak megoldását, majd egy a tételhez kapcsolódó egy konkrét feladatot és annak megoldását.
Sorozathoz egy érték hozzárendelése
1. Az összegzés és átlagszámítás tétele
Feladat: Adott egy A nevű N elemű sorozat, amely numerikus elemeket tartalmaz. Készítsünk olyan programot, amely megadja a sorozat elemeinek összegét.
Gondolatmenet: Vegyük a sorozat elemeit rendre egyesével és adjuk hozzá az előzőek összegéhez. Az összegzés elvégzéséhez egy SUM nevű változót használjunk. Az elemek feldolgozásához előírt lépésszámú növekményes ciklust szervezünk.
Algoritmus Összegez
Sum:=0
Ciklus I:= 1 -Től N -Ig
Sum:= Sum + A(I)
Ciklus Vége
Ki(Sum)
Algoritmus Vége.
Fontos lépés a Sum változó értékének nullázása, Sum:= 0 utasítás elvégzése. A Sum ugynevezett gyűjtő változó, értékét nullázni kell. A gyűjtés lépése Sum:=Sum+ A(i), olyan mint amikos egy kosárba mindig ujabb dolgokat teszünk.
Módosítsuk a feladatot, hogy az A(N) tömb elemeinek átlagát számoljuk ki.
Megfeleltetés:
A(N): sorozat; Sum: összeg Átl: átlag
Algoritmus: ÁtlagSzámítás
Sum:=0
Ciklus I:= 1 -Től N -Ig
Sum:= Sum + A(I)
Ciklus Vége
Átl:= Sum / N
Ki(Átl)
Algoritmus Vége.
Vegyük észre, hogy az átlag kiszámítása a teljes összegzés elvégzése után történt, tehát a cikluson kívül.
Konkrét feladat: N napon keresztül naponta egyszer megmértük a hőmérsékletet. Adjuk meg az N napos időszak átlaghőmérsékletet!
Megfeleltetés:
Sorozat: HŐ(N), megfelel A(N) -nek
N napi átlaghőmérséklet: ÁtlHő, megfelel Átl-nak
N nap hőmérsékletének összege: Összhő, megfelel Sum-nak.
(Ezután a feladat egyszerűen a szereplő azonosítók cseréjére vezethető vissza, vagyis egy szövegszerkesztői feladatot kaptunk. Persze nem árt érteni, mit csinálunk.)
Algoritmus: Átlagszámítás
Összhő:= 0;
Ciklus I:= 1 -Től N -Ig
Összhő:= Összhő + A(I)
Ciklus Vége
ÁtlHő:= Összhő / N
Ki(ÁtlHő)
Algoritmus Vége.
2. Megszámlálás tétele:
Feladat: Ismert egy N elemű sorozat és a sorozat elemein értelmezett T tulajdonság. A T tulajdonsággal rendelkező elemek számára vagyok kíváncsi.
Gondolatmenet:
Vizsgáljuk meg a szorzat minden elemét! ( Ciklus szervezés 1-től N-ig.) Ha a sorozat valamely eleme rendelkezik T tulajdonsággal, akkor eggyel több ilyen elemünk van, vagyis megnöveljük a Db változó értékét eggyel: Db:=Db+1.
Algoritmus: Megszámlál
Db:=0
Ciklus I:= 1-Től N-Ig
Ha A(I) = T Tulajdonságú Akkor
Db:= Db+1
Elág vége
Ciklus Vége
Ki: Db
Algoritmus Vége.
Konkrét feladatok:
Számoljuk meg egy Számok(N) tömbnek hány pozitív eleme van!
Adjuk meg az osztály névsorából a "Kovács" vezetéknevű emberkék számát. (Írják fel a megfeleltetést, gondolatmenetet, algoritmust.)
3. A maximum, (minimum) kiválasztás tétele
Feladat: Ebben a feladatban egy sorozat legnagyobb, (legkisebb) elemét kell megtalálni, pontosabban annak sorszámát meghatározni. A sorozat lehet szám vagy szöveges elemű.
Gondolatmenet a maximum kiválasztására:
A legelső elemet válasszuk maximumnak és annak sorszámát, vagyis 1-et a maximum elem sorszámának. Az elemek feldolgozását a 2. elemtől végezzük, ettől kezdve minden elemet hasonlítsunk össze a maximummal. Ha a maximumtól a most vizsgált elem nagyobb akkor új maximumot és sorszámot választunk: a maximum értéke az éppen vizsgált elem, sorszáma a vizsgált elem sorszáma lesz.
A feladat megoldását úgy kapjuk, hogy visszavezetjük elemenkénti feldolgozásra. Ha ismerjük K elem közül a legnagyobbat és veszünk ezekhez egy új elemet, akkor a maximum, vagy az eddigi, vagy az új elem lesz.
Megfeleltetés:
A(N) - sorozat
MAXINDEX - a sorozat aktuálisan (az eddig vizsgáltak közüli) legnagyobb elemének sorszáma, végén a maximum sorszáma
MAXÉRTÉK – a sorozat aktuálisan legnagyobb értékű elemének értéke, végén a maximális érték
Algoritmus: MaxÉrték
MaxIndex:= 1
MaxÉrték:= A(MaxIndex)
Ciklus I:= 2-Től N-Ig
Ha MaxÉrték < A(I) akkor
MaxIndex:= I
MaxÉrték:=A(MaxIndex)
Elág vége
Ciklus Vége
Ki: MaxIndex
Ki: MaxÉrték
Allgoritmus Vége.
Egy Másik gondolatmenet:
Most egyszerre nem elég a sorozat egyetlen elemét vizsgálni, hiszen a legnagyobb az, amelyik mindegyiknél nagyobb, azaz mindegyikkel össze kell hasonlítani. A feladat megoldását úgy kapjuk, hogy visszavezetjük elemenkénti feldolgozásra. Ha ismerjük K elem közül a legnagyobbat és veszünk ezekhez egy új elemet, akkor a maximum, vagy az eddigi, vagy az új elem lesz.
Megfeleltetés:
A(N) - sorozat
INDEX - segédváltozó, mely az eddig megvizsgáltak közül mutatja a legnagyobb sorszámát
MAXINDEX - a sorozat legnagyobb elemének sorszáma
Algoritmus:
Program
Index:= 1
Ciklus I:= 2-Től N-Ig
Ha A(Index) < A(I) Akkor Index:= I
Ciklus Vége
Maxindex:= Index
Program Vége.
Az index, illetve a Maxindex egyértelműen meghatározza a maximum keresett értékét!
Gondolom a legkisebb elem kiválasztása már csak kézügyesség kérdése, ekkor a reláció jelet kell csak megfordítani, de emellett célszerű a változókat is átnevezni a minimum nevekre.
Más jelölésekkel és segédváltozókkal egy újabb megoldást kapunk.
Program
Érték:= A(1),
Index:=1
Ciklus I:= 2-Től N-Ig
Ha Érték < A(I) Akkor
Érték:= A(I) ; Index:= I
Elágazás vége
Ciklus Vége
Maxindex:= Index
Maxérték:= Érték
Program Vége.
4. A kiválogatás tétele:
Feladat: Egy N elemű sorozat összes T tulajdonsággal rendelkező elemét kell meghatározni, sorszámukat összegyűjteni egy másik sorozatban.
Gondolatmenet:
Összehasonlítom a sorozat összes elemét a T tulajdonsággal és közben számolom, sorszámozom a T tulajdonságúakat, melyek sorszámait egy B(K) vektorban fogom gyűjteni.
Algoritmus: kiválogat
J:= 0
Ciklus I:= 1-Től N-Ig
Ha A(I) T Tulajdonságú Akkor
J:= J+1; B(J):= I
Elág vége
Ciklus Vége
Algoritmus Vége.
Feladat: Készítsen algoritmust, amely N ember magasságának ismeretében megadja az X magasságtól alacsonyabbakat! (Itt csak a magasságok értékét tároltuk eddig is és csak ezt érjük el most is, de bármely más tulajdonság párhuzamosan kezelhető.)
Megfeleltetés:
sorozat - A(N)
tulajdonság - A(I) < X
A B tömb elemeinek számát a B_Esz változóban tároljuk.
Algoritmus: Alacsonyak
J:= 0
Ciklus I:= 1-Től N-Ig
Ha A(I) < X Akkor
J:= J+1; B(J):= I
Elág vége
Ciklus Vége
B_Esz:=J;
Alg. Vége.
A tárolt értékek kiírása:
Ciklus j:=1 –től B_Esz –ig
Ki: A(B(j))
Ciklus vége
A ciklus belsejében az A tömb B(j) által mutatott elemét íratjuk ki.