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 + 1Elá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 + 1Elá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
Powered by Facebook Comments