[[:oktatas:programozás:Programozási_tételek|< Programozási tételek]]

====== Programozási tételek ======

  * **Szerző:** Sallai András
  * Copyright (c) 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 <nowiki>(=)</nowiki> jelenti,
az egyenlőség vizsgálatot két egyenlőségjel <nowiki>(==)</nowiki> jelzi, a nem egyenlőt egy kisebb-mint
és egy nagyobb-mint jel jelzi <nowiki>(<>)</nowiki>.


===== Összegzés =====


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

{{:oktatas:programozás:programozási_tételek:osszegzes-tetel.png?|}}





===== 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

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

{{:oktatas:programozás:programozási_tételek:megszamolas-tetel.png?|}}


===== Eldöntés =====

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


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


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:

<code>
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
</code>


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

{{:oktatas:programozás:programozási_tételek:eldontestetel.png?|}}


===== Kiválasztás =====


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

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




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.

{{:oktatas:programozás:programozási_tételek:kivalasztastetel.png?|}}



===== 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.

<code>
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
</code>


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


{{:oktatas:programozás:programozási_tételek:keresestetel.png?|}}

===== Másolás =====

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

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

{{:oktatas:programozás:programozási_tételek:masolastetelek.png|}}

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.

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


{{:oktatas:programozás:programozási_tételek:kivalogatastetel.png?|}}


===== Szétválogatás =====

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

<code>
a = {3, 2, 7, 1, 4, 8, 15, 17}
b = {}
c = {}
</code>


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. 

<code>
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
</code>


{{:oktatas:programozás:programozási_tételek:szetvalogatastetel.png?|}}

===== 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:





{{:oktatas:programozás:programozási_tételek:metszettetel.png?|}}










<code>
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
</code>

===== 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.


{{:oktatas:programozás:programozási_tételek:uniotetel.png?|}}





<code>
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
</code>




===== 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:

<code>
max = t[0]
ciklus i = 1 .. n - 1
    ha t[i]> max akkor 
        max = t[i]
    ha vége
ciklus vége
ki max
</code>
Elég ha a második elemtől hasonlítunk össze, ezért az i kezdetben nem 0 helyett 1.


{{:oktatas:programozás:programozási_tételek:maximumkivalasztastetel.png?|}}

===== Minimum kiválasztás =====
Keressük a legkisebb elemet

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


{{:oktatas:programozás:programozási_tételek:minimumkivalasztastetel.png?|}}
====== 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:

{{:oktatas:programozás:programozási_tételek:buborekrendezes.png|}}



Struktogrammal:

{{:oktatas:programozás:programozási_tételek:buborekrendezesstruktogram.png|}}



===== 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.

<code>
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
</code>
===== Rendezés maximum kiválasztással =====
Kiválasztjuk a legnagyobb elemet és a tömb végére rakjuk.

<code>
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
</code>

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

<code>
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
</code>

===== 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.

<code>
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
</code>

===== 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
<code>
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
</code>


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<sup>k</sup> (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<sup>k</sup>-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<sup>i+1</sup> + 3·2<sup>i</sup> + 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. 
A rendezendő tömböt/listát kettéosztjuk, majd ami kisebb a támpontnál azt kisebb, ami nagyobb azt a nagyobb és ami egyenlő azt egy egyenlő tömbbe rakom. A végén összefűzöm a három tömböt. 
A kisebb és nagyobb tömbre külön-külön alkalmazom a gyorsrendezést. 

<code>
function quicksort(list) 
	if meret(list) <= 1 akkor
		return list
	var list less, equal, greater
	pivot = list[meret(list)-1]
	for each x in lista 
		if x<pivot then append x to less
		if x==pivot then append x to equal
		if x>pivot then append x to greater
	return concatenate(quicksort(less), equal, quicksort(greater))
</code>



===== Ö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:
| 3 | 6 | 7 |

| 2 | 5 | 8 |



Indexel megjelölöm a legkisebbet:
| 3 | 6 | 7 |
| <nowiki>^</nowiki> | 

| 2 | 5 | 8 |
| <nowiki>^</nowiki> |


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


| 2 | | | | | |


Az indexmutató ugrik:

| 3 | 6 | 7 |
| <nowiki>^</nowiki> | 

| 2 | 5 | 8 |
| | <nowiki>^</nowiki> |


Az indexek által mutatott kisebbet megint elteszem:


| 2 | 3 | | | | |


Az indexet beállítom:

| 3 | 6 | 7 |
| | <nowiki>^</nowiki> | 

| 2 | 5 | 8 |
| | <nowiki>^</nowiki> |


A kisebbet megint kiemelem:



| 2 | 3 | 5 | | | |

Az indexeket igazítom:

| 3 | 6 | 7 |
| | <nowiki>^</nowiki> | 

| 2 | 5 | 8 |
| | | <nowiki>^</nowiki> |


Kisebbet elteszem:



| 2 | 3 | 5 | 6 | | |


Indexeket igazítom:

| 3 | 6 | 7 |
| | |  <nowiki>^</nowiki> | 

| 2 | 5 | 8 |
| | | <nowiki>^</nowiki> |



Elteszem:



| 2 | 3 | 5 | 6 | 7 | |

Igazítom:

| 3 | 6 | 7 |
| | | | | <nowiki>^</nowiki> | 

| 2 | 5 | 8 |
| | | <nowiki>^</nowiki> |


Elteszem a kisebbet:



| 2 | 3 | 5 | 6 | 7 | 8 |

Indexet állítok:

| 3 | 6 | 7 |
| | | | | <nowiki>^</nowiki> | 

| 2 | 5 | 8 |
| | | | <nowiki>^</nowiki> |



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ő.



<code>
ö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
</code>

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: <m>log_2 n</m>.


<code>
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

</code>


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