Programozási tételek

Tartalom

Mind eldöntés / optimista eldöntés (MIND)

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.

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.

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

Maximumkiválasztás (MAX)

A legnagyobb elem megadása. Indexet és értéket ad vissza.

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])

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

Minimumkiválasztás (MIN)

A legkisebb elem megadása. Indexet és értéket ad vissza.

Specifikáció


                    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
                    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).

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).

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.

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.

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
                    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.

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ÁLASZT)

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 végén i vagy elemek[i] szerepel-e. Lent az indexes verzió látható.

Specifikáció (indexek)


                    Be: elemszám ∈ N, elemek ∈ H[1..elemszám], T:H->L
                    Ki: db ∈ N, kivelemek ∈ H[1..db]
                    Ef: -
                    Uf: (db, kivelemek)=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
                            kivelemek[db] := i
                        Elágazás vége
                    Ciklus vége

További linkek

Gyakorló feladatok programozási tételekkel ELTE specifikáció szerkesztője

Forrá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)