Tartalomjegyzék
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
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.
- 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)
- Í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, …
- 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.
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.
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))
Ö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), 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