„Algoritmuselmélet - ZH, 2013.04.03.” változatai közötti eltérés
| 104. sor: | 104. sor: | ||
}} | }} | ||
===7. Feladat=== | ===7. Feladat (Van megoldás)=== | ||
Az <math>A[1 \dots 2013]</math> tömbben egy kupac adatstruktúrát tárolunk, minden tárolt elem különböző. Tudjuk, hogy ebben a kupacban a legnagyobb elem <math> A[i]</math>. Határozza meg <math> i </math> összes lehetséges értékét! | |||
{{Rejtett | {{Rejtett | ||
|mutatott=<big>'''Megoldás'''</big> | |mutatott=<big>'''Megoldás'''</big> | ||
|szöveg= | |szöveg= | ||
*Kupac egyik jó tulajdonsága, hogy teljes bináris fa, így az elem számból kiszámolható, hogy milyen magas a fa. | |||
**Tudjuk, hogy :<math> 2^{m-1} \leq n \leq 2^{m}-1</math>. | |||
**Ebben az esetben <math> 2^{m-1} \leq 2013 \leq 2^{m}-1 \Rightarrow m = 11</math>. | |||
*A legnagyobb elem vagy a legalsó szinten van, vagy ha az nem "telített", akkor az előtte lévő szinten olyan csúcsok is szóba jöhetnek, akiknek nincsen gyereke. | |||
**Mivel tudjuk, hogy a fa magassága 11, ezért: | |||
***A kupacban összesen 2047 elemnek van hely, tehát még 34 elem férne el. Ebből pedig az következik, hogy a 10. szinten 17 olyan csúcs van, aminek nincsen fia, így ők még játszhatnak a legnehezebb elem díjáért. | |||
***A 11. szinten 1024 elem férne el, de tudjuk, hogy hiányzik 34, tehát a 11. szinten csak 990 elem van, amik a legnehezebbek lehetnek a fában. | |||
*Ha a kupacot tömbbe írjuk, akkor azt fentről-lefele, balról-jobbra töltjük fel. | |||
**Az előzőek alapján tudjuk, hogy a 11. szinten 990, a 10. szinten pedig 17 csúcs jöhet szóba, így összesen 1007 helyen lehet a legnehezebb elem. A listás elrendezés alapján ez azt jelenti, hogy az <math> i \geq (2013-1007+1) \rightarrow i \geq 1007</math>. | |||
}} | }} | ||