Programozási tételek

Szerző: Sallai András
Copyright © Sallai András, 2011, 2012, 2013, 2014, 2015, 2017
Licenc: GNU Free Documentation License 1.3
Web: https://szit.hu

A programozás során felmerülő, nyelvtől független elméleti témák. A leírás jegyzet jellegű. Minden visszajelzést szívesen várok.

Bevezetés

A programozási tételek gyakran használt algoritmusokat takarnak. Ezeket az algoritmusokat általában tömbökön hajtjuk végre. Az adatok persze jöhetnek billentyűzetről, fájlból vagy adatbázisból is.

Az itt található feladatok t[ ] tömbön kerülnek végrehajtásra, a t[ ] tömbnek pedig n darab eleme van. Ahol több tömbbel dolgozunk ott az első tömb a[ ], amelynek n eleme van, a második tömb b[ ], amelynek m elem van. Harmadik tömb neve például c[ ]. Az a[ ] tömb ciklus változója szokásosan i, a b[ ] tömbbé j, a harmadik c[ ] tömbbé k.

A tömbök indexelését 0-val kezdem. Az értékadást egy darab egyenlőségjel (=) jelenti, az egyenlőség vizsgálatot két egyenlőségjel (==) jelzi, a nem egyenlőt egy kisebb-mint és egy nagyobb-mint jel jelzi (<>).

Összegzés

osszeg = 0
ciklus i = 0 .. n -1
    osszeg = osszeg + t[i]
ciklus vége
ki osszeg

Megszámolás

Adott feltételek alapján a tömb bizonyos elemeit megszámolom.

Pl.: Megszámoljuk mennyi negatív szám van a tömbben

szamlalo = 0
ciklus i = 0 .. n - 1
    ha t[i] < 0 akkor 
        szamlalo = szamlalo + 1
    ha vége
ciklus vége
ki szamlalo

Eldöntés

Szeretnénk tudni, hogy egy érték megtalálható-e egy tömbben.

  van = 0
  ciklus i = 0 .. n-1
    ha tomb[i] = keresett_ertek akkor
        van = 1
    ha vége
  ciklus vége

A fenti megoldásnak az a hátránya, ha keresett értéket megtaláltuk, a ciklus akkor is tovább megy. Erre megoldást ad, ha a olyan ciklus állítunk munkába, amelyet akkor szoktunk használni, ha nem tudjuk meddig kell menni. Itt pedig ezzel van, dolgunk. Hogy hol lesz a keresett érték nem tudjuk, de ha meg van, le kell állni. Kell egy feltétel, hogy a ciklus addig menjen amíg nincs meg. Egy másik pedig, miszerint a ciklus addig menjen amíg van adat (nincs vége a tömbnek).A következő algoritmus megvalósítja ezt:

i = 0
ciklus amíg i<n és t[i]<> ker
    i=i+1
ciklus vége

Ha i<n akkor
    ki "Van ilyen" 
különben
    ki "A keresett érték nem található"
ha vége

A ker változó tartalmazza a keresett értéket, a tömb 0-tól van indexelve!

Kiválasztás

Az adott elem a tömb hányadik helyén van

i = 0
ciklus amíg tomb[i] <> ker
    i = i + 1
ciklus vége
ki i + 1

A kiválasztás tételt akkor használjuk, ha tudjuk, hogy a keresett értéket tartalmazza a tömb. Ezért az nem vizsgáljuk, hogy vége van-e a tömbnek. A példában a ker változó tartalmazza a keresett értéket.

Keresés

Lineáris vagy szekvenciális keresés néven is ismert, mivel végig megyünk a számokon sorba.

Adott elem szerepel-e a tömbben és hányadik helyen.

ker = 30
i = 0
ciklus amíg i<n és t[i]<>ker
    i = i + 1
ciklus vége

Ha i<n akkor
    ki "Van ilyen" 
    ki: "Indexe: ", i
különben
    ki: "A keresett érték nem található"
ha vége

Ha nincs ilyen elem, akkor erről értesítjük a felhasználót.

Másolás

