szit

Ez az oldal csak olvasható. Megtekintheted a forrását, de nem változtathatod meg. Ha úgy gondolod, hogy ez helytelen, kérdezd az Adminisztrátorokat!
[[: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, 2014
  * Licenc: [[https://creativecommons.org/licenses/by-sa/4.0/|CC BY-SA 4.0]]
  * Web: https://szit.hu

Ez megegyezik a szimpla "Mondatszerű leírások résszel, azzal a különbséggel, hogy
a Pascal nyelvhez igazodva, mindenhol 1-es indexel kezdődnek a tömbindexek. 

===== 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 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 1-gyel kezdem. Az értékadást egy kettőspont és egy darab egyenlőségjel <nowiki>(:=)</nowiki> jelenti,
az egyenlőség vizsgálatot egy darab egyenlőségjel <nowiki>(=)</nowiki> jelzi, a nem egyenlőt egy kisebb-mint
és egy nagyobb-mint jel jelzi <nowiki>(<>)</nowiki>.

(A rendezés tételtelek egyelőre a pascal szintaxis szerint vannak leírva).
===== Összegzés =====


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



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




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

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


<code>
  van = 0
  ciklus i = 1 .. n
    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 = 1
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!



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


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

<code>
i = 1
ciklus amíg tomb[i] <> ker
    i = i + 1
ciklus vége
ki i
</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.




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





===== 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 = 1
ciklus i = 1 .. n
    ha a[i] < 5 
        b[j] = a[i]
        j = j + 1
    ha vége
ciklus vége
</code>





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

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

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-nél, különben c-ben tároljuk. 

<code>
j = 1
k = 1
ciklus i = 1 .. n
    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>



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
















<code>
k = 1
ciklus i = 1 .. n
    j = 1
    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.








<code>
ciklus i = 1 .. n
    c[i] = a[i]
ciklus vége 
k = n
ciklus j = 1 .. m
    i = 1
    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 következő megoldás akkor működik, ha nincs negatív vagy nulla érték a tömbben:

<code>
max = 0
ciklus i = 1 .. n
    ha t[i]> max akkor 
        max = t[i]
    ha vége
ciklus vége
</code>

A másik lehetőség, hogy 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[1]
ciklus i = 2 .. n
    ha t[i]> max akkor 
        max = t[i]
    ha vége
ciklus vége
</code>
Ebben a formában viszont elég ha a második elemtől hasonlítunk össze. 

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

<code>
min=t[1]
ciklus i = 1 .. n
    ha t[i] < min 
        min = t[i]
    ha vége
ciklus vége
</code>
====== Rendezések ======

===== Buborékrendezés =====

A sorozat két utolsó elemét összehasonlítjuk, és ha fordított sorrendben vannak felcseréljük.

  ciklus i := n-1 .. 1
    ciklus j := 1 .. i
      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és megvalósítható lentről felfelé és fentről lefelé is.

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

  Ciklus i := 1 .. n-1
    Ciklus j := i+1 .. n
      Ha T[i] > T[j] akkor
         Csere(i,j)
      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
    max := i
    ciklus j := 1 .. i
      ha t[j] > t[max] akkor max := j
    ciklus vége
    csere(t[i], t[max])
  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 := 1 .. n-1
    min := i
    ciklus j := i+1  .. n
      ha T[j] < T[min] akkor 
        min := j 
      Elágazás vége
    ciklus vége
    ha min <> 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 := 2 .. n
    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 1
  t = tömb(8, 9, 4, 7, 6, 3, 2, 1, 5);
  h = tömb(5, 3, 1);
  
  ciklus k := 1 .. 3 
    lepes := h[k]
    ciklus j := lepes + 1  .. n
      i := j - lepes; 
      x := t[j]
      ciklus amíg i > 0 és t[i] > x 
        t[i + lepes] := t[i]
        i = i - lepes
      Ciklus vége    
      t[i + lepes] := x
    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<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)
    * 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.



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



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



====== Ö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 := 1
    j := 1
    k := 0
    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