„Algoritmuselmélet - PPZH, 2013.05.23.” változatai közötti eltérés
Ugrás a navigációhoz
Ugrás a kereséshez
| 63. sor: | 63. sor: | ||
===5. Feladat=== | ===5. Feladat=== | ||
| − | + | Egy kupac elemeit preorder bejárás szerint kiolvasva az alábbi számsorozatot kapjuk: <math> 1, 17, 19, 21, 22, 31, 37, 2, 8, 3.</math> Rekonstruálható-e ebből a kupac? | |
{{Rejtett | {{Rejtett | ||
|mutatott=<big>'''Megoldás'''</big> | |mutatott=<big>'''Megoldás'''</big> | ||
|szöveg= | |szöveg= | ||
| − | + | *A kupac egy teljes bináris fa, így tudjuk, hogy mi a fa alakja. | |
| + | *Nincs is más dolgunk, mint felrajzolni, majd a preorder bejárás alapján beírni az elemeket a megfelelő csúcsokba, és ellenőrizni, hogy sérül-e valahol a kupac adatszerkezet egy tulajdonsága. | ||
| + | :::::::::::::::::[[File:algel_ppzh_2013tavasz_5_1.png|400px]] | ||
| + | *Látszik, hogy minden rendben van, így a kupac rekonstruálható. | ||
}} | }} | ||
A lap 2013. június 18., 16:59-kori változata
Tartalomjegyzék
2013.05.23 - PPZH megoldásai
1. Feladat (Van megoldás)
Tudjuk, hogy az [math] f(n), g(n) : \textsc{N} \rightarrow \textsc{N} [/math] függvényekre igaz, hogy [math] f(n)= \Omega (logn) [/math] és [math] g(n) = \Theta (n^4) .[/math] Lehetséges-e, hogy:
(a) [math] f(n) = \Theta (g(n)) ?[/math]
(b) [math] g(n) = O(f(n)) ?[/math]
(Ez két, egymástól függetlenül megválaszolandó kérdés.)
Megoldás
a)
- Ha [math] f(n) = n^4 , g(n) = n^4 [/math]
- Akkor igaz az, hogy:
- [math] f(n)= \Omega (logn) \Rightarrow n^4 = \Omega (logn)[/math]
- És az is, hogy [math] f(n) = \Theta (g(n)) \Rightarrow n^4 = \Theta (n^4)[/math]
- Tehát lehetséges.
b)
- Ha [math] g(n) = n^4 , f(n) = n^4 [/math]
- Akkor igaz az, hogy:
- [math] g(n)= \Theta (n^4) \Rightarrow n^4 = \Theta (n^4)[/math]
- És az is, hogy [math] g(n) = O(f(n)) \Rightarrow n^4 = O(n^4)[/math]
- Tehát lehetséges.
2. Feladat
TODO
Megoldás
TODO
3. Feladat
TODO
Megoldás
TODO
4. Feladat
TODO
Megoldás
TODO
5. Feladat
Egy kupac elemeit preorder bejárás szerint kiolvasva az alábbi számsorozatot kapjuk: [math] 1, 17, 19, 21, 22, 31, 37, 2, 8, 3.[/math] Rekonstruálható-e ebből a kupac?
Megoldás
- A kupac egy teljes bináris fa, így tudjuk, hogy mi a fa alakja.
- Nincs is más dolgunk, mint felrajzolni, majd a preorder bejárás alapján beírni az elemeket a megfelelő csúcsokba, és ellenőrizni, hogy sérül-e valahol a kupac adatszerkezet egy tulajdonsága.
- Látszik, hogy minden rendben van, így a kupac rekonstruálható.
6. Feladat
TODO
Megoldás
TODO
7. Feladat
TODO
Megoldás
TODO
8. Feladat
TODO
Megoldás
TODO