Egy sorozat elemeit átmásolom egy másik sorozatba, miközben valamilyen átalakítást végzek az egyes elemeken.

ciklus i = 1 .. n    
    b[i] = művelet(a[i]) //valamilyen művelet a[i]-vel
ciklus vége

A példa kedvéért: Legyen például egy mondat, amelynek szavai szóközzel vannak tagolva. Szeretnénk a szóközöket, alsóvonásra cserélni.

Másik típusfeladat: Adott egy hőmérsékleteket tartalmazó lista. Írassuk a másik tömbbe, hogy mikor volt fagypont. Fagypontot volt ha a hőmérséklet ⇐ 0.

Kiválogatás

A tömb elemit egy másik tömbbe rakom, feltételhez kötve.

Például: Adott a és b tömb. Az a tömb egész számokat tartalmaz. Az a tömbből az 5-nél kisebb számokat átrakom b tömbbe.

j = 0
ciklus i = 0 .. n - 1
    ha a[i] < 5 
        b[j] = a[i]
        j = j + 1
    ha vége
ciklus vége

Szétválogatás

Két tömbbe válogatjuk szét egy tömb elemeit.

a = {3, 2, 7, 1, 4, 8, 15, 17}
b = {}
c = {}

Adott „a” tömb, amely egész számokat tartalmaz. A „b” és „c” tömb pedig üres. Az „a” elemeit „b” tömbbe rakjuk ha kisebbek 5-él, különben c-ben tároljuk.

j = 0
k = 0
ciklus i = 0 .. n-1
    ha a[i] < 5 
        b[j] = a[i]
        j = j + 1
    különben
        c[k] = a[i]
        k = k + 1
    ha vége
ciklus vége

Metszet

Két tömb azonos elemeinek kiválogatása egy harmadik tömbbe

Adott például A és B tömb:

A	5, 3, 6, 2, 1

B	6, 2, 7, 8, 9

A közös elemeket szeretnénk C tömbben:

C	6, 2

Algoritmus:

k = 0
ciklus i = 0 .. n-1
    j = 0
    ciklus amíg j<m és b[j]<>a[i]
        j = j + 1
    ciklus vége
    ha j<m akkor 
        c[k] = a[i]
        k = k + 1
    ha vége
ciklus vége

Unió

A és B tömb minden elemét szeretnénk C tömbbe tenni.

Adott például A és B tömb:

A	5, 3, 6, 2, 1

B	6, 2, 7, 8, 9

Az elemek uniója C tömbben:

C	5, 3, 6, 2, 1, 7, 8, 9

Először C-be tesszük az A összes elemét, majd ami nem szerepel A-ban, azt beletesszük C-be.

ciklus i = 0 .. n-1
    c[i] = a[i]
ciklus vége 
k = n
ciklus j = 0 .. m-1
    i = 0
    ciklus amíg i<n és b[j]<>a[i]
        i = i + 1
    ciklus vége
    ha i>=n akkor
        c[k] = b[j]      
        k = k + 1
    ha vége
ciklus vége

Maximum kiválasztás

Keressük a tömb legnagyobb elemét.

A max kezdeti értéke rögtön az első elem. Ez a megoldás bármilyen halmazon megállja a helyét:

max = t[0]
ciklus i = 1 .. n - 1
    ha t[i]> max akkor 
        max = t[i]
    ha vége
ciklus vége
ki max

Elég ha a második elemtől hasonlítunk össze, ezért az i kezdetben nem 0 helyett 1.

Minimum kiválasztás

Keressük a legkisebb elemet

min=t[0]
ciklus i = 1 .. n-1
    ha t[i] < min 
        min = t[i]
    ha vége
ciklus vége
ki min

Rendezések

Buborékrendezés

Feltételezzük, hogy az n a tömb elemeinek száma.

A sorozat két első elemét összehasonlítjuk, és ha fordított sorrendben vannak felcseréljük. Utána a másodikat és a harmadikat hasonlítom össze.

