Programozás/Algoritmusok
- Az oldalt bárki szerkesztheti. Nem kell hozzá regisztráció. Kérlek, te is segíts kitölteni a tételeket. Ha valami hibát veszel észre, azt javítsd ki, vagy ha nem tudod, akkor jelezd a végén levő Hibák-nál.
- Az itt közölt anyagok nagyrészt a /pub-ban levő jegyzetekből vannak. Az algoritmusok vagy a Java kódok átíratai, vagy a WikiPedia-n és egyéb helyeket fellelt [pszeudó]kódok-ból lettek kialakítva. Kommentekkel próbáltam érthetőbbé tenni az anyagot, több-kevesebb sikerrel. Az ø minden esetben - ahol nincs más írva - a "nincs értelmezve"-t (fordított T) jelenti.
- Semmilyen felelősséget nem vállok az oldalon található hibákból származó hátrányok miatt.
- "Én, mint a pub-ban található anyag szerzője, egyébként hozzájárulok az ilyen felhasználáshoz."
Gyorstalpaló a szerkesztéshez:
=1. szintű címsor= ==2. szintű címsor== ''dőlt betű'' '''vastag betű''' '''''vastag dőlt betű''''' ;definíció :bekezdés ::még beljebb kezdés <pre> kód kód <{per}pre> #számos felsorolás *jeles felsorolás
Az O, Ω, Θ, o, ω jelölések definíciója √
[szerkesztés]Definíciók és magyarázatok
[szerkesztés]- O(g(n))
- {f(n) : (∃c, n0 ≥ 0)(∀n ≥ n0)(0 ≤ f(n) ≤ c*g(n))}
- Azon f(n)függvények halmaza, amelyekhez létezik olyan c konstans és n0 kezdőindex, nemnegatív számok, hogy minden n-re, ami n0-nál nagyobb-egyenlő, az f(n) függvény c*g(n) alatt van.
- Ω(g(n))
- {f(n) : (∃c, n0 ≥ 0)(∀n ≥ n0)(0 ≤ c*g(n) ≤ f(n))}
- Azon f(n)függvények halmaza, amelyekhez létezik olyan c konstans és n0 kezdőindex, nemnegatív számok, hogy minden n-re, ami n0-nál nagyobb-egyenlő, az f(n) függvény c*g(n) felett van.
- Θ(g(n))
- {f(n) : (∃c1, c2, n0 ≥ 0)(∀n ≥ n0)(0 ≤ c1*g(n) ≤ f (n) ≤ c2*g(n))}
- O és Ω együtt teljesül
- Azon f(n) függvények halmaza, amelyekhez léteznek olyan c1, c2 konstansok és n0 kezdőindex, nemnegatív számok, hogy minden n-re, ami n0-nál nagyobb-egyenlő, az f(n) függvény c1*g(n) és c2*g(n) között fut.
- o(g(n))
- {f(n) : (∀c > 0)(∃n0 > 0)(∀n ≥ n0)(0 ≤ f(n) < c*g(n))}
- O szigorítása
- Azon f(n) függvények halmaza, amelyekre teljesül, hogy minden pozitív c konstanshoz létezik pozitív n0 kezdőindex, hogy minden n-re, ami n0-nál nagyobb-egyenlő teljesül, hogy a függvény szigorúan c * g(n) alatt van.
- ω(g(n))
- {f(n) : (∀c > 0)(∃n0 > 0)(∀n ≥ n0)(0 ≤ c*g(n) < f(n))}
- Ω szigorítása
- Azon f(n) függvények halmaza, amelyekre teljesül, hogy minden pozitív c konstanshoz létezik pozitív n0 kezdőindex, hogy minden n-re, ami n0-nál nagyobb-egyenlő teljesül hogy a függvény szigorúan c * g(n) felett van.
Kiegészítés
[szerkesztés]- O, Ω, Θ, o, ω tranzitív
- f(n) = *(g(n)) ∧ g(n) = *(h(n)) ⇒ f(n) = *(h(n))
- mégpedig a nagyobb n0-tól kezdődően
- O, Ω, Θ reflexív
- f(n) = *(f(n))
- önmagában relációban áll, mivel az egyenlőség is megengedett
- Θ szimmetrikus
- f(n) = Θ(g(n)) ⇔ g(n) = Θ(f(n))
- O, Ω, o, ω antiszimmetrikus
- ha f(n) = *(g(n)) ∧ g(n) = *(f(n)) ⇒ f(n) = g(n)
- tehát egyszerre, csak az egyik lehet kisebb, vagy nagyobb mint a másik (f és g közül)
- f(n) = o*(g(n)) ⇔ g(n) = ω*(f(n))
- a fenti képlet kifejezi, hogy az ordó és az omega jelölések egymás ellentettjei
A partíciószám kiszámításának rekurzív algoritmusa √
[szerkesztés]int Partíció(int n) { return Partíció2(n, n); } int Partíció2(int n, int k) { // 1-et csak egyféleképp lehet felbontani, és bármilyen számot 1-esekből csak 1 féleképp lehet felépíteni if (n == 1 || k == 1) return 1; // n-nél nagyobb partíciója nem lehet n-nek: // az n-nél kisebb számokat tartalmazó partíciók, és a csak n-et tartalmazó partíció if (k >= n) return Partíció2(n, n - 1) + 1; return // azon partíciók, amelybe nem vesszük bele a k-t Partíció2(n, k - 1) // és azon partíciók, amelybe belevesszük a k-t + Partíció2(n - k, k); } //////////////megjegyzés if (k >= n) return Partíció2(n, n - 1) + 1; helyett egyszerűbb if (n<1) return 0; if (k > n) return Partíció2(n,n); Ez főleg a probléma változatainak tárgyalása során egyszerűsítés. Például, ha k-nak vagy 3-al vagy 5-el oszhatónak kell lennie.
VeremBol, VeremBe, SorBol, SorBa és a Prioritási sor adattípus SorBol, SorBa műveletek specifikációja √
[szerkesztés]Előtte | Művelet | Utána |
---|---|---|
{V = <a1, ..., an>} | VeremBe(V, x) | {V = <a1, ..., an, x>} |
{0 < n ∧ V = <a1, ..., an>} | VeremBől(V, x) | {V = <a1, ..., an - 1> ∧ x = an} |
{S = <a1, ..., an>} | SorBa(S, x) | {S = <a1, ..., an, x>} |
{0 < n ∧ S = <a1, ..., an>} | SorBól(S, x) | {x = a1 ∧ S = <a2, ..., an>} |
{P = {a1, ..., an}} | PriSorBa(P, x) | {P = Pre(P) ∪ {x}} |
{P ≠ ø} | PriSorBól(P, x) | {x = min(Pre(P)) ∧ P = Pre(P) \ {x}} |
A Halmaz adattípus specifikációja √
[szerkesztés]Nem biztos, hogy ez az!, Az ø itt üres halmazt jelent!
- Értékhalmaz
- Halmaz = { H : H ⊆ E}
- Műveletek
- H: Halmaz, x: E, I: Iterator
Előtte | Művelet | Utána |
---|---|---|
{Igaz} | Létesít(H) | {H = ø} |
{H = H} | Megszüntet(H) | {Igaz} |
{H = H} | Üresít(H) | {H = ø} |
{H = {a1, ..., an}} | Elemszám(H) | {Elemszám = n} |
{H = H} | Eleme(H, x) | {Eleme = x ∈ Pre(H)} |
{H = H} | Bővít(H, x) | {H = Pre(H) ∪ {x}} |
{H = H} | Töröl(H, x) | {H = Pre(H) \ {x}} |
{H = H} | IterKezd(H, I) | {} |
{I = I} | IterAd(I, x) | {} |
{I = I} | IterVege(I) | {} |
A Függvény adattípus Kiolvas, Modosit, Bovit és Torol műveleteinek specifikációja √
[szerkesztés]Java-ban java.util.Map, C++-ban std::map
Műveletek: F: Függvény, k: K, x: A
Előtte | Művelet | Utána |
---|---|---|
{(∃a ∈ A)((k,a) ∈ F)} | Kiolvas(F, k, x) | {x = a ∧ F = Pre(F)} |
{(∀a ∈ A)((k,a) ∉ F)} | Kiolvas(F, k, x) | {F = Pre(F) ∧ x = Pre(x)} |
{(∃a ∈ A)((k,a) ∈ F)} | Módosít(F, k, x) | {F = Pre(F) \ {(k,a)} ∪ {(k,x)} } |
{(∀a ∈ A)((k,a) ∉ F)} | Módosít(F, k, x) | {F = Pre(F) ∧ x = Pre(x)} |
{(∀a ∈ A)((k,a) ∉ F)} | Bővít(F, k, x) | {F = Pre(F) ∪ {(k,x)} } |
{(∃a ∈ A)((k,a) ∈ F)} | Bővít(F, k, x) | {F = Pre(F) ∧ x = Pre(x)} |
{(∃a ∈ A)((k,a) ∈ F)} | Töröl(F, k) | {F = Pre(F) \ {(k,a)} } |
{(∀a ∈ A)((k,a) ∉ F)} | Töröl(F, k) | {F = Pre(F)} |
A Reláció adattípus APar, KPar, ATorol, KTorol műveleteinek specifikációja √
[szerkesztés]Java-ban java.util.Map, C++-ban std::map, vagy ha több érték megengedett egy kulcshoz: java.util.Map<java.util.List>, std::multimap
Előtte | Művelet | Utána |
---|---|---|
{R = R} | KPar(R, k) | {KPar = {a : (k, a) ∈ Pre(R)} } |
APar(R, a) | {APar = {k : (k, a) ∈ Pre(R)} } | |
KTöröl(R, k) | {R = Pre(R) \ {(k,a) : (k,a) ∈ Pre(R)} } | |
ATöröl(R, a) |
Lánc és körlánc absztrakt adatszerkezetek definíciói √
[szerkesztés]Lánc
[szerkesztés]- A = (M, R, Adat) lánc, ha R = {követ},
- követ
- M → M parciális függvény, amelyre teljesül:
- (∃ fej ∈ M)(∀ x ∈ M)(∃! k ≥ 0)(x = követk(fej))
- láncvég
- Pontosan egy olyan c ∈ M cella van, amelyre követ(c) = ø (NULL).
- Lánc hosszán az n számot értjük, mely a cellák számát adja meg.
- Ha n > 0, akkor követn − 1(fej) = láncvég
Körlánc
[szerkesztés]- A = (M, R, Adat) körlánc, ha R = {követ},
- követ
- M → M (totális) függvény, amelyre teljesül:
- (∀x, y ∈ M)(∃k ≥ 0)(y = követk(x))
- bármely x ∈ M-re az <x = x0, x1, ..., xn−1> sorozat, ahol xi = követ(xi−1), i = 1, ..., n − 1, az M halmaz elemeinek egy ciklikus permutációja.
A nem rendezett fa definíciói (bináris reláció, és apa függvény) √
[szerkesztés]Bináris reláció
[szerkesztés]- A = (M, R, Adat) nem-rendezett fa, ha R = {r}, r ⊆ M × M bináris reláció, és van olyan g ∈ M, hogy a G = (M, r) irányított gráfban bármely x ∈ M-re pontosan egy g ~> x út vezet. g-t a fa gyökerének nevezzük.
Apa függvény
[szerkesztés]- Minden nem-rendezett fa egyértelműen megadható egy olyan Apa : M → M parciális függvénnyel, amelyre teljesül a következő feltétel:
- (∃ g ∈ M)((Apa(g) = ø) ∧ (∀x ∈ M)(∃!k ≥ 0)(Apak(x) = g))
- Ha y = Apa(x), akkor azt mondjuk, hogy x apja y és y-nak fia x.
- Az így megadott szerkezeti kapcsolat nem definiál rendezettséget adott x cella {y : Apa(y) = x} fiainak halmazán.
A rendezett fa absztrakt adatszerkezet definíciója fi függvényekkel √
[szerkesztés]- Legyen A = (M, R, Adat) olyan absztrakt adatszerkezet, hogy R = {f}, f : M → (M ∪ {ø})*.
- x ∈ M, f(x) = <y1, ..., yk>, yi ∈ M ∪ {ø}, i = 1, ..., k.
- Minden i > 0 természetes számra definiáljuk az fi : M → M ∪ {ø} függvényt a következőképpen:
- Tehát fi(x) az x i-edik fiát adja. Ha fi(x) = ø, akkor hiányzik az i-edik fiú.
- Az A adatszerkezetet fának nevezzük, ha van olyan g ∈ M, hogy teljesül az alábbi négy feltétel
-
- a gyökér nem fia egyetlen pontnak sem:
- minden, gyökértől különböző pont fia valamely pontnak:
- minden pontnak legfeljebb egy apja lehet:
- minden pont elérhető a gyökérből:
- a gyökér nem fia egyetlen pontnak sem:
Fa absztrakt adatszerkezet algebrai definíciója √
[szerkesztés]Legyen E tetszőleges adathalmaz. Az E-feletti fák Fa(E) halmaza az a legszűkebb halmaz, amelyre teljesül az alábbi három feltétel:
- ø ∈ Fa(E), az E-feletti fák része az üres halmaz
- (∀a ∈ E)a ∈ Fa(E), ha egy adat benne van az adathalmazban, akkor benne van az E-feletti fákban is
- (∀a ∈ E)(∀t1, ..., tk ∈ Fa(E))(a(t1, ..., tk) ∈ Fa(E))
Általános absztrakt adatszerkezet definíciója √
[szerkesztés]- Olyan A = (M, R, Adat) rendezett hármas, ahol
- M az absztrakt memóriahelyek, cellák halmaza.
- R = {r1, ..., rk} a cellák közötti szerkezeti kapcsolatok, ri : M → (M ∪ {ø})*
- Adat : M → E parciális függvény, a cellák adattartalma.
- x ∈ M, r ∈ R és r(x) = <y1, ..., yi, ..., yk> esetén az x cella r kapcsolat szerinti szomszédai {y1, ..., yk}, yi pedig az x cella i-edik szomszédja.
- Ha yi = ø, akkor azt mondjuk, hogy x-nek hiányzik az r szerinti i-edik szomszédja.
Különbségek a gráf és általános absztrakt adatszerkezetek között (nem anyag)
[szerkesztés]- A gráf csak egy szerkezeti kapcsolatot ad meg.
- Gráf esetén a szomszédok halmaza nem rendezett.
- Gráfban nem tudunk hiányzó kapcsolatot megadni.
Fa adatszerkezet kapcsolati tömb, kapcsolati lánc ábrázolásai √
[szerkesztés]Kapcsolati tömb
[szerkesztés]Statikus
[szerkesztés]struct FaPont { ElemTípus elem; FaPont* fiuk[MAXHOSSZ]; int hossz; }
- Memóriaigény
- n * (sizeof(ElemTipus) + MAXHOSSZ * sizeof(FaPont*) + sizeof(int))
- Feltéve, hogy sizeof(FaPont*) = 4 és ElemTípus = int32: 4 * n * (MAXHOSSZ + 2)
- Az ábrázolás előnye
- Minden pont i-edik fia közvetlenül (konstans időben) elérhető.
- Az ábrázolás hátránya
- Statikus, azaz nem lehet konstans időben bővíteni és törölni.
Dinamikus (nem anyag)
[szerkesztés]Ha előre tudjuk a bizonyos pontok gyerekeinek számát, akkor dinamikus foglalással:
struct FaPont { ElemTípus elem; FaPont** fiuk; int hossz; }
- Memóriaigény
- , mivel minden gyereknek legfeljebb egy apja van (gyökérnek nincs).
- Feltéve, hogy sizeof(T*) = 4 és ElemTípus = int32: 16 * n - 4
- Az ábrázolás előnye
- Minden pont i-edik fia közvetlenül (konstans időben) elérhető.
- Az ábrázolás hátránya
- Statikus, azaz nem lehet konstans időben bővíteni és törölni.
Kapcsolati lánc
[szerkesztés]struct FaPont { int n; struct kapcsolo { FaPont* gyerek; kapcsolo* kovetkezo; }; kapcsolo* kapocs; };
- Memóriaigény
- n * (sizeof(ElemTípus) + sizeof(kapcsolo*)) + (n - 1) * (sizeof(FaPont*) + sizeof(kapcsolo*))
- Feltéve, hogy sizeof(T*) = 4 és ElemTípus = int32: 16 * n - 8
Fa adatszerkezet elsőfiú-testvér, elsőfiú-testvér-apa ábrázolásai √
[szerkesztés]Elsőfiú-testvér
[szerkesztés]struct Fa { ElemTípus adat; Fa* elsőfiú; Fa* testvér; };
- Memóriaigény
- n * (sizeof(ElemTípus) + 2 * sizeof(Fa*))
- Feltéve, hogy sizeof(Fa*) = 4 és ElemTípus = int32: 12 * n
Elsőfiú-testvér-apa
[szerkesztés]struct Fa { ElemTípus adat; Fa* elsőfiú; Fa* testvér; Fa* apa; };
- Memóriaigény
- n * (sizeof(ElemTípus) + 3 * sizeof(Fa*))
- Feltéve, hogy sizeof(Fa*) = 4 és ElemTípus = int32: 16 * n
Preorder rekurzív fabejáró algoritmus √
[szerkesztés]PreOrder(Fa fa, Művelet M) { M(fa); for(gyerek : fa.gyerekek) PreOrder(gyerek, M); }
C++-os megvalósítás, elsőfiú-testvér ábrázolással:
struct FaPont { int adat; FaPont* elsőfiú; FaPont* testvér; }; void PreOrder(FaPont* p, void(Művelet*)(FaPont*)) { if (p == NULL) return; Művelet(p); if (p->elsőfiú != NULL) // az if elhagyható, úgyis visszatér ha NULL-t kap PreOrder(p->elsőfiú, M); if (p->testvér != NULL) // az if elhagyható, úgyis visszatér ha NULL-t kap PreOrder(p->testvér, M); }
Szintszerinti fabejáró algoritmus √
[szerkesztés]void SzintSzerint(Fa fa, Művelet M) { Sor<Fa> S; S.push(fa); while(!S.empty()) { Fa f = S.pop(); M(f); for(gyerek : f.gyerekek) S.push(gyerek); } }
Partíció probléma megoldása rekurziómemorizálással √
[szerkesztés]long Particio[][]; long Partíció(int n) { Particio = new long[n][n]; return Partíció2(n,n); } long Partíció2(int n, int k){ if (Particio[n][k] != 0) // Partíció2(n, k)-t már kiszámítottuk return Particio[n][k]; long P_nk; if (k == 1 || n == 1) P_nk = 1; else if (k >= n) P_nk = Partíció2(n, n - 1) + 1; else P_nk = Partíció2(n, k - 1) + Partíció2(n - k, k); Particio[n][k] = P_nk; //memorizálás return P_nk; }
Algoritmust kommentezve lásd: Partíciószám rekurzív algoritmusa
Partíció probléma dinamikus programozási megoldása (táblázat-kitöltéssel) √
[szerkesztés]Az indexelés [oszlop, sor] szerint van. Csak a mátrix felső háromszögét tölti ki, a főátlót és fölötte.
long P(int N) { long tabla[1..N, 1..N]; for (int i = 1; i <= N; i++) // első sor tabla[i, 1] = 1; for (int k = 2; k <= N; k++) { // a k. sor kitöltése tabla[k, k] = tabla[k, k - 1] + 1; // P2(n, n) = P2(n, n - 1) + 1 // P2(n, k) = T2[n, k] számítása for (int n = k + 1; n <= N; n++) { // P2(n, k) = P2(n, n), ha k > n int n1 = (n - k < k)? n - k : k; // P2(n, k) = P2(n, k - 1) + P2(n - k, k) tabla[n, k] = tabla[n, k - 1] + tabla[n - k, n1]; } } return tabla[n, n]; }
Algoritmust kommentezve lásd: Partíciószám rekurzív algoritmusa
Pénzváltási probléma definíciója, részproblémák definíciója, a közöttük levő összefüggések √
[szerkesztés]- Probléma
- Pénzváltás
- Bemenet
- P = {p1, ..., pn} pozitív egészek halmaza, és E pozitív egész szám.
- Tehát P = pénzérmék, és E hogy mennyit szeretnénk kirakni P-ből
- Kimenet
- Olyan S ⊆ P, hogy .
- Tehát azon érmék halmaza, melyek összege kiadja E-t
- Megjegyzés
- A pénzek tetszőleges címletek lehetnek, nem csak a szokásos 1, 2, 5 10, 20, stb., és minden pénz csak egyszer használható a felváltásban.
- Először azt határozzuk meg, hogy van-e megoldás.
- Tegyük fel, hogy
- , tehát a megoldásban szereplő pénzérmék egy sorrendje
- egy megoldása a feladatnak. Ekkor
- megoldása lesz annak a feladatnak, amelynek bemenete a felváltandó érték, és a felváltáshoz legfeljebb a első ik - 1
- pénzeket használhatjuk.
- Részproblémákra bontás
- Bontsuk részproblémákra a kiindulási problémát:
- Minden (X, i)(1 ≤ X ≤ E, 1 ≤ i ≤ N) számpárra vegyük azt a részproblémát, hogy az X érték felváltható-e legfeljebb az első p1, ..., pi pénzzel. Jelölje V(X, i) az (X, i) részprobléma megoldását, ami logikai érték:
- V(X, i) = IGAZ, ha az X összeg előállítható legfeljebb az első i pénzzel, egyébként HAMIS.
- Összefüggések a részproblémák és megoldásaik között
-
- V(X, i) = (X == pi), ha i = 1
- egyetlen érménk van
-
- ha megegyezik a kirakandó értékkel, akkor IGAZ
- egyébként HAMIS
- V(X, i) = V(X, i - 1) ∨ (X > pi) ∧ V(X - pi, i - 1) ha i > 1
- több érménél
-
- kirakható 1-gyel kevesebb érméből
- vagy az érték nagyobb, mint az utolsó érme
- és a vele csökkentett érték kirakható a maradék érmékből
Pénzváltási probléma egy megoldásának előállítása táblázat-kitöltéssel
[szerkesztés]- kötelező mindkét kód, választható, egyébként is egyanaz, csak az egyik Pseudokódan a másik meg Javában van.
int[] PénzVáltás(int E, int P[n]){ boolean kirakhato[0..E][0..n]; for (x = 1..E) // ??? kirakhato[x, 0] = false; kirakhato[0, 0] = true; // semmit, érmék nélkül ki lehet rakni kirakhato[P[0], 0] = true; // ??? for (i = 1..n-1) for (x = 1..E) kirakhato[x, i] = // az aktuális érme kiadja az értéket: P[i] == x // vagy e nélkül az érme nélkül is ki lehet rakni: || kirakhato[x, i - 1] // vagy belevehető az P[i] érme, és belevéve kiarkható: || x > P[i] && kirakhato[x - P[i], i - 1]; int db = 0; x = E; i = n - 1; if (!kirakhato[E, n - 1]) return NULL; //megoldás visszafejtése érmék tömbbe int érmék[0..n] = 0; do { while (i >= 0 && kirakhato[x, i]) i--; érmék[db++] = ++i; x -= P[i]; // csökkenti a kirakandó értéket } while(x > 0); // amíg van mit kirakni return érmék; // 0..db-1 -ig lesz a megoldás, utána 0-k }
- A táblázat kitöltésének logikája:
Olyan kiszámítási sorrendet kell megállapítani, amelyre teljesül, hogy amikor az (X, i) rész- problémát számítjuk, akkor ennek összetevőit már korábban kiszámítottuk. Mivel az (X, 1) részproblémáknak nincs összetevőjük, ezért közvetlenül kiszámíthatóak, azaz a táblázat első sorát számíthatjuk eloször. Ha i > 1, akkor az (X i) részprobléma összetevoi az (X, i − 1) és (X − pi , i − 1), ezért az i-edik sor bármely elemét ki tudjuk számítani, ha már kiszámítottuk az i − 1-edik sor minden elemét. Tehát a táblázat-kitöltés sorrendje: soronként (alulról felfelé), ̋ balról-jobbra haladó lehet.
Akkor és csak akkor van megoldása a problémának, ha a VT táblázat kitöltése után VT[E,N] értéke igaz. Ekkor az (1-2.) képletek szerint a legnagyobb i indexű pi pénz, amely szerepelhet E eloállításában, az a legnagyobb index, amelyre
- VT[E,i] = True ∧ (VT[E,i − 1] = False)
- Java kód
public class PenzValt1{ public static int[] Valto(int E, int[] P){ int n=P.length; int MaxE=1000; boolean VT[][]=new boolean[E+1][n+1]; int i,x; for (x=1; x<=E; x++) //inicializálás VT[x][0]=false; //0 sor végig false VT[0][0]=true; //semmit, érmék nélkül ki lehet rakni VT[P[0]][0]=true; //inicializálás vége for (i=1; i<n; i++) //kitöltjük a táblázatot az összes lehetséges P-re balról-jobbra for (x=1; x<=E; x++) //kitöltjük a táblázatot az összes lehetséges X-re alulról-fölfele VT[x][i]= P[i]==x || VT[x][i-1] || x>=P[i] && VT[x-P[i]][i-1]; int db=0; x=E; i=n-1; if (!VT[E][n-1]) return null; //a fenti összefügének megfelelően eldönti ki lehet-e rakni E-t int C[]=new int[n]; //felhasznált érmék do{ //megoldás visszafejtés while (i>=0 && VT[x][i]) i--; //kikeresi az x-hez az i-k közül a legnagyobb olyat amelyik //esetén az x-et nem lehet kirakni C[db++]=++i; //ekkor az etől 1-gyel nagyobb benne lesz a megoldási listában x-=P[i]; //csökkenti a kirakandó értéket }while(x>0); for (i=db; i<n; i++) C[i]=0; return C; } }
Optimális pénzváltási probléma definíciója, részproblémák definíciója, a közöttük levő összefüggések
[szerkesztés]Optimális pénzváltási probléma megoldása táblázat-kitöltéssel (egy megoldást is előállítani)
[szerkesztés]Mátrixszorzás probléma definíciója, részproblémák definiálása, a közöttük levő összefüggések
[szerkesztés]Hátizsák probléma definíciója, részproblémák definiálása, a közöttük levő összefüggések
[szerkesztés]Optimális bináris keresőfa definíciója, részproblémák definíciója, a közöttük levő összefüggések
[szerkesztés]Optimális bináris keresőfa megoldása táblázat-kitöltéssel (egy optimális bináris keresőfa előállítása)
[szerkesztés]Eseménykiválasztási probléma definíciója, megoldó algoritmus
[szerkesztés]Optimális prefix kód probléma definícója, Huffman-kód szerkesztő algoritmus
[szerkesztés]A Graf adattípus specifikációja √
[szerkesztés]- Irányítatlan gráf
- G = (V, E), E rendezetlen {a, b}, a, b ∈ V párok halmaza.
- Irányított gráf
- G = (V, E), E rendezett (a, b) párok halmaza; E ⊆ V × V.
- Multigráf
- G = (V, E, Ind, Érk), Ind, Érk : E → V; Ind(e) az e él induló, Érk(e) az érkező pontja.
- Ki(G, p) = {q ∈ V : (p, q) ∈ E}
- Be(G, p) = {q ∈ V : (q, p) ∈ E}
- Értékhalmaz
- Gráf = {G = (V, E) : V ⊆ PontTípus, E ⊆ V × V}
- Műveletek
- G : Gráf; p, p1, p2 : PontTípus; I : Iterator; irányított: boolean
Előtte | Művelet | Utána |
---|---|---|
{Igaz} | Létesít(G, irányított?) | {G = (ø, ø)} |
{G = G} | Megszüntet(G) | {Igaz} |
Üresít(G) | {G = (ø, ø)} | |
Irányított(G) | {¬Irányított(G) ⇒ (p, q) ∈ E ⇒ (q, p) ∈ E)} | |
PontokSzáma(G) | {= |V|} | |
ÉlekSzáma(G) | {= |E|} | |
KiFok(G, p) | {= |Ki(G, p)|} | |
BeFok(G, p) | {= |Be(G, p)|} | |
{G = (V, E)} | PontBővít(G, p) | {V = Pre(V) ∪ {p} ∧ E = Pre(E)} |
{G = (V, E) ∧ p ∈ V} | PontTöröl(G, p) | {V = Pre(V) \ {p} ∧ E = Pre(E) \ ( {(p,q) : q ∈ Ki(G, p)} ∪ {(q, p) : q ∈ Be(G, p)} ) } |
{G = (V, E), p1, p2 ∈ V} | ÉlBővít(G, p1, p2) | {E = Pre(E) ∪ {(p1, p2)} ∧ V = Pre(V)} |
ÉlTöröl(G, p1, p2) | {E = Pre(E) \ {(p1, p2)} ∧ V = Pre(V)} | |
VanÉl(G, p1, p2) | {= (p1, p2) ∈ E ∧ E = Pre(E) ∧ V = Pre(V)} | |
{G = G} | KiÉl(G, p) | {= {q : VanÉl(p,q)}} |
PIterator(G, I) | {} | |
KiIterator(G, p) | ||
ÉlIterator(G, I) |
Kapcsolatmátrix, éllista gráf-reprezentációk, Tárigény, VanEl, Eliteráció, KiIteráció időigénye √
[szerkesztés]Kapcsolatmátrix (szomszédsági mátrix)
[szerkesztés]- bool G[|V|, |V|];
- (p, q) akkor és csak akkor éle a gráfnak, ha G[p, q] = true.
- Címkézett (súlyozott) gráf ábrázolására:
boolean[][] G; // Cimke[][] G; //címkézett (súlyozott) gráf ábrázolására
- Címkézett gráf esetén választani kell egy nem ∈ dom(CímkeTípus) értéket, amely nem fordul elő semmilyen él címkéjeként.
- (p, q) akkor és csak akkor éle a címkézett gráfnak, ha G[p, q] != nem, és a (p, q) él címkéjének értéke G[p, q].
- Multi-gráf nem ábrázolható szomszédsági mátrix-al.
Éllista
[szerkesztés]Statikus
[szerkesztés]- int G[|V|, |V|];
- int KiFok[|V|];
Dinamikus
[szerkesztés]- Lánc<int> G[|V|];
Általános
[szerkesztés]- Az általános éllistás ábrázolás előnye, hogy a gráf pontjai tetszőleges (de rögzített) típusú értékek lehetnek.
- Címkézett gráf esetén a ki-lánc (a vízszintes lánc) minden cellája a pont mellett egy címke értéket is tartalmaz.
template<typename PontTípus> struct GráfLánc { PontTípus címke; GráfLánc<PontTípus>* csat; Lánc<PontTípus> ki; }
Igények (n = |V|, m = |E|, k = |Ki(G, p)|)
[szerkesztés]Reprezentáció | Tárigény | VanÉl | Él-iteráció | Ki-iteráció |
---|---|---|---|---|
Kapcsolati mátrix | Θ(n2) | Θ(1) | Θ(n2) | Θ(n) |
Statikus éllista | Tlr = O(n) | Θ(m) | Θ(k) | |
Dinamikus éllista | Θ(n + m) | |||
Általános éllista | Tlr = O(n) + Θ(k) |
Út, legrövidebb út definíciója súlyozott és súlyozatlan gráfokban √
[szerkesztés]Legyen G = (V,E) irányított (irányítatlan) gráf.
- Út
- p, q ∈ V-re egy p-ből q-ba vezető út G-ben, olyan π = <p0, p1, ..., pk> pontsorozat, ahol p = p0, q = pk és pi ≠ pj, ha i ≠ j, vagy p = q = p0, továbbá teljesül (∀i ∈ {1, ..., k})((pi-1, pi) ∈ E).
- Olyan pontsorozat, melynek az eleje p, a vége q és minden eleme különböző vagy a kezdőpont megegyezik a végponttal (kör), továbbá az egymást követő pontokat összekötő él benne van a gráfban.
- Legrövidebb út
-
- π = <p0, p1, ..., pk> = p ~> q út hossza
- |π| = |p ~> q| = k
- Ha G = (V, E, C) élei a C : E → R függvénnyel súlyozottak, akkor a p ~> q út hossza
- .
- p és q távolsága, p-ből q-ba vezető legrövidebb út hossza
Szélességi keresés algoritmusa √
[szerkesztés]Egy adott súlyozatlan irányított vagy irányítatlan gráf egy pontjából keressük az elérhető pontokat, és az azokhoz vezető legrövidebb utakat.
Bemenet: a G = (V, E) gráf és egy kiindulási pont start ∈ V . Kimenet: a legrövidebb utak fája, egy Apa függvény által megadva, és egy d függvény, amelyre d(p) = δ(p) minden p ∈ V -re.
- Megj.: A tombnev[1...Valami.size()] = 0; jelentése, hogy felveszünk egy Valami.size méretű tömböt, és elemeit kinullázzuk 1-től egészen végéig.
szelkeres(Graf G, start) { Sor S; //Inicializálás int apa[1..G.size()] = -1; //A tömb fogja tárolni a G pontjaihoz az apjukat. Egyelőre mind -1 int d[1..G.size()] = ∞; //A tömb fogja tárolni a mélységét a pontnak. Ha végtelen akkor elérhetetlen apa[start] = 0; d[start] = 0; //Inicializálás vége S.push(start); while(!S.empty()) { u = S.pop(); for(v : G[u].ki) { //v végigmegy az u "gyermekein" if(apa[v] == -1) { //megvizsgálja hogy v-hez van-e már apa eltárolva. Ha nincs, //akkor ez lesz a legrövidebb út apa[v] = u; //bejegyzi u-t v apjának. Legrövidebb út d[v] = d[u] + 1; //feljegyzi v mélységi szintjét, u szintjétől eggyel mélyebb szinten lesz S.push(v); } } } }
Mélységi keresés algoritmusa √
[szerkesztés]- Gráfpontok 1-től indexelve
- apa == -1
- fa-gyökér
- apa == 0
- még nem bejárt pont
- Megj.: A tombnev[1...Valami.size()] = 0; jelentése, hogy felveszünk egy Valami.size méretű tömböt, és elemeit kinullázzuk 1-től egészen végéig.
int idő; //globális változó, ezzel számoljuk hogy mennyit mozogunk a gráfban void MélyKeres(Graf G) { //inicializálás d[1..G.size()]; //érkezési idő f[1..G.size()]; //elhagyási idő apa[1..G.size()] = 0; //a pontok apját tároló tömb ki nullázása idő = 0; //inicializálás vége for(p: G.V) if(!apa[p]) { //végig lépked a gráfban lévő fák gyökrein apa[p] = -1; //feljegyzi az apa tömbben hogy gyökerek MélyBejár(G, p); //bejárja a gyökerekhez tartozó fákat } } void MélyBejár(Graf G, int u) { d[u] = ++idő; //növeli eggyel az időt, majd tárolja a ponthoz az érkezési táblán for (v: G[u].ki) if(!apa[v]) { //kiválasztja sorba a pont fiait, és ha nem lett még bejárva bejárja öket sorban apa[v] = u; //feljegyzi az apa táblán v fiuhoz hogy u az apja MélyBejár(G, v); //rekurzivan meghívja magát v-re amíg be nem járja a részfát } f[u] = ++idő; //feljegyzi az elhagyási időt, ekkora u összes részfája be lett járva }
"Színezős MélyKeresés"
[szerkesztés]int idő; void MélyKeres(Graf G) { d[1..G.size()]; f[1..G.size()]; apa[1..G.size()] = -1; szín[1..G.size()] = fehér; idő = 0; for(p: G.V) if(szín[p] == fehér) MélyBejár(p); } void MélyBejár(Graf G, int u) { szín[u] = szürke; d[u] = ++idő; for (v: G[u].ki) if(szín[u] == fehér) { apa[v] = u; MélyBejár(v); } f[u] = ++idő; szín[u] = fekete; }
Zárójelezési tétel
[szerkesztés]Mélységi keresést alkalmazva a G = (V,E) gráfra, a következő három feltétel közül pontosan az egyik teljesül minden u és v pontra:
1. A [ d(u) , f(u) ] és [ d(v) , f(v) ] intervallumok diszjunktak és az u és v pontok egyike sem leszármazottja a másiknak a Mélységi Feszítő Erdőben (MFE).
2. [ d(v) , f(v) ] ⊆ [ d(u) , f(u) ] és v leszármazottja u-nak a MFE-ben.
3. [ d(u) , f(u) ] ⊆ [ d(v) , f(v) ] és u leszármazottja v-nek a MFE-ben.
/* d -> elérési-, f -> elhagyási idő , MFE = (V,F) : F = {(p,q) : Apa(q) = p} */
Élek osztályozása (faél, előre él, visszaél, keresztél definíciója) √
[szerkesztés]- (u, v) ∈ V , (MFE = Mélységi Feszítő Erdő)
- Faél
- ha bekerül a MFE élei közé, azaz Apa(v) = u
- u → v él vizsgálatakor Szín(v) = fehér
- vagy másképp: ∃ u ~> v ∈ MFE út és |u ~> v| = 1
- Visszaél
- ha u leszármazottja v-nek a MFE-ben
- u → v él vizsgálatakor Szín(v) = szürke
- Előreél
- ha v leszármazottja u-nak a MFE-ben és nem faél , azaz Apa(v) ≠ u;
- u → v él vizsgálatakor Szín(v) = fekete és d(u) < d(v)
- vagy másképp: ∃ u ~> v út és |u ~> v| > 1
- Keresztél
- Minden más esetben
- u → v él vizsgálatakor Szín(v) = fekete és d(u) > d(v)
Topologikus rendezés definíciója, a körmentesség és a visszaélek kapcsolata
[szerkesztés]- Topológikus rendezés
- Egy G = (V, E) irányított gráf topologikus rendezésén a V pontjainak egy olyan <v1,v2...vn> (n = |V|) felsorolását értjük, amelyre teljesül, hogy minden (u, v) ∈ E élre, u előbb áll a felsorolásban mint v.
- A G = (V, E) irányított gráfnak akkor és csak akkor van topologikus rendezése, ha G körmentes.
- A G = (V, E) irányított gráfban akkor és csak akkor van kör, ha van vissza-éle.
Topologikus rendezést megadó algoritmus
[szerkesztés]- Végrehajt egy mélységi keresés az f elhagyási időkkel
- amikor egy pont vizsgálatát befejezzük, akkor egy lánc elejére beszúrjuk
- A rendezés a lánc szerint Megj.: a pontok csökk. F érték szerint vannak
Ha a G irányított gráf körmentes, akkor pontjainak minden olyan <v1,...vn> felsorolása, amelyre
f (vi ) > f (vi+1 ); i = 1,...n − 1
G egy topologikus rendezése lesz bármely mélységi bejárással kiszámított f elhagyási függvényre.
Ennek függvényében a következő kódban R[] egy olyan tömb lesz melynek mérete megegyezik a V pontjainak számával. Ez a tömb hátulról lesz kitöltve, úgy hogy az a pont kerül bele legelösször (hátra, n helyre) amelyiket elösször hagyjuk el (jelöljük feketével). A legelső elem a tömben (R[0]) tehát az a pont lesz amelyiket legutoljára hagytuk el, azaz a legnagyobb elhagyási számmal rendelkező.
- Java kód
public class TopRend { private: enum Paletta {Feher, Szurke, Fekete}; //Osztályra scope-ban érvényes változók static Paletta[] Szin; int[] R; int n; boolean MelyBejar(Graf G, int p) { Szin[p]=Paletta.Szurke; //p pontot szürkével jelöli for (int q:G.Ki(p)) //p->q él vizsgálatának kezdete { if (Szin[q]==Paletta.Szurke) //kört találtunk, nem lehet rendezést csinálni hiba! return false; if (Szin[q]==Paletta.Feher) { if (!MelyBejar(G,q)) //Rekurzív hivás p pont q fiára return false; //hiba hogyha találunk kört a leszármazottakban } } R[n--] = p; //beirjuk a pontott az R lánc elejére. n-et a Rendez() a Szin[p] = Paletta.Fekete; //G pontjainak számával teszi egyenlővé. return true; //feketével jelöljük a sikeresen elhagyott pontot } public int[] Rendez(Graf G) //publikusan elérhető Rendezést végrehajtó metódus { n = G.Pontokszama(); Szin = new Paletta[n+1]; //szineket tároló tömb, mint a szinezős bejárásnál R = new int[n+1]; //pontok rendezett sorrendjét tárolja for (int p:G) //minden pontot a Szin táblán fehérrel jelöl, kifehérit Szin[p]=Paletta.Feher; for (int p:G) { if (Szin[p] == Paletta.Feher) if (!MelyBejar(G,p)) //meghívja MelyBejart()-t és ellenörzi hogy nem-e talált kört. { R=null; //ha sikertelen volt akkor talált kör, üres R-el kilép break; } } return R; } }
Erősen összefüggő komponensek, és a transzponált gráf definíciója √
[szerkesztés]- u ~ v ha u ~> v és v ~> u
- u akkor és csak akkor van egy komponensben v-vel, ha u-ból vezet út v-be és v-ből is vezet út u-ba
- Egy u pontot tartalmazó erősen összefüggő komponens
- C(u) = {v ∈ V : u ~ v}
- A G = (V, E) gráf transzponáltja
- GT = (V, ET), ahol ET = {(u, v) : (v, u) ∈ E}
Erősen összefüggő komponenseket előállító algoritmus √
[szerkesztés]- Elvi algoritmus
- Számítsuk ki a Mélykeresés algoritmussal az f(u) elhagyási értékeket.
- A GT transzponált gráfra alkalmazzuk a Mélykeresés eljárást úgy, hogy a pontokra a Mélybejár eljárást f szerint csökkenő sorrendben hívjuk.
- A 2. pontban az egy mélységi feszítőfába kerülő pontok alkotnak egy erősen összefüggő komponenst.
- bejárt: tömb, mely meghatározza, hogy egy pontban voltunk-e már
- csökkenőF: verem, melyből csökkenő f szerint jönnek ki a pontok
Halmaz<Halmaz<int>> EÖK(Gráf G) { mélyKeres(G); return mélyKeresT(transzponál(G)); } Gráf transzponál(Gráf G) { Gráf GT; for(él : G.élek) GT.bővít(él.be, él.ki); return GT; } bool bejárt[n]; Verem<int> csökkenőF; void mélyBejár(Gráf G, int u) { bejárt[u] = true; for(v : G[u].ki) if(!bejárt[v]) mélyBejár(v); csökkenőF.push(u); } void mélyKeres(Gráf G) { ∀i bejárt[i] = false; for(v : G) if(!bejárt[v]) mélyBejár(v); } Halmaz<int> mélyBejárT(int p, Halmaz<int> komponens) { bejárt[p] = true; for(int i = 0; i < grafT[p].size(); ++i) if(!bejárt[grafT[p][i]]) mélyBejárT(grafT[p][i], komponens); komponens.insert(p); return komponens; } Halmaz<Halmaz<int>> mélyKeresT(Gráf G) { bejárt = false; Halmaz<Halmaz<int>> komponensek; while(!csökkenő.empty()) { int p = csökkenőF.pop(); Halmaz<int> komponens; if(!bejárt[p]) { komponens = mélyBejárT(p, komponens) komponensek.insert(komponens); } } return komponensek; }
A súlyozott gráf (SGraf) adattípus specifikációja √
[szerkesztés]- Értékhalmaz
- Gráf = {G = (V, E, C) : V ⊆ PontTípus, E ⊆ V × V, C : E → CímkeTípus}
- Műveletek
- Gráfműveletek +
G : Gráf; p, p1, p2 : PontTípus; c : CímkeTípus; I : ÉlIterator
Előtte | Művelet | Utána |
---|---|---|
{G = (V, E), p1, p2 ∈ V} | ÉlBővít(G, p1, p2, c) | E = Pre(E) ∪ {(p1, p2)} ∧ C(p1, p2) = c;} |
{G = (V, E), (p1, p2) ∈ E} | ÉlCímke(G, p1, p2, c) | {c = Pre(C)(p1, p2) ∧ E = Pre(E)} |
ÉlCímkéz(G, p1, p2, c) | {C(p1, p2) = c ∧ E = Pre(E)} | |
{G = G} | KiCímkézettÉl(G, p) | { = {(q, s) : VanÉl(p, q) ∧ C(p, q) = s} } |
ÉlIterátor(G, I) | { = {(p1, p2) : (p1, p2) ∈ E} } |
Minimális feszítőfa problémája, a vágások és a biztonságos élek kapcsolatát leíró tétel
[szerkesztés]A vágások és biztonságos élek kapcsolata: Legyen G = (V,E) egy összefüggő, írányítatlan, a w : E -> R függvénnyel élsúlyozott gráf. Legyen A egy olyan részhalmaza E-nek, amelyik G valamelyik minimális feszítőfának is része. Legyen (S,V-S) tetszőleges A-t elkerülő vágása a G-nek. Legyen (u,v) az (S,V-S) vágást keresztező könnyű él. Ekkor az (u,v)él biztonságos az A-ra nézve.
Kruskal algoritmus √
[szerkesztés]- fa, unioholvan, prisorba(minden él)
- kivesz egy él, ha különböző fában vannak akkor két fát összekötni
Gráf Kruskal(SúlyozottGráf G){ Gráf feszítőFa; UnioHolvan H(G.size()); PriSor<SúlyozottGráfÉl> S(G.size()); for(él : G.élek) S.push(él); while (!S.empty()) { SúlyozottGráfÉl él = S.pop(); int fa1 = H.Holvan(él.ki); int fa2 = H.Holvan(él.be); if (fa1 != fa2) { H.Unio(fa1, fa2); feszítőFa.ÉlBővit(él.ki, él.be); } } if (H.size() != 1) //G nem összefüggő! feszítőFa = NULL; return feszítőFa; }
Prim algoritmus √
[szerkesztés]Prim(SúlyozottGráf<double> G, int start) { int n = G.size(); int apa[1..n] = -1; double d[1..n] = ∞; bool fa[1..n] = false; ModPriSor<double> S(n); fa[start] = true; d[start] = apa[start] = 0; for (v : G) S.push( (d[v], v) ); while (!S.empty()) { u = S.pop(); // kiveszi a minimális elemet, és beveszi a fába fa[u.adat] = true; for (v : G[u.adat].ki) { // még nincs a fában és jobb, mint ami van, akkor update if (!fa[v.pont] && súly(u, v) < d[v.pont]) { d[v.pont] = súly(u, v); apa[v.pont] = u.adat; S.modify(v.pont, d[v.pont]); } } } }
Dijsktra algoritmus √
[szerkesztés]Dijkstra(SúlyozottGráf<double> G, int start/*, int end*/) { int n = G.size(); int apa[1..n] = -1; double d[1..n] = ∞; bool kész[1..n] = false; ModPriSor<double> S(n); fa[start] = true; d[start] = apa[start] = 0; for (v : G) S.push( (d[v], v) ); while (!S.empty()) { u = S.pop(); kész[u.adat] = true; // if(u.adat == end) return; // elértük a keresett pontot for (v : G[u.adat].ki) { if (!kész[v.pont]) { double d_uv = d[u.adat] + v.súly; if(d_uv < d[v.pont]) { d[v.pont] = d_uv; apa[v.pont] = u.adat; v.kulcs = d_uv; S.modify(v); } } } } }
A legrövidebb utak felső korlát és konvergencia tulajdonságai √
[szerkesztés]- Felső korlát tulajdonság
- D[v] > δ(s, v) és ha egyszer D[v] = δ(s, v), akkor ezután mindig teljesül a D[v] = δ(s, v) egyenlőség.
- Konvergencia tulajdonság
- Ha s ~> u → v egy legrövidebb út és D[u] = δ(s, u) Közelít(u, v) végrehajtása előtt, akkor Közelít(u, v) után D[v] = δ(s, v).
Floyd-Warshall algoritmus √
[szerkesztés]void FW(SúlyozottGráf G) { int n = G.Pontokszáma(); double D[1..n, 1..n] = ∞; int előző[1..n, 1..n] = 0; for (int u : G){ D[u, u] = 0.0; for (v : G[u].ki) { D[u, v] = G[v].súly; előző[u, v] = v; } } for (k = 1..n) for (i = 1..n) for (j = 1..n) { double Dikj=D[i, k]+D[k, j]; if (Dikj < D[i, j]) { D[i, j]=Dikj; előző[i, j] = előző[i, k]; } } }
void ÚtKiír(int[][] előző, int u, int v) { if (előző[u, v] == 0) { kiír("Nincs " + u + "->"+ v + " út!"); return; } do { kiír(u + "->"); u = előző[u, v]; } while (u != v); kiír(u); }
Kiválasztó rendezés algoritmusa √
[szerkesztés]template<typename T> void KiválasztóRendezés(T* tömb, int n /*hossz*/) { for(int i = 0; i < n; ++i) { // minimum kiválasztás int minIndex = i; for(int j = i + 1; j < n; ++j) if(tömb[j] < tömb[minIndex]) minIndex = j; // csere a minimum és az aktuális eleje swap(tömb[minIndex], tömb[i]); // így a sor aktuális elején mindig a minimális elem lesz } }
Beszúró rendezés algoritmusa √
[szerkesztés]template<typename T> BeszúróRendezés(T* tömb, int n /*hossz*/) { for(int i = 1; i < n; ++i) { T temp = tömb[i]; j = i - 1; while (0 <= j && temp < tömb[j]) tömb[j + 1] = tömb[j--]; tömb[j + 1] = temp; } }
Kupac adatszerkezet definíciója, süllyeszt algoritmus √
[szerkesztés]- Kupac
- Olyan (bináris) fa, amely teljesíti a kupactulajdonságot.
- Kupactulajdonság
- Ha B A gyereke, akkor a (maximális) kupactulajdonság: kulcs(A) ≥ kulcs(B)
template<typename T> void Sullyeszt(T* kupac, int pont, int vege){ int apa = pont; int fiu; T temp = kupac[pont]; while ((fiu = 2*apa + 1) < vege ) { //a nulla indexelés miatt a 2*apa + 1 adja a bal gyereket //pelda: 8, 2, 5, 7, 6. a 0 indexelés szerinti 1. elem azaz a "2" bal gyermeke a "2*1 + 1 = 3" indexű elem, azaz a "7". // ha jobb gyerek > bal gyerek, akkor átlép jobb gyerekre if (kupac[fiu + 1] > kupac[fiu]) fiu++; // ha teljesül a kupac tulajdonság, akkor megáll if (temp >= kupac[fiu]) break; // a gyereket feljebb hozza kupac[apa] = kupac[fiu]; apa = fiu; } // a javítandó elemet beteszi az utolsó emelt gyerek helyére kupac[apa] = temp; }
Kupacrendezés algoritmusa, a süllyeszt algoritmussal együtt √
[szerkesztés]template<typename T> void KupacRend(T* tomb, int n /*hossz*/) { n = n - 1; // nulla indexelés miatt // épít egy kupacot for (int i = n / 2; i >= 0; --i) Sullyeszt(tomb, i, n); // a kupac legnagyobb elemét kicseréli az utolsó elemmel // majd kijavítja a kupacot, ami mostmár nem a teljes, hossz, hanem csak az "utolsó" előtti elemtől számít for (int i = n; i >= 0; --i) { swap(tomb[0], tomb[i]); Sullyeszt(tomb, 0, i - 1); } }
Gyorsrendezés algoritmusa, a feloszt algoritmussal együtt, egy tömbben megvalósítva √
[szerkesztés]template<typename T> int Feloszt(T* tömb, int bal, int jobb) { T osztó = tömb[bal]; int b = bal; // H = tömb[bal..jobb] for (int j = bal + 1; j <= jobb; j++) { // invariáns: H_bal = tömb[bal..j] < osztó ≤ H_jobb = tömb[j + 1..jobb] if (tömb[j] < osztó) { tömb[b] = tömb[j]; tömb[j] = tömb[++b]; } } tömb[b] = osztó; return b; }
template<typename T> void GyorsRendezés(T* tömb, int bal, int jobb) { int felosztás = Feloszt(tömb, bal, jobb); if (bal < felosztás) GyorsRendezés(tömb, bal, felosztás - 1); if (felosztás + 1 < jobb) GyorsRendezés(tömb, felosztás + 1, jobb); } template<typename T> void GyorsRendezés(T* tömb, int hossz) { GyorsRendezés(tömb, 0, hossz - 1); }
Számláló rendezés (input specifikációval) √
[szerkesztés]- Tegyük fel, hogy a rendezendő A = {a1, ..., an} halmaz elemei (kulcs, adat) pár és a halmazt a kulcs szerint kell rendezni. Legyen min a legkisebb, max pedig a legnagyobb kulcsérték, m = max - min. Ekkor a rendezés elvégezhető O(m + n) időben.
- Teljes megvalósítás
pair<KulcsTípus, AdatTípus>[] szamlalo(pair<KulcsTípus, AdatTípus> A[n]) { KulcsTípus min, max; for(int i = 0; i < n; ++i) { if(A[i].kulcs > max) max = A[i].kulcs; if(A[i].kulcs < min) min = A[i].kulcs; } int m = max - min + 1; KulcsTípus C[m] = 0; for(int i = 0; i < n; ++i) C[ A[i].kulcs - min ]++; for(int i = 1; i < m; ++i) C[i] += C[i - 1]; pair<KulcsTípus, AdatTípus> B[n]; for(int i = 0; i < n; ++i) B[ --C[ A[i].kulcs - min ] ] = A[i]; return B; }
- Rövidített megvalósítás
- Tegyük fel hogy a rendezés kap egy tömböt, melyben a számok 0 ≤ A[i] ≤ max, ∀ 0 ≤ i < n-re, ahol n a tömb hossza.
int[] szamlalo(int A[n], int max) { int C[max] = {0}; // megszámolja hogy adott elemből mennyi van for(int i = 0; i < n; ++i) C[ A[i] ]++; // összeszámolja, hogy adott elemnél kisebb-egyenlő mennyi van for(int i = 1; i < max; ++i) C[i] += C[i - 1]; int B[n]; // feltölti az új - leendő rendezett - tömböt C-nek megfelelően for(int i = 0; i < n; ++i) B[ --C[ A[i] ] ] = A[i]; return B; }
Radix rendezés (input specifikációval)
[szerkesztés]Példa
[szerkesztés]Rendezetlen | Utolsó jegy szerint |
Középső jegy szerint |
Első jegy szerint | |||
---|---|---|---|---|---|---|
329 | → | 720 | → | 720 | → | 329 |
457 | 355 | 329 | 355 | |||
657 | 436 | 436 | 436 | |||
839 | 457 | 839 | 457 | |||
436 | 657 | 355 | 657 | |||
720 | 329 | 457 | 720 | |||
355 | 839 | 657 | 839 |
Vödrös rendezés (input specifikációval)
[szerkesztés]- Tegyük fel, hogy a rendezendő H = {a1, ..., an} halmaz elemeinek kulcsai a [0,1) intervallumba eső valós számok (float vagy double).
Pszeudo kód wiki-ről: Vödrös rendezés, de szerintem ez kevés:
lista VödrösRendezés(tömb[n], vödrökSzáma) { lista vödrök[vödrökSzáma]; for(i = 0..n-1) vödrök[(int)(tömb[i] * vödrökSzáma)].beszúr(tömb[i]); for(i = 0..n-1) next-sort(vödrök[i]); return vödrök[0] + ... + vödrök[n-1]; }
Kibővített euklideszi algoritmus √
[szerkesztés]Visszatér a és b legnagyobb közös osztójával és p, q kimeneti paraméterekben megadja p * a0 + q * b0 = lnko(a, b) paramétereit
int euclid(int a, int b, int& p, int& q) { // We maintain the invariant: // p * a0 + q * b0 = a // r * a0 + s * b0 = b. if(a < b) swap(a, b); int s = p = 1, r = q = 0; while (b != 0) { int rem = a % b, quot = a / b; a = b; b = rem; int new_r = p - quot * r; int new_s = q - quot * s; p = r; q = s; r = new_r; s = new_s; } return a; }
Bináris keresőfa definíciója , Keres algoritmus √
[szerkesztés]Az F fát bináris fának nevezzük, ha (∀p ∈ F)(Fok(p) ≤ 2).
- Ábrázolás
struct Fa { ElemTípus adat; Fa* bal; Fa* jobb; // Fa* apa; };
- A F = (M, R, Adat) absztrakt adatszerkezetet bináris keresőfának nevezzük, ha
- F bináris fa,
- Adat : M → ElemTípus és ElemTípus-on értelmezett egy ≤ lineáris rendezési reláció,
- (∀x ∈ M)(∀p ∈ Fbal(x))(∀q ∈ Fjobb(x))(Adat(p) ≤ Adat(x) ≤ Adat(q))
Fa* Keres(Fa* fa, ElemTípus adat){ while (fa != NULL) && (adat != fa->adat) if (adat < fa->adat) fa = fa->bal; else fa = fa->jobb; return fa; }
Rákövetkező elem megtalálása bináris keresőfában √
[szerkesztés]Fa* Következő(Fa* fa) { // ha van jobb részfája if(fa->jobb != NULL) { fa = fa->jobb; // megkeresi annak minimális elemét while (fa->bal != NULL) fa = fa->bal; return fa; } else { Fa* fiu = fa; Fa* apa = fiu->apa; // felmegy a fában amíg a fiú nem lesz bal fiú while (apa != NULL && fiu != apa->bal) { fiu = apa; apa = fiu->apa; } return apa; } }
Beszúrás bináris keresőfába √
[szerkesztés]struct Fa { int adat; Fa* bal, jobb; Fa(int n): adat(n) {} }; void beszur(Fa* gyoker, int n) { Fa* jelen = NULL; Fa* kov = gyoker; // megkeresi a beszúrás helyét, jelen-ben a beszúrandó elem apja lesz while(kov) { jelen = kov; if(n < kov->adat) kov = kov->bal; else kov = kov->jobb; } // létrehozza az új pontot kov = new Fa(n); if(jelen == NULL) // üres fa gyoker = kov; else // normál fa, beszúrja a megfelelő helyre if(n < jelen->adat) jelen->bal = kov; else jelen->jobb = kov; }
Törlés bináris keresőfában √
[szerkesztés]- levél
- egyszerű törlés
- egy gyerek
- csere a másik gyerekre, majd törlés
- két gyerek
- kicseréljük az értékét
- vagy inorder következővel (jobb részfa min)
- vagy inorder előzővel (bal részfa max)
- majd törlés
- kicseréljük az értékét
struct Pont { Pont* bal; Pont* jobb; int érték; }; void Töröl(Pont* pont) { Pont* temp = pont; // egy gyerek: jobb, (és levél, ha pont = pont->jobb NULL) if (pont->bal == NULL) { *pont = *pont->jobb; // copy constructor delete temp; // egy gyerek: bal } else if (pont->jobb == NULL) { *pont = *pont->bal; // copy constructor delete temp; // két gyerek } else { temp = pont->jobb; while (temp->bal != NULL) temp = temp->bal; // csere helyett, elég lementeni a következő elemet, mivel a jelenlegit úgyis töröljük pont->érték = temp->érték; Töröl(temp); // lehet hogy van neki 1 gyereke } }
//===Hibák, észrevételek=== //#n3.pdf: 3.3 PriSor.SorBol() művelet végeredménye nem Pre(S) ∪ {x}, hanem Pre(S) \ {x} //#...
kikommenteztem, mert nincs benne hiba.
A Sullyeszt algoritmusban az alábbi utasításban azt is ellenőrizni kellene, hogy van-e jobb gyermeke is az apa-nak (fiu + 1 < vege). if (kupac[fiu + 1] > kupac[fiu]) fiu++;