Miért?
¯\_(ツ)_/¯
Na de, hogy ennél kicsit többet mondjak: a programozási tételek célja, hogy egyedi problémákra általános megoldásokat használjunk.
Kicsit bővebben kifejtve. Azt szeretnénk elérni, hogy programozás során a konkrét programozási feladatokat ne izoláltan, mint csupán "feladat 1" és "feladatat 2" lássuk. Ne csak mindig az adott problémára keressük az éppen pontosan megfelelő megoldást.
Helyette tanuljunk meg relatíve kevés, lecsupaszított, általános tételt. Ezek segítségével a specifikus feladatokat nem kell minden egyes alkalommal nulláról kezdeni, hanem a sablon segítségével már félig kész lépéssorral vághatunk neki a kódolásnak. Csupán pontosításra van szükségünk.
Összegzés (SZUM)
Elemek összesítése. Kód egész számokhoz (C#)
Specifikáció
Be: elemszám ∈ N, elemek ∈ H[1..elemszám]
Ki: össz ∈ H
Ef: -
Uf: össz = SZUM(i=1..elemszám, elemek[i])
Algoritmus
Változó
i: Egész
össz := 0
Ciklus i=1-től elemszám-ig
össz := össz + elemek[i]
Ciklus vége
Megszámolás (DARAB)
Feltétel(ek)nek eleget tevő elemek darabszáma. Általános kód (C#)
Specifikáció
Be: elemszám ∈ N, elemek ∈ H[1..elemszám], T: H->L
Ki: db ∈ N
Ef: -
Uf: db = DARAB(i=1..elemszám, T(elemek[i]))
Algoritmus
Változó
i: Egész
db := 0
Ciklus i=1-től elemszám-ig
Ha T(elemek[i]) akkor db := db + 1
Ciklus vége
Maximum- és minimumkiválasztás (MAX/MIN)
A legnagyobb/legkisebb elem megadása. Indexet és értéket ad vissza. MAX Kód egész számokhoz (C#).
Specifikáció
Be: elemszám ∈ N, elemek ∈ H[1..elemszám]
Ki: maxind ∈ Z, maxért ∈ H
Ef: elemszám > 0
Uf: (maxind, maxért) = MAX(i=1..elemszám, elemek[i])
Be: elemszám ∈ N, elemek ∈ H[1..elemszám]
Ki: minind ∈ Z, minért ∈ H
Ef: elemszám > 0
Uf: (minind, minért) = MIN(i=1..elemszám, elemek[i])
Algoritmus
Változó
i: Egész
maxért := elemek[1]
maxind := 1
Ciklus i=2-től elemszám-ig
Ha elemek[i] > maxért akkor
maxért := elemek[i]
maxind := i
Elágazás vége
Ciklus vége
Változó
i: Egész
minért := elemek[1]
minind := 1
Ciklus i=2-től elemszám-ig
Ha elemek[i] < minért akkor
minért := elemek[i]
minind := i
Elágazás vége
Ciklus vége
Eldöntés (VAN)
Feltétel(ek)nek megfelelő elem keresése. A válasz logikai érték (igen/nem).
Általános kód (C#)Specifikáció
Be: elemszám ∈ N, elemek ∈ H[1..elemszám], T:H->L
Ki: van ∈ L
Ef: -
Uf: van = VAN(i=1..elemszám, T(elemek[i]))
Algoritmus
Változó
i: Egész
i := 1
Ciklus amíg i <= elemszám és nem T(elemek[i])
i := i + 1
Ciklus vége
van := i <= elemszám
vagy
Változó
i: Egész
van := hamis
i := 1
Ciklus amíg nem van és i <= elemszám
Ha T(elemek[i]) akkor van := igaz
különben i := i + 1
Ciklus vége
Mind eldöntés / optimista eldöntés (MIND)
Feltétel(ek) teljesülésének ellenőrzése az összes elemre. A válasz logikai érték (igen/nem).
Általános kód (C#)Specifikáció
Be: elemszám ∈ N, elemek ∈ H[1..elemszám], T:H->L
Ki: mind ∈ L
Ef: -
Uf: mind = MIND(i=1..elemszám, T(elemek[i]))
Algoritmus
Változó
i: Egész
i := 1
Ciklus amíg i <= elemszám és T(elemek[i])
i := i + 1
Ciklus vége
mind := i > elemszám
Kiválasztás (KIVÁLASZT)
Feltétel(ek)nek megfelelő elem keresése. Biztosan tudjuk, hogy szerepel megfelelő elem. Indexet ad vissza.
Általános kód (C#)Specifikáció
Be: elemszám ∈ N, elemek ∈ H[1..elemszám], T:H->L
Ki: ind ∈ Z
Ef: ∃i ∈ [i..elemszám]: (T(elemek[i]))
Uf: ind = KIVÁLASZT(i>=1, T(elemek[i]))
Algoritmus
Változó
i: Egész
i := 1
Ciklus amíg nem T(elemek[i])
i := i + 1
Ciklus vége
ind := i
vagy
ind := 1
Ciklus amíg nem T(elemek[ind])
ind := ind + 1
Ciklus vége
Keresés (KERES)
Feltétel(ek)nek megfelelő elem keresése. Nem biztos, hogy van megfelelő elem. Logikai értéket és indexet ad vissza.
Általános kód (C#)Specifikáció
Be: elemszám ∈ N, elemek ∈ H[1..elemszám], T:H->L
Ki: van ∈ L, ind ∈ Z
Ef: -
Uf: (van, ind) = KERES(i=1..elemszám, T(elemek[i]))
Algoritmus
Változó
i: Egész
i := 1
Ciklus amíg i <= elemszám és nem T(elemek[i])
i := i + 1
Ciklus vége
van := i <= elemszám
Ha van akkor ind := i
vagy
ind := 1
Ciklus amíg ind <= elemszám és nem T(elemek[ind])
ind := ind + 1
Ciklus vége
van := ind <= elemszám
vagy
van := hamis
ind := 1
Ciklus amíg nem van és ind <= elemszám
Ha T(elemek[ind]) akkor van := igaz
különben ind := ind + 1
Elágazás vége
Ciklus vége
Másolás (MÁSOL)
A tömb(ök)höz egy másik, azonos hosszúságú tömböt rendelünk. A tömb(ök) elemein elvégzett műveletek azonosak. Tömböt ad vissza.
Általános kód (C#)Specifikáció
Be: elemszám ∈ N, elemek ∈ H[1..elemszámok], f:H1->H2
Ki: fvelemek ∈ H2[1..elemszám]
Ef: -
Uf: fvelemek = MÁSOL(i=1..elemszám, f(elemek[i]))
Algoritmus
Változó
i: Egész
Ciklus i=1-től elemszám-ig
fvelemek[i] := f(elemek[i])
Ciklus vége
Kiválogatás (KIVÁLOGAT)
Feltétel(ek)nek megfelelő összes elem megkeresése. Tömböt ad vissza.
Két változata van. Az első, amikor az indexeket válogatjuk ki, míg a másikban az értékeket.
A különbség a kettő között annyi, hogy a KIVÁLOGAT tömbje kivindexek vagy kivelemek és a végén i vagy elemek[i] szerepel-e. Lent az indexes verzió látható.
Általános kód (C#)Specifikáció (indexek)
Be: elemszám ∈ N, elemek ∈ H[1..elemszám], T:H->L
Ki: db ∈ N, kivindexek ∈ H[1..db]
Ef: -
Uf: (db, kivindexek)=KIVÁLOGAT(i=1..elemszám, T(elemek[i]), i)
Algoritmus (indexek)
Változó
i: Egész
db := 0
Ciklus i=1-től elemszám-ig
Ha T(elemek[i]) akkor
db := db + 1
kivindexek[db] := i
Elágazás vége
Ciklus vége
Kiválogatás több szempont szerint (speci + alg.)
Ha kettő, vagy több kiválogatást szeretnénk párhuzamosan végezni, akkor változik minimálisan a specifikáció és a kód.
- az utófeltételben több KIVÁLOGAT van, amik a megfelelő db, kivelemek párhoz tartoznak
- az algoritmus számlálós ciklusa annyi (egymástól ált. elkülönülő) elágazást kap, ahány T tulajdonság van
Be: elemszám ∈ N, elemek ∈ H[1..elemszám], T1:H->L, T2:H->L
Ki: db1 ∈ N, kivelemek1 ∈ H[1..db1], db2 ∈ N, kivelemek2 ∈ H[1..db2]
Ef: -
Uf: (db1, kivelemek1)=KIVÁLOGAT(i=1..elemszám, T1(elemek[i]), elemek[i]) és
(db2, kivelemek2)=KIVÁLOGAT(i=1..elemszám, T2(elemek[i]), elemek[i])
Változó
i: Egész
db1 := 0
db2 := 0
Ciklus i=1-től elemszám-ig
Ha T1(elemek[i]) akkor
db1 := db1 + 1
kivelemek1[db1] := elemek[i]
Ha T2(elemek[i]) akkor
db2 := db2 + 1
kivelemek2[db2] := elemek[i]
Elágazás vége
Ciklus vége
További linkek
Gyakorló feladatok programozási tételekkel ELTE specifikáció szerkesztőjeForrások
Horváth Győző, Horváth Gyula, Szlávi Péter, Törley Gábor: Programozási alapismeretek 3. előadás (ppt) (előadó: Törley Gábor)
Horváth Győző, Horváth Gyula, Szlávi Péter, Törley Gábor: Programozási alapismeretek 4. előadás (ppt) (előadó: Törley Gábor)
Horváth Győző, Horváth Gyula, Szlávi Péter, Törley Gábor: Programozási alapismeretek 5. előadás (ppt) (előadó: Törley Gábor)