Ha a nagyobb számokat a végén szeretném látni, akkor az első körben a legnagyobb szám tulajdonképpen a sor végére kerül. Ezért a következő körben azzal már nem foglalkozunk, ezért megyünk mindig a belső ciklusban csak i változó értékéig. A külső ciklus így megmutatja meddig kell mennünk.

ciklus i = n-1 .. 1
  ciklus j = 0 .. i-1
    ha t[j] > t[j+1] akkor 
      b = t[j+1]
      t[j+1] = t[j]
      t[j] = b
    ha vége
  ciklus vége
ciklus vége

A buborék rendezésben az összehasonlításokat a fenti példában a sorozat elején kezdtük. Ezt azonban kezdhettük volna a sorozat végéről is.

Folyamatábrával:

Struktogrammal:

Rendezés cserével

Az aktuális első elemet összehasonlítjuk az utána következőkkel, ha a következő kisebb akkor csere. Utána a második, harmadik, stb. elemmel, hasonlítok és cserélek, ha kell.

Ciklus i := 0 .. n-2
  Ciklus j := i+1 .. n-1
    Ha t[i] > t[j] akkor
       tmp = t[i]
       t[i] = t[j]
       t[j] = tmp
    Elágazás vége
  Ciklus vége
Ciklus vége

Rendezés maximum kiválasztással

Kiválasztjuk a legnagyobb elemet és a tömb végére rakjuk.

ciklus i = n-1 .. 0
  maxIndex = i
  ciklus j = 0 .. i-1
    ha t[j] > t[maxIndex] akkor maxIndex = j
  ciklus vége
  tmp = t[i]
  t[i] = t[maxIndex]
  t[maxIndex] = tmp
ciklus vége

Például a tömb végétől kezdve feltételezem, hogy a legutolsó a legnagyobb. De nem magát a számot, hanem annak indexét jegyzem fel. Ezek után elölről kezdve átnézem, hogy a feltételezettnél nagyobb-e valamelyik. A végén mindenképpen cserélek.

Minimum kiválasztásos rendezés

Megkeressük a legkisebbet és a tömb elejére tesszük

ciklus i = 0 .. n-2
  minIndex = i
  ciklus j = i+1  .. n
    ha t[j] < t[minIndex] akkor 
      minIndex = j 
    Elágazás vége
  ciklus vége
  ha minIndex <> i akkor 
    Csere(i,min) 
  Elágazás vége
ciklus vége

Rendezés beszúrással

Balról veszem a második elemet és haladok jobbra. Ez lesz az aktuális elem. Mindig az aktuális elemtől balra lévő elemhez hasonlítok. Ha a balra lévő nagyobb, cserélek. Ha cseréltem a csere kisebb elemét megint a baloldalihoz hasonlítom. Ha nem cserélek tovább balra haladva, akkor visszamegyek az aktuális elemhez, és ott újra kezdem.

ciklus i = 0 .. n-1
  kulcs = t[i]
  j = i - 1
  ciklus amíg j >= 0 és t[j] > kulcs
    t[j+1] = t[j]
    j = j - 1
  ciklus vége
  t[j+1] = kulcs
ciklus vége

Shell rendezés

Nem csak a szomszédos elemeket hasonlítjuk össze, hanem először távoli indexű értékeket nézzünk, majd folyamatosan csökkentjük a távolságot. Az aktuális távolságot tárolhatom például h tömbben. (Az i értéke felvesz negatív értéket is)

Megvalósítás ha az első index 0

t = tömb(8, 9, 4, 7, 6, 3, 2, 1, 5);
h = tömb(5, 3, 1);
  
ciklus k = 0 .. 2
  lepes = h[k]
  ciklus j = lepes .. n-1
    i = j - lepes; 
    kulcs = t[j]
    ciklus amíg i >= 0 és t[i] > kulcs 
      t[i + lepes] = t[i]
      i = i - lepes
    Ciklus vége    
    t[i + lepes] = kulcs
  Ciklus vége
Ciklus vége

