3. Összetett programozási tételek I
Másolás:
Típusfeladatok közös jellemzői:
- Az eredmény és a bemenet megegyező elemszámú
- Az eredmény i. elemét a bemenet i. eleméből lehet előállítani
Pszeudokód(X: feldolgozandó tömb, N: tömb elemeinek száma, Y: eredmény tömb):
Eljárás Másolás(N, X, Y)
Ciklus i<-1-től N-ig
X[i]<-művelet X[i]
Ciklus vége
Eljárás vége
Megjegyzések:
- Az eredmény elemszáma mindig megegyezik a bemenet elemszámával
- A művelet segítségével nem csak szimpla másolást hajthatunk végre, hanem elemi művelettel is manipulálhatjuk a bemenetet(minden bemenet kétszeresét írjuk a kimeneti tömbbe.)
- Az elemek közti összefüggés nem kihasználható
Kiválogatás:
Típusfeladatok közös jellemzői:
- Hasonlít a keresésre, mert itt is adott tulajdonságú elemet(eket) kell megadni, de itt nem csak az elsőt.
- Hasonlít a megszámlálásra is, de itt nem elég megszámolni az adott tulajdonságú elemet(eket), megadni/másolni is kell azokat
Pszeudokód(X: feldolgozandó tömb, N: Tömb elemeinek száma, T: tulajdonság függvény, Y: eredmény tömb, DB: Y tömbbe kiválogatott elemek száma):
Eljárás Kiválogatás(X, N, T, Y, DB)
DB<-0
Ciklus i<-1-től N-ig
Ha T(X[i]) akkor
DB<-DB+1
Y[DB]<-X[i]
Elágazás Vége
Ciklus vége
Eljárás vége
Megjegyzések:
- Az eredmény tömb elemeinek száma előre nem meghatározható, de biztos, hogy a bemeneti tömbnél nem több
- Esetenként az eredménytömbbe csak az indexet másoljuk(i) nem pedig az elem tartalmát(X[i])
Memóriatakarékos módosítás a pszeudokódon:
- Ha a bemeneti tömbre már nincsen szükség, a bemeneti tömb elején is tárolhatjuk az eredmény tömböt
- Konzekvencia: a kód kevesebb memóriát használ
Eljárás Kiválogatás(X, N, T, DB)
DB<-0
Ciklus i<-1-től N-ig
Ha T(X[i]) akkor
DB<-DB+1
X[DB]<-X[i]
Elágazás vége
Ciklus vége
Eljárás vége
Módosítás elemjelöléssel:
- Megoldásként szolgálhat az is ha a tulajdonságfüggvénynek meg nem felelő elemeket(amik kimaradnának a kimeneti tömbből) megjelöljük egy speciális értékkel
- Ez esetben is elveszik a bemeneti tömb!
Eljárás Kiválogatás(X, N, T)
Ciklus i<-1-től N-ig
Ha ¬(T(X[i])) akkor
X[i]<- speciális érték
Elágazás vége
Ciklus vége
Eljárás vége
Szétválogatás:
Típusfeladatok közös jellemzői:
- Egy sorozathoz több sorozatot rendelünk
- Végérvényben a feladatok megoldhatóak kettő vagy több egymás utáni kiválogatással
- A két kiválogatás értelmét veszti, mivel ami nem került be az egyikbe, az a másikba tartozik!
Pszeudokód(X: feldolgozandó tömb, N: tömb elemeinek száma, T: tulajdonság függvény, Y: egyik eredmény tömb, DBY: Y tömb elemszáma, Z: másik eredménytömb, DBZ: Z eredménytömb száma):
Eljárás Kiválogatás(X, N, T, Y, DBY, Z, DBZ)
DBY<-0
DBZ<-0
Ciklus i<-1-től N-ig
Ha T(X[i]) akkor
DBY<-DBY+1
Y[DBY]<-X[i]
különben
DBZ<-DBZ+1
Z[DBZ]<-X[i]
Elágazás Vége
Ciklus vége
Eljárás vége
Megjegyzés:
- Y és Z tömbök mérete előre nem meghatározható, ezért N méretű tömböket foglalunk a memóriában
Módosítás egyetlen tömbben tárolással:
- A T tulajdonságú elemeket a kimeneti tömb elején helyezzük el a többi elem pedig a végén kap helyet
Eljárás Kiválogatás(X, N, T, Y, DBY)
DBY<-0
INDZ<-N+1
Ciklus i<-1-től N-ig
Ha T(X[i]) akkor
DBY<-DBY+1
Y[DBY]<-X[i]
különben
INDZ<-INDZ-1
Y[INDZ]<-X[i]
Elágazás Vége
Ciklus vége
Eljárás vége
Módosítás a bemeneti tömbben tároljuk a szétválogatott elemeket:
Eljárás Szétválogatás(X, N, DB)
E<-1; U<-N; seged<-X[E];
Ciklus amíg E<U
Ciklus amíg E<U és ¬(T(X[U]))
U<-U-1
Ciklus vége
Ha E<U akkor
X[E]<-X[U]; E<-E+1;
Ciklus amíg E<U és T(X[E])
E<-E+1
Ciklus vége
Ha E<U akkor
X[U]<-X[E]; U<-U-1;
Elágazás vége
Elágazás vége
Ciklus vége
X[E]<-seged
Ha T(X[E]) akkor
DB<-E
különben
Db<-E-1
Elágazás vége
Eljárás vége
Magyarázat:
- A fő ciklus(Ciklus amíg E<U) addig megy, amíg össze nem ér a tömb 2 végéről a program. Ez szolgálja azt, hogy az egész tömböt szétválogassuk.
- Az első alciklus(Ciklus amíg E<U és ¬(T(X[U])) ) a tömb hátuljáról indulva elkezdi megvizsgálni, hogy mely elemek nem felelnek meg a tulajdonság függvénynek.
- Ahogy az első alciklus talál egy elemet ami megfelel a tulajdonság függvénynek, leáll és a kód tovább fut
- Megvizsgáljuk, hogy E még mindig kisebb-e mint U, ha igen, akkor az aktuális elemet ami megfelel neki berakja a tömb E indexű mezőjébe és E-t inkrementálja.
- Ezután a második alciklus elkezdi E-től vizsgálni a tömb elemeit, hogy megfelelnek e a tulajdonság függvénynek. Ha talál egy olyat ami nem felel meg, kilép az alciklusból és megnézi, hogy E még mindíg kisebb-e mint U. Ha igen Berakja X[U] az X[E]-t és dekrementálja U-t.
- Ezután előre ugrik a főciklushoz és ha E<U akkor továbbpörög a rendszer, ha nem, akkor kilép és X[E]-be berakja a seged változót és megvizsgálja, hogy megfelel-e a tulajdonságfüggvénynek. Ez azért fontos, hogy tudjuk a tömbben meddig vannak a T tulajdonságú elemek (azokat rendezi előre!)!
Felhasznált Irodalom: Sergyán Szabolcs – Programozás I – 4. előadás diasor
Kommentek
Powered by Facebook Comments