„Algoritmuselmélet - PZH, 2013.04.24.” változatai közötti eltérés
a (→3. Feladat) |
|||
13. sor: | 13. sor: | ||
}} | }} | ||
− | ===2. Feladat=== | + | ===2. Feladat (Van megoldás)=== |
− | + | Adott egy teljes bináris fa, a csúcsaiba egész számok vannak írva, összesen ''n'' darab (a fa nem feltétlenül bináris keresőfa). Adjon algoritmust, ami <math>O(n)</math> lépésben megkeres egy olyan csúcsot a fában, aminek a részfája kupac, és aminek a magassága a legető legnagyobb az összes ilyen csúcs közül. | |
{{Rejtett | {{Rejtett | ||
|mutatott=<big>'''Megoldás'''</big> | |mutatott=<big>'''Megoldás'''</big> | ||
|szöveg= | |szöveg= | ||
− | + | {{Rejtett | |
− | + | |mutatott=<big>'''Megjegyzések a feladathoz'''</big> | |
+ | |szöveg= | ||
+ | *Bár nem tartozik a feladathoz, talán érdemes megjegyezzem, hogy bináris kereső fa nem is lehetne, hiszen akkor ott kapásból csak a legalsó szinten lévő elemek lehetnek kupacok (egy 1 elemet tartalmazó kupac), hiszen bináris keresőfánál balra kisebbek, jobbra nagyobbak vannak, míg kupacnál balra és jobbra is nagyobbak vannak. | ||
+ | *Továbbá a teljes bináris fára azért van szükség, mert így "jóval egyszerűbb" a feladat, és nem kell szívózni annak vizsgálatával, hogy az adott részfa teljes bináris fa-e (ugyebár ez a kupac egyik fontos tulajdonsága). | ||
+ | }} | ||
+ | Minden csúcsban 3 adatot fogunk számon tartani: Érték (ez persze adott már), részfa magassága (jelüljük M-mel), és egy bool érték (IGAZ/HAMIS, jelöljük B-vel), hogy igaz-e a részfájára, hogy az kupac. | ||
+ | *Első lépésben a legalsó szinteken lévő csúcsok esetén <math>M:=1, B:=IGAZ</math>. | ||
+ | *Legyen egy változónk, amiben tároljuk, hogy melyik csúcsra igaz, hogy az részfája a "legnagyobb" kupac (kezdeti értéke legyen mondjuk az egyik legalsó szinten lévő csúcs). | ||
+ | *Minden további szinten az a feladatunk, hogy megnézzük az adott csúcs (x) bal, és jobb fiát <math>(JOBB(x), BAL(x))</math>. | ||
+ | **Megnézzük, hogy nagyobbak-e, mint x, majd megnézzük, hogy kupac tulajdonsággal bírnak-e: | ||
+ | ***Ha <math>BAL(x),JOBB(x) > x;BAL(x).B=JOBB(x).B=IGAZ\Rightarrow\Rightarrow x.M := BAL(x).M+1, x.B := IGAZ</math> majd a változónkba belerakjuk a csúcsot. ''Vagyis ha mindkettő nagyobb, és mindkettő kupac tulajdonsággal bír, akkor a csúcs részfa magassága 1-gyel nagyobb lesz, mint az egyik (bal, vagy jobb) fiai magassága, és kupac tulajdonságú lesz.'' | ||
+ | ***Ha <math>BAL(x) < x</math> VAGY <math>JOBB(x) < x</math> VAGY <math>BAL(x).B=HAMIS</math> VAGY <math>JOBB(x).B=HAMIS\Rightarrow\Rightarrow x.M := BAL(x).M+1, x.B := HAMIS</math>. ''Vagyis ha bármelyik feltétel nem teljesül (valamelyik fia kisebb, avagy valamelyik gyerekére nem igaz, hogy kupac tulajdonságú), akkor maga a csúcs sem lehet már kupac tulajdonságú (itt a magasságot nem is kéne beállítani, de...hát miért is ne).'' | ||
+ | Mivel minden csúcsot csak egyszer látogatunk meg, így <math>O(n)</math> lépésben megyünk végig a gráfon. | ||
}} | }} | ||
A lap 2013. június 11., 07:38-kori változata
Tartalomjegyzék
2013.04.24. PZH megoldásai
1. Feladat (Van megoldás)
Egy algoritmus lépésszámáról tudjuk, hogy [math] T(n) = T\left(\left \lfloor \frac{n}{4} \right \rfloor\right) + O(n^2)[/math] és tudjuk azt is, hogy [math] T(1)=T(2)=T(3)=1[/math]. Bizonyítsa be, hogy [math] T(n)=O(n^2)[/math].
[math] T(n) = T\left(\left \lfloor \frac{n}{4} \right \rfloor\right) + O(n^2) = T\left(\left \lfloor \frac{n}{16} \right \rfloor\right) + O\left(\frac{n^2}{4} \right) + O(n^2)=...=1 + O(n^2)*\left(\sum_{i=0}^{\left \lfloor log_4n \right \rfloor} \left (\frac{1}{4} \right )^i\right)[/math]
Azt kell észrevennünk, hogy ez tulajdonképpen egy mértani sor, amire van képletünk:
[math]\sum_{i=0}^{k} r^i = \frac{1-r^{k+1}} {1-r} [/math] ahol [math] k = \left \lfloor log_4n \right \rfloor, r = 0.25[/math], vagyis [math]\frac{1-0.25^{\left \lfloor log_4n \right \rfloor+1}} {1-0.25}[/math]
[math] \lim_{n \to \infty}\frac{1-0.25^{\left \lfloor log_4n \right \rfloor+1}} {1-0.25} = \frac{1}{0.75}[/math]
2. Feladat (Van megoldás)
Adott egy teljes bináris fa, a csúcsaiba egész számok vannak írva, összesen n darab (a fa nem feltétlenül bináris keresőfa). Adjon algoritmust, ami [math]O(n)[/math] lépésben megkeres egy olyan csúcsot a fában, aminek a részfája kupac, és aminek a magassága a legető legnagyobb az összes ilyen csúcs közül.
- Bár nem tartozik a feladathoz, talán érdemes megjegyezzem, hogy bináris kereső fa nem is lehetne, hiszen akkor ott kapásból csak a legalsó szinten lévő elemek lehetnek kupacok (egy 1 elemet tartalmazó kupac), hiszen bináris keresőfánál balra kisebbek, jobbra nagyobbak vannak, míg kupacnál balra és jobbra is nagyobbak vannak.
- Továbbá a teljes bináris fára azért van szükség, mert így "jóval egyszerűbb" a feladat, és nem kell szívózni annak vizsgálatával, hogy az adott részfa teljes bináris fa-e (ugyebár ez a kupac egyik fontos tulajdonsága).
Minden csúcsban 3 adatot fogunk számon tartani: Érték (ez persze adott már), részfa magassága (jelüljük M-mel), és egy bool érték (IGAZ/HAMIS, jelöljük B-vel), hogy igaz-e a részfájára, hogy az kupac.
- Első lépésben a legalsó szinteken lévő csúcsok esetén [math]M:=1, B:=IGAZ[/math].
- Legyen egy változónk, amiben tároljuk, hogy melyik csúcsra igaz, hogy az részfája a "legnagyobb" kupac (kezdeti értéke legyen mondjuk az egyik legalsó szinten lévő csúcs).
- Minden további szinten az a feladatunk, hogy megnézzük az adott csúcs (x) bal, és jobb fiát [math](JOBB(x), BAL(x))[/math].
- Megnézzük, hogy nagyobbak-e, mint x, majd megnézzük, hogy kupac tulajdonsággal bírnak-e:
- Ha [math]BAL(x),JOBB(x) \gt x;BAL(x).B=JOBB(x).B=IGAZ\Rightarrow\Rightarrow x.M := BAL(x).M+1, x.B := IGAZ[/math] majd a változónkba belerakjuk a csúcsot. Vagyis ha mindkettő nagyobb, és mindkettő kupac tulajdonsággal bír, akkor a csúcs részfa magassága 1-gyel nagyobb lesz, mint az egyik (bal, vagy jobb) fiai magassága, és kupac tulajdonságú lesz.
- Ha [math]BAL(x) \lt x[/math] VAGY [math]JOBB(x) \lt x[/math] VAGY [math]BAL(x).B=HAMIS[/math] VAGY [math]JOBB(x).B=HAMIS\Rightarrow\Rightarrow x.M := BAL(x).M+1, x.B := HAMIS[/math]. Vagyis ha bármelyik feltétel nem teljesül (valamelyik fia kisebb, avagy valamelyik gyerekére nem igaz, hogy kupac tulajdonságú), akkor maga a csúcs sem lehet már kupac tulajdonságú (itt a magasságot nem is kéne beállítani, de...hát miért is ne).
- Megnézzük, hogy nagyobbak-e, mint x, majd megnézzük, hogy kupac tulajdonsággal bírnak-e:
3. Feladat (Van megoldás)
Kukori és Kotkoda egy-egy bináris fára gondolnak (nem feltétlenül bináris keresőfákra). Következik-e, hogy a két fa azonos, ha
(a) inorder bejárással kilolvasva a két fát ugyanazt a számsorozatot kapják?
(b) preorder bejárással kiolvasva a két fát ugyanazt a számsorozatot kapják?
4. Feladat
TODO
5. Feladat
TODO
6. Feladat
TODO
7. Feladat
TODO
8. Feladat
TODO