[[: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 (:=) jelenti,
az egyenlőség vizsgálatot egy darab egyenlőségjel (=) jelzi, a nem egyenlőt egy kisebb-mint
és egy nagyobb-mint jel jelzi (<>).
(A rendezés tételtelek egyelőre a pascal szintaxis szerint vannak leírva).
===== Összegzés =====
osszeg = 0
ciklus i = 1 .. n
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 = 1 .. n
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 = 1 .. n
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 = 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
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 = 1
ciklus amíg tomb[i] <> ker
i = i + 1
ciklus vége
ki i
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 = 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
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.
j = 1
ciklus i = 1 .. n
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
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.
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
===== 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 = 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
===== 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 = 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
===== 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:
max = 0
ciklus i = 1 .. n
ha t[i]> max akkor
max = t[i]
ha vége
ciklus vége
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:
max = t[1]
ciklus i = 2 .. n
ha t[i]> max akkor
max = t[i]
ha vége
ciklus vége
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
min=t[1]
ciklus i = 1 .. n
ha t[i] < min
min = t[i]
ha vége
ciklus vége
====== 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.
- 2k (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, ...
- 2k-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
- 4i+1 + 3·2i + 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 |
| ^ |
| 2 | 5 | 8 |
| ^ |
A kettő közül a kisebbet elteszem:
| 2 | | | | | |
Az indexmutató ugrik:
| 3 | 6 | 7 |
| ^ |
| 2 | 5 | 8 |
| | ^ |
Az indexek által mutatott kisebbet megint elteszem:
| 2 | 3 | | | | |
Az indexet beállítom:
| 3 | 6 | 7 |
| | ^ |
| 2 | 5 | 8 |
| | ^ |
A kisebbet megint kiemelem:
| 2 | 3 | 5 | | | |
Az indexeket igazítom:
| 3 | 6 | 7 |
| | ^ |
| 2 | 5 | 8 |
| | | ^ |
Kisebbet elteszem:
| 2 | 3 | 5 | 6 | | |
Indexeket igazítom:
| 3 | 6 | 7 |
| | | ^ |
| 2 | 5 | 8 |
| | | ^ |
Elteszem:
| 2 | 3 | 5 | 6 | 7 | |
Igazítom:
| 3 | 6 | 7 |
| | | | | ^ |
| 2 | 5 | 8 |
| | | ^ |
Elteszem a kisebbet:
| 2 | 3 | 5 | 6 | 7 | 8 |
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).
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