4. Összetett programozási tételek II

Metszet:

Típusfeladatok közös jellemzői:

• Több sorozathoz egy sorozatot rendelünk
• Két sorozat közös(megegyező) elemeit kell kiválogatni

Megvalósítási ötlet:

• Válogassuk ki az egyik sorozat(X) azon elemeit, amelyek a másikban(Y) is szerepelnek
• Ötvözzük a kiválogatás és eldöntés tételeket

Pszeudokód(X: egyik feldolgozandó tömb, M: X elemeinek száma, Y: másik feldolgozandó tömb, N: Y elemeinek száma, Z: eredménytömb, DB: Metszeti elemek száma):

Eljárás Metszet(X, M, Y, N, Z, DB)

DB<-0

Ciklus i<-1-től M-ig

j<-1

Ciklus j<=N és X[i]!=Y[j]

j<-j+1

Ciklus vége

Ha j<=N akkor

DB<-DB+1; Z[DB]<-X[i];

Elágazás vége

Ciklus vége

Eljárás vége

Megjegyzések:

Kis módosítással a metszet tétel nem csak két sorozat közös elemeinek meghatározására alkalmazható

• Eldöntés: Van-e a sorozatoknak közös eleme?
• Kiválasztás: Két sorozat egyik közös elemének megadása (ha tudjuk, hogy van ilyen)
• Keresés: Adjuk meg a két sorozat közös elemét, ha van
• Megszámlálás: Hány közös eleme van a két sorozatnak?

Egyesítés:

Típusfeladatok közös jellemzői:

• Két sorozathoz egy sorozatot rendel
• Azokat az elemeket keressük, amely két sorozatból legalább az egyikben szerepel.

Pszeudokód(X: egyik feldolgozandó tömb, M: X elemeinek száma, Y: másik feldolgozandó tömb, N: Y elemeinek száma, Z: Eredmény tömb, DB: unióbeli elemek száma):

Eljárás Egyesítés(X, M, Y, N, Z, DB)

Z<-X; DB<-M;

Ciklus j<-1-től N-ig

i<-1

Ciklus amíg i<=M és X[i]!=Y[j]

i<-i+1

Ciklus vége

Ha i>M akkor

DB<-DB+1; Z[DB]<-Y[j];

Elágazás vége

Ciklus vége

Eljárás vége

Módosítás:

Halmazfelsorolás készítése. Egy sorozatból halmazt készít, vagyis kiszűri a többször szereplő elemeket és minden elemből csak egy fog szerepelni.

Pszeudokód(X: eredeti sorozat, N: X elemeinek száma, Z: halmazzá alakított sorozat, DB: Z elemeinek száma):

Eljárás HalmazfelsorolásKészítése(X, N, Z, DB)

DB<-0

Ciklus i<1-től N-ig

j<-1

Ciklus amíg j<=DB és X[i]!=Z[j]

j<-j+1

Ciklus vége

Ha j>DB akkor

DB<-DB+1

Z[DB]<-X[i]

Elágazás vége

Ciklus vége

Eljárás vége

Összefuttatás:

Típusfeladatok közös jellemzői:

• Az egyesítéshez képest itt speciális, hogy mindegyik sorozat rendezett!

Pszeudokód(X: egyik feldolgozandó tömb, M: X elemeinek száma, Y: Másik feldolgozandó tömb, N: Y elemeinek száma, Z: eredmény tömb, DB: Unióbeli elemszám):

Eljárás Összefuttatás(X, M, Y, N, Z, DB)

i<-1; j<-1; DB<-0;

Ciklus amíg i <= M és j<=N

DB<-DB+1

Elágazás

X [i] < Y [j] esetén Z [DB] <- X [i]; i <- i + 1
X [i] = Y [j] esetén Z [DB] <- X [i]; i <- i + 1; j <- j + 1
X [i] > Y [j] esetén Z [DB] <- Y [j]; j <- j + 1

Elágazás vége

Ciklus vége

Ciklus amíg i<=M

DB <- DB + 1; Z [DB] <- X [i]; i <- i + 1

Ciklus vége

Ciklus amíg j<=N

DB <- DB + 1; Z [DB] <- Y [j]; j <- j + 1

Ciklus vége

Eljárás vége

Módosított az utolsó két ciklusra nincs szükség:

Eljárás Összefuttatás(X, M, Y, N, Z, DB)

i<-1; j<-1; DB<-0;

X [M + 1] <- +∞; Y [N + 1] <- +∞

Ciklus amíg i <= M+1 vagy j<=N+1

DB<-DB+1

Elágazás

X [i] < Y [j] esetén Z [DB] <- X [i]; i <- i + 1
X [i] = Y [j] esetén Z [DB] <- X [i]; i <- i + 1; j <- j + 1
X [i] > Y [j] esetén Z [DB] <- Y [j]; j <- j + 1

Elágazás vége

Ciklus vége

Eljárás vége

Módosítás ha nincs a két bemeneti sorozatban két egyforma elem:

Eljárás Összefuttatás(X, M, Y, N, Z, DB)

i<-1; j<-1; DB<-0;

X [M + 1] <- +∞; Y [N + 1] <- +∞

Ciklus amíg i <= M+1 vagy j<=N+1

DB<-DB+1

Ha X [i] < Y [j] akkor

Z [DB] ← X [i]; i ← i + 1

különben

Z [DB] ← Y [j]; j ← j + 1

Elágazás vége

Ciklus vége

Eljárás vége

Felhasznált Irodalom: Sergyán Szabolcs – Programozás I – 4. előadás diasor

Kommentek

comments

Powered by Facebook Comments