„Algoritmuselmélet - PZH, 2013.04.24.” változatai közötti eltérés
aNincs szerkesztési összefoglaló |
a elírások javítva |
||
| (4 közbenső módosítás, amit 3 másik szerkesztő végzett, nincs mutatva) | |||
| 21. sor: | 21. sor: | ||
===2. Feladat (Van megoldás)=== | ===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 | 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 lehető legnagyobb az összes ilyen csúcs közül. | ||
{{Rejtett | {{Rejtett | ||
|mutatott=<big>'''Megoldás'''</big> | |mutatott=<big>'''Megoldás'''</big> | ||
| 31. sor: | 31. sor: | ||
*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). | *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 ( | 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>. | *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 a részfája a "legnagyobb" kupac (kezdeti értéke legyen mondjuk az egyik legalsó szinten lévő csúcs). | *Legyen egy változónk, amiben tároljuk, hogy melyik csúcsra igaz, hogy a részfája a "legnagyobb" kupac (kezdeti értéke legyen mondjuk az egyik legalsó szinten lévő csúcs). | ||
| 44. sor: | 44. sor: | ||
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 | 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 | '''(a)''' inorder bejárással kiolvasva 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? | '''(b)''' preorder bejárással kiolvasva a két fát ugyanazt a számsorozatot kapják? | ||
| 67. sor: | 67. sor: | ||
===4. Feladat=== | ===4. Feladat=== | ||
Éllistával adott n csúcsú, élsúlyozott, irányítatlan gráfként ismerjük egy ország úthálózatát (a csomópontok a városok, az élek a közvetlen összeköttetések a városok között). Az élek súlya azt adja meg, hogy hány (egész) perc alatt tudjuk megtenni az adott útszakaszt. Nagy havazás várható, de szerencsére pontosan tudjuk a következő k percre, hogy mely élek (utak) mikortól nem lesznek járhatóak. Ha egyszer járhatatlanná válnak, akkor úgy is maradnak, ezután már az úton nem lehet közlekedni, és ha épp az adott élen vagyunk, amikor az járhatatlanná válik, akkor elakadunk. | |||
Adjon O(k(n+e)) lépést használó algoritmust, ami az adatok ismeretében el tudja dönteni, hogy el lehet-e jutni A városból B városba, ha most azonnal elindulunk! | |||
{{Rejtett | {{Rejtett | ||
|mutatott=<big>'''Megoldás'''</big> | |mutatott=<big>'''Megoldás'''</big> | ||
| 121. sor: | 122. sor: | ||
===7. Feladat=== | ===7. Feladat=== | ||
Adott egy n és egy k elemet tartalmazó kupac. Adjon olyan O(n + k) összehasonlítást használó algoritmust, ami létrehoz egy olyan kupacot, ami a két kupacban tárolt elemek halmazának unióját tartalmazza. (TFH a két kupacban csupa különböző számocska áll.) | |||
{{Rejtett | {{Rejtett | ||
|mutatott=<big>'''Megoldás'''</big> | |mutatott=<big>'''Megoldás'''</big> | ||
| 135. sor: | 136. sor: | ||
|szöveg= | |szöveg= | ||
*Összesen 5 felállás lehet: [[File: | *Összesen 5 felállás lehet: [[File:algel_pzh_2013tavasz_8_1.png|400px]] | ||
**Ebből az 1. és a 4. jó is ''(a 4. persze csak akkor, ha X az nem a főgyökér)''. | **Ebből az 1. és a 4. jó is ''(a 4. persze csak akkor, ha X az nem a főgyökér)''. | ||
**A 3. - kis módosítással - látszik, hogy szintén fenn állhat gond nélkül: [[File: | **A 3. - kis módosítással - látszik, hogy szintén fenn állhat gond nélkül: [[File:Algel pzh 2013tavasz 8 2.png|100px]] | ||
**Egyedül a 2. és az 5. problémás. Ezek viszont rosszak is, hiszen mindkét esetben elmondható, hogy X-nek a fekete magassága jobbra 1, balra viszont legalább 2, mert az Y csúcsnak legalább 1-1 levél fia van. Tehát belső csúcsnál ilyen állapot nem állhat fent. | **Egyedül a 2. és az 5. problémás. Ezek viszont rosszak is, hiszen mindkét esetben elmondható, hogy X-nek a fekete magassága jobbra 1, balra viszont legalább 2, mert az Y csúcsnak legalább 1-1 levél fia van. Tehát belső csúcsnál ilyen állapot nem állhat fent. | ||