< Programozási tételek

Programozási tételek

Szerző: Sallai András

Copyright © Sallai András, 2011, 2014

Licenc: 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.

_Átalakítás alatt_!

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