A h tömb tartalmazza lépésszámot. Mindig az adott lépésszámú elemhez hasonlítok a sorozat végéig. Kezdetben ez 5 a példában. Ha elértük a sorozat végét, akkor kisebb lépésközre váltunk, esetünkben ez a 3. A végén 1-es lépésközzel végig megyünk. Ekkor biztosan rendezett a tömb. Az első lépésközt úgy számítjuk, hogy vesszük a tömb felét (n/2), és ahhoz közeli számot választunk. Az utolsó szám mindig az 1-es. A többi lépésköz kiszámítására több elmélet született.

2^k (2 hatványai; ez a legrosszabb választás; nem hatékony)
- 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, …
k · log(k) (Itt az egész részét vettem, ha kerekítek más számok jönnek:)
- 2, 4, 8, 11, 15, 19, 24, 28, 33, 38, …
prímszámok (azok a számok, amelyeknek pontosan két osztójuk van)
- 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, …
fibonacci-számok (Az első két elem 0 és 1, a továbbiakat az előző kettő összeadásával kapom)
- Így kezdődik: 0, 1, 1, 2, 3, 5, de nekünk nem kell az első két szám:
- 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, …
2^k-1 (Hibbard ajánlása)
- 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, …
1-gyel indulunk, a következőben ezt szorozzuk 3-mal majd hozzáadunk 1-t (Knuth ajánlása, 1969)
- 1, 4, 13, 40, 121, 364, 1093, 3280, 9841, …
  - a = 1
  - a = (a * 3) + 1
4ⁱ⁺¹ + 3·2ⁱ + 1 (i >= 0) Robert Sedgewick ajánlása. 20-30% gyorsabb mint a Knuth féle sorozat)
- 1, 8, 23, 77, 281, 1073, 4193, 16577, …

Kis iskolai feladatnál, például 10 elem esetén a lépésköz lehet: 5, 3, 1, esetleg Hibbard ajánlása.

1, 3, 7, 21, 48, 112, 336, 861, 1968, 4592, 13776, 33936, 86961, 198768, 463792, 1391376, 3402672, 8382192, 21479367, 49095696, 114556624, 343669872
1, 4, 13, 40, 121, 364, 1093, 3280, 9841, 29524, 88573, 265720, 797161, 2391484, 7174453, 21523360, 64570081, 193710244, 581130733, 1743392200
1, 8, 23, 77, 281, 1073, 4193, 16577, 65921, 262913, 1050113, 4197377, 16783361, 67121153, 268460033, 1073790977

Az első Incerpi-Sedgewick féle ajánlás. A második Knuth féle ajánlás. Az utolsó a Sedgewick.

Gyorsrendezés

A gyorsrendezés egy rekurzív algoritmus. Kiválasztunk a listából egy elemet támpontnak, angolosan pivotnak.

Egy helyben rendező változatot látunk.

quicksort(array, balIndex, jobbIndex)
    if (balindex < jobbindex>)
        pivotIndex = partition(array, balIndex, jobbIndex)
        quicksort(array, balindex, pivotIndex-1)
        quicksort(array, pivotIndex, jobbIndex)

partition(array, balindex, jobbindex)
    pivot = jobbindex
    i = balIndex - 1
    ciklus j= balIndex .. jobbindex
        ha (array[j] <= pivot)
            i = i + 1
            csere(array[i], array[j])
    csere(array[i+1], array[jobbIndex])
    visszatérünk i + 1

Összefésüléses rendezés

Nem helyben rendezünk, létrehozunk két másik tömböt, amelyben rendezetten vannak az elemek. A két segédlistára indexeket helyezünk el, amelyek mindig a legkisebb elemre mutatnak. A listák aktuális index által mutatott elemeit összehasonlítjuk, a kisebbet az eredeti tömbbe másoljuk. Oszd-meg-és-uralkodj algoritmusnak is nevezik.

Először két kisebb tömbre van szükségünk, amelyek rendezettek:

Indexel megjelölöm a legkisebbet:

3	6	7
^

2	5	8
^

A kettő közül a kisebbet elteszem:

Az indexmutató ugrik:

3	6	7
^

2	5	8
	^

Az indexek által mutatott kisebbet megint elteszem:

