Programozási alapismeretek

Halmazszerű nemtételek (metszet, unió)

Tartalom

További linkek

Források

A metszet és az unió régen külön programozási tételnek voltak tekintve, ám igazából ezek a műveletek más prt-k tétel-összeépítése. További tétel-összeépítések itt találhatók.

Halmazszerű tömb

Egy tömb akkor "halmazszerű", hogy ha nincs azonos értékű eleme.

        Fv: halmaze: H[] x N -> L, halmaze(elemek,méret)= ∀i ∈ [1..méret]: (∀j ∈ [1..méret]: (nem i=j -> nem elemek[i]=elemek[j]))
    

Metszet

Két (vagy több) halmaz közös elemeivel történő művelet.

FONTOS: Az eldöntés melletti második tétel nem feltétlenül kiválogatás, feladattól függően behelyettesíthető megszámolással, kereséssel, stb.

Példa: két tömb közös elemeinek kiválogatása egy harmadik tömbbe.

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ó

Két (vagy több) halmaz összes elemével történő művelet.

FONTOS: Az eldöntés melletti második tétel nem feltétlenül kiválogatás, feladattól függően behelyettesíthető megszámolással, kereséssel, stb.

Példa: két tömb összes elemeinek kiválogatása egy harmadik tömbbe.

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)
        

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
    

További linkek

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)