szuchi.hu

Szuchi Dániel Blogja

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

comments

Powered by Facebook Comments