Nevezetes tételösszeépítések

Tartalom

Feltételes maximum-/minimumkeresés

Tételösszeépítésről

Bár a 10 tanult alaptétellel önmagában számos feladat megoldható, ám sok esetben kevésnek bizonyul 1 tétel egy komplexebb feladat megoldására. Ez azonban könnyen orvosolható, hiszen semmi nem akadályozza az embert abban, hogy egy feladathoz több tételt is felhasználjon.

Példa

Van nekem egy tömböm, ami egy osztály diákjainak átlagát tartalmazza. Szeretném kideríteni, hogy ha a minimum 4,5-ös átlagú diákokat nem számolnánk, akkor mennyi lenne az osztály átlaga.

Ez egy olyan feladat ami egy tétellel nem oldható meg, ugyanis egyik tanult tétellel sem tudunk úgy összegezni, hogy azt feltételhez kötjük (átlag < 4,5).

Itt jön képbe a tételösszeépítés.

A feladathoz mindenképpen kell egy összegzés (átlagszámításhoz). Ám az összegzést nem az eredeti tömbön kell elvégezni, hanem egy olyan tömbön, ami az összes 4,5 alatti átlagot tartalmazza. Ezt egy kiválogatással tudjuk elvégezni. Lásd a példa feladat megoldását itt

Ez a konkrét példa egy olyan tételösszeépítést használ, aminek külön neve is van, "feltételes összegzés". A következőkben ilyen, külön elnevezéssel is bíró tételösszeépítések szerepelnek.

FONTOS: Bármely tétel összeépíthetű bármely másikkal! Az alábbi nevezetes összeépítések csupán egy apró részhalmaza a lehetséges opcióknak.

Halmazszerű tömb

Használt tételek: kiválogatás + eldöntés

Specifikáció


        Be: elemszam ∈ N, elemek ∈ N[1..elemszam]
        Ki: hdb ∈ N, halmaz ∈ N[1..hdb]
        Fv: volt: N -> L, volt(i)=VAN(j=1..i-1, elemek[j] = elemek[i])
        Ef: -
        Uf: (hdb, halmaz) = KIVÁLOGAT(i=1..elemszam, nem volt(i))

Algoritmus


        Változó
            i: Egész
        hdb := 0
        Ciklus i=1-től elemszam-ig
            Ha nem volt(i) akkor
                hdb := hdb + 1
                halmaz[hdb] := elemek[i]
            Elágazás vége
        Ciklus vége

        Függvény volt(i: Egész): Logikai
            Változó
                j: Egész
            j := 1
            Ciklus amíg j <= i-1 és nem elemek[j] = elemek[i]
                j := j + 1
            Ciklus vége
            volt := j <= i-1
        Függvény vége

Metszet

Specifikáció


        Be: elemszám1 ∈ N, elemek1 ∈ H[1..elemszám1], elemszám2 ∈ N, elemek2 ∈ H[1..elemszám2]
        Ki: db ∈ N, metszet ∈ H[1..db]
        Fv: bennevan: H -> L, bennevan(elem)=VAN(i=1..elemszám2,elemek2[i]=elem)
        Ef: halmaze(elemek1, elemszám1) és halmaze(elemek2, elemszám2)
        Uf: (db, metszet)=KIVÁLOGAT(i=1..elemszám1, bennevan(elemek1[i]), elemek1[i]) és halmaze(metszet,db)

Algoritmus


        Változó
            i: Egész
        db := 0
        Ciklus i=1-től elemszám1-ig
            Ha bennevan(elemek1[i]) akkor
                db := db + 1
                metszet[db] := elemek1[i]
            Elágazás vége
        Ciklus vége

        Függvény bennevan(elem: H): Logikai
            Változó
                i: Egész
            i := 1
            Ciklus amíg i <= elemszám2 és nem elemek2[i] = elem
                i := i + 1
            Ciklus vége
            bennevan := i <= elemszám2
        Függvény vége

Unió

Specifikáció


        Be: elemszám1 ∈ N, elemek1 ∈ H[1..elemszám1], elemszám2 ∈ N, elemek2 ∈ H[1..elemszám2]
        Ki: db ∈ N, unió ∈ H[1..db]
        Fv: bennevan: H -> L, bennevan(elem)=VAN(i=1..elemszám2,elemek2[i]=elem)
        Ef: halmaze(elemek1, elemszám1) és halmaze(elemek2, elemszám2)
        Uf: (db, unió)=MÁSOL(i=1..elemszám1, bennevan(elemek1[i]), elemek1[i]) ⊕ KIVÁLOGAT(i=1..elemszam2, nem bennevan(elemek2[i]), elemek2[i]) és halmaze(unió,db)

FONTOS: a '⊕' (:= sorozat összeadás) szimbólum nem értelmezett az ELTE-s specifikációs rendszerben, ettől még helyes!

Algoritmus


        Változó
            i: Egész
        Ciklus i=1-től elemszám1-ig
            unió[i] := elemek1[i]
        Ciklus vége
        db := elemszám1
        Ciklus i=1-től elemszám2-ig
            Ha nem bennevan(elemek2[i]) akkor
                db := db + 1
                unió[db] := elemek2[i]
            Elágazás vége
        Ciklus vége

        Függvény bennevan(elem: H): Logikai
            Változó
                i: Egész
            i := 1
            Ciklus amíg i <= elemszám1 és nem elemek1[i] = elem
                i := i + 1
            Ciklus vége
            bennevan := i <= elemszám1
        Függvény vége

Feltételes összegzés

Specifikáció


        Be: elemszam ∈ N, elemek ∈ H[1..elemszam]
        Ki: ossz ∈ H
        Ef: - 
        Uf: ossz=SZUM(i=1..elemszam, elemek[i], T(elemek[i]))

Algoritmus


        Változó
            i: Egész
        ossz := 0
        Ciklus i=1-től elemszam-ig
            Ha T(elemek[i]) akkor
                ossz := ossz + elemek[i]
            Elágazás vége
        Ciklus vége

Feltételes maximum-/minimumkeresés

Specifikáció


        Be: elemszam ∈ N, elemek ∈ H[1..elemszam], T:H->L
        Ki: van ∈ L, maxind ∈ Z, maxert ∈ H
        Ef: -
        Uf: (van,maxind,maxert)=MAXHA(i=1..elemszam, elemek[i], T(elemek[i]))

Algoritmus


        Változó
            i: Egész
        maxert := -∞
        maxind := 0        
        Ciklus i=1-től elemszam-ig
            Ha T(elemek[i]) és maxert < elemek[i] akkor
                maxind := i
                maxert := elemek[i]
            Elágazás vége
        Ciklus vége
        van := maxind > 0

Ablakléptetés (09-26)

Olyan

Specifikáció


        Be: elemszam ∈ N, elemek ∈ H, k ∈ N
        Ki: kezd ∈ N
        Fv:
        Ef:
        Uf: ()

Algoritmus

További linkek

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 5. 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 6. 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 7. 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 9. előadás (ppt) (előadó: Törley Gábor)