2. Egyszerű programozási tételek
Sorozatszámítás:
Pszeudokód (A: feldolgozandó tömb, N: Tömb elemeinek száma, R: Művelet eredménye):
Eljárás Sorozatszámítás(A,N,R)
R <- R0
Ciklus i<-1-től N-ig
R<-R művelet A[i]
Ciklus vége
Eljárás vége
Megjegyzések:
- Adatok sorozatához egy értéket rendelő függvényt helyettesít
- Minden olyan esetben használható, ha ezt a függvényt felbonthatjuk értékpárokon kiszámított függvények sorozatára
- Az induláskor használt nullérték értelem szerűen a kérdéses függvény (esetleg feladat) alapján kell megválasztani
Összegzés: R0<-0, művelet: R<-R+A[i]
Faktoriális: R0<-1, művelet: R<-R*A[i]
elemek uniója: R0<-{}, művelet: R<-R U A[i]
Eldöntés:
Pszeudokód(A: feldolgozandó tömb, N: Tömb elemeinek száma, T: tulajdonság függvény, VAN: Logikai változó):
Eljárás Eldöntés(A, N, T, VAN)
i<-1
Ciklus amíg (i<=N) és ¬T(A[i])
i<-i+1
Ciklus vége
VAN <- (i<=N)
Eljárás vége
Megjegyzések:
- A T tulajdonság helyes megválasztásával a tétel sokféle szituációban alkalmazható
- A “minden elem T tulajdonságú” feladatot egyszerűen visszavezethetjük az eldöntésre a T tulajdonság tagadásával
- Ez az algoritmus az első T tulajdonságú elem megtalálása után már nem folytatja a keresést
Kiválasztás:
Pszeudokód(A: feldolgozandó tömb, N: tömb elemeinek száma, T: tulajdonság függvény, SORSZ: Első T tulajdonságú elem indexe):
Eljárás Kiválasztás(A, N, T, SORSZ)
i<-1
Ciklus amíg ¬T(A[i])
i<-i+1
Ciklus vége
SORSZ<-i
Eljárás vége
Megjegyzések:
- Az eldöntéssel ellentétben ez visszaadja az első T tulajdonságú elem sorszámát
- A tétel feltételezi, hogy legalább egy T tulajdonságú elem van!
- Sorszám helyett visszaadhatjuk az elem értékét is, de sorszám alapján az elem tartalma is gyorsan visszaadható
Lineáris keresés:
Pszeudokód(A: feldolgozandó tömb, N: tömb elemeinek száma, T: tulajdonság függvény, SORSZ: Első T tulajdonságú elem indexe, VAN: logikai változó):
Eljárás Keresés(A, N, T, VAN, SORSZ)
i<-1
Ciklus amíg (i<=N) és ¬T(A[i])
i<-i+1
Ciklus vége
VAN<-(i<=N)
Ha VAN akkor
SORSZ<-i
Elágazás vége
Eljárás vége
Megjegyzések:
- Tekinthető az eldöntés és kiválasztás tétel ötvözésének is
- Értelemszerűen nem feltételezi, hogy biztosan van T tulajdonságú elem a sorozatban. Ha nincs, a VAN változó hamis értéket kap a SORSZ pedig nem kap értéket
Megszámlálás:
Pszeudokód(A: feldolgozandó tömb, N: tömb elemeinek száma, T: tulajdonság függvény, DB: T tulajdonságú elemek száma):
Eljárás Megszámlálás(A, N, T, DB)
DB<-0
Ciklus i-től N-ig
Ha T(A[i]) akkor
DB<-DB+1
Elágazás vége
Ciklus vége
Eljárás vége
Megjegyzések:
- Amennyiben nincsen T tulajdonságú elem, értelem szerűen DB értéke 0
- Ez valójában egy sorozatszámítás, ami minden T tulajdonságú elem esetén inkrementálja DB értékét
Maximumkiválasztás:
Pszeudokód(A: feldolgozandó tömb, N: tömb elemeinek száma, MAX: maximális elem indexe):
Eljárás Maximumkiválasztás(A, N, MAX)
MAX<-1
Ciklus i<-2-től N-ig
Ha A[i]>A[MAX] akkor
MAX<-i
Elágazás vége
Ciklus vége
Eljárás vége
Megjegyzések:
- A reláció megfordításával a minimum kiválasztást kapjuk meg
- Feltételezzük, hogy legalább egy elem van a listában
- Több maximális elem esetén az elsőt adja vissza
Felhasznált Irodalom: Sergyán Szabolcs – Programozás I – 3. előadás diasor
Kommentek
Powered by Facebook Comments