Az indexet beállítom:

3	6	7
	^

2	5	8
	^

A kisebbet megint kiemelem:

Az indexeket igazítom:

3	6	7
	^

2	5	8
		^

Kisebbet elteszem:

Indexeket igazítom:

3	6	7
		^

2	5	8
		^

Elteszem:

Igazítom:

3	6	7
				^

2	5	8
		^

Elteszem a kisebbet:

Indexet állítok:

3	6	7
				^

2	5	8
			^

Az egész rendezést azzal kezdem, hogy két részre osztom a tömböt. A két részre osztott tömb ekkor nem rendezett, tehát alkalmatlan a fenti műveletekre. Viszont megtehetem, hogy a bal és jobb oldali tömböt is szintén ketté osztom, azok részeit is, mindaddig, amíg kettő nem marad. Ha csak kettő maradt, akkor már elvégezhető a fenti művelet, így rekurzívan visszafele az egész rendezhető.

összefésül(tömb, p, q, r)
   n1 := q - p + 1
   n2 := r - q
   a bal[1..n1+1] és a jobb[1..n2+1] tömbök létrehozása
   ciklus i := 1 .. n1
       bal[i] := tömb[p+i-1]
   ciklus vége
   ciklus j := 1 .. n2 
       jobb[j] := tömb[q+j]
   ciklus vége
   bal[n1+1] := ∞
   jobb[n2+1] := ∞
   i := 1
   j := 1
   ciklus k := p .. r
       ha bal[i] <= jobb[i]
           tömb[k] := bal[i]
           i := i + 1
       ellenben
           tömb[k] := jobb[j]
           j := j + 1
       ha vége
   ciklus vége
eljárás vége

Összefésülő-rendezés(tömb, p, r)
    ha p < r
        q := (p+r)/2
        Összefésülő-rendezés(tömb, p, q)
        Összefésülő-rendezés(tömb, q+1, r)
        Összefésülés(tömb, p, q, r)
eljrásá vége

A ∞ jel azt jelenti, a tömb legnagyobb eleménél nagyobb elem.

Keresés rendezett tömbben

Ha a tömb rendezett a keresés gyorsabban elvégezhető.

Bináris (logaritmikus vagy felezéses) keresés

Megnézzük a középső elemet. Ha az a keresett szám, akkor vége. Ha nem akkor megnézzük, hogy a keresett elem a tömb alsó vagy felső részében van. Amelyik tömbrészben benne van a keresett szám, a fentieknek megfelelően keresem a számot. A ciklus lépésszáma nagyjából log(n), másként: .

első = 0
utolsó = n-1
ciklus amíg  első <= utolsó
  Középső :=  (Első + Utolsó)  Div 2
  Ha keresett = t[középső] akkor 
    van := igaz
    utolso := középső - 1
  ellenben ha Keresett < t[középső] akkor 
          utolsó := Középső - 1
      Ellenben ha Keresett > t[középső] akkor 
          Első := Középső + 1
      Ha vége
ciklus vége

A végén a van logikai változó mutatja, hogy van-e ilyen elem. Az n a tömb elemeinek a száma.

Összefuttatás

Összefuttatás, összefésülés

Itt is két tömb unóját szeretném megkapni, viszont a tömbök most rendezettek, és az unióképzés után szeretném megtartani a rendezettséget.

  i := 0
  j := 0
  k := -1
  ciklus amíg (i< n) és (j<m)
      k := k + 1

      ha a[i] < b[j] akkor 
          c[k] := a[i]
          i := i + 1
      ellenben
      ha a[i] = b[j] akkor 
          c[k] := a[i]
          i := i + 1
          j := j + 1
      ellenben
      ha a[i]> b[j] akkor
          c[k] := b[j]
          j := j + 1
      ha vége
  ciklus vége
  
  ciklus amíg i < n 
      k := k + 1
      c[k] := a[i]
      i := i + 1
  ciklus vége
  
  ciklus amíg j < m 
      k := k + 1
      c[k] := b[j]
      j := j + 1
  ciklus vége

Tartalomjegyzék