„Algoritmuselmélet 2010.11.19. PZH megoldásai” változatai közötti eltérés

A VIK Wikiből
Ugrás a navigációhoz Ugrás a kereséshez
77. sor: 77. sor:
 
}}
 
}}
  
−
===7. Feladat===
+
===7. Feladat (Van megoldás)===
−
TODO
+
Egy piros-fekete fa gyökerének mindkét gyereke fekete. A gyökér baloldali részfájában 14, a jobboldali részfájában 63 elemet tárolunk. Mennyi lehet a fa fekete-magassága?
 
{{Rejtett
 
{{Rejtett
 
|mutatott=<big>'''Megoldás'''</big>
 
|mutatott=<big>'''Megoldás'''</big>
 
|szöveg=
 
|szöveg=
  
−
TODO
+
*Először vizsgáljuk a jobboldali részfát:
 +
**Tudjuk, hogy <math> n \leq 2^m-1 \Rightarrow 63 \leq 2^m-1 \Rightarrow m \geq 6 </math>, vagyis a jobb oldali részfa magassága legalább 6.<br><br>
 +
**Továbbá <math> fm \geq \frac{m}{2} \Rightarrow fm \geq 3 </math> <br><br>
 +
*Most nézzük a baloldali részfát:
 +
**Ismert, hogy <math> b_v \geq 2^{fm(v)}-1 \Rightarrow 14 \geq 2^{fm(v)}-1 \Rightarrow fm \leq 3.907 \Rightarrow \Rightarrow fm < 4 </math>
 +
 
 +
 
 +
*A 2 korlátot összevetve jön ki, hogy a bal és jobb részfa esetén <math> fm = 3.</math>
 +
*Emiatt az eredeti fában pedig <math> fm = 4.</math>
 
}}
 
}}
  

A lap 2013. június 19., 20:29-kori változata

← Vissza az előző oldalra – Algoritmuselmélet

2010.11.19 - PZH megoldásai

1. Feladat

TODO

Megoldás
TODO

2. Feladat

TODO

Megoldás
TODO

3. Feladat

TODO

Megoldás
TODO

4. Feladat (Van megoldás)

Dijkstra algoritmussal határozza meg a G gráfban az [math]A[/math] pontból az összes többi pontba menő legrövidebb utak hosszát az [math]X[/math] pozitív valós paraméter függvényében. Minden lépésnél írja fel a távolságokat tartalmazó D tömb állapotát, és a KÉSZ halmaz elemeit.

Algel pzh 2010osz 4 f.PNG

Megoldás
  • Egy egyszerű Dijkstra-s feladat.
  • Annyit kell megjegyezni hozzá, hogy:
    • Ha [math] X \leq 2 [/math], akkor az [math]X[/math] élt [math]( D \rightarrow E )[/math] veszi be.
    • Ha [math] X \geq 2 [/math], akkor a [math]C \rightarrow E [/math] élt veszi be.
Algel pzh 2010osz 4 2.PNGAlgel pzh 2010osz 4 3.PNGAlgel pzh 2010osz 4 1.png

5. Feladat

TODO

Megoldás
TODO

6. Feladat (Van megoldás)

Hajtsa végre az alábbi [math]F[/math] bináris keresőfán a BESZÚR(13), TÖRÖL(10) műveleteket! Minden lépést jelezzen!

Algel pzh 2010osz 6 f.PNG

Megoldás
  • BESZÚR(13):
    • Egyszerű, mint az 1x1

Algel pzh 2010osz 6 1.png

  • TÖRÖL(10):
    • Töröljük a 10-t.
    • A BAL oldali részfából kiválasztjuk a LEGNAGYOBB elemet, és berakjuk a gyökérbe (ebben az esetben a 7).
    • A fát rendbe rakjuk (ez esetben a 6-t beírjuk a 7 régi helyére).
Algel pzh 2010osz 6 2.png

7. Feladat (Van megoldás)

Egy piros-fekete fa gyökerének mindkét gyereke fekete. A gyökér baloldali részfájában 14, a jobboldali részfájában 63 elemet tárolunk. Mennyi lehet a fa fekete-magassága?

Megoldás
  • Először vizsgáljuk a jobboldali részfát:
    • Tudjuk, hogy [math] n \leq 2^m-1 \Rightarrow 63 \leq 2^m-1 \Rightarrow m \geq 6 [/math], vagyis a jobb oldali részfa magassága legalább 6.

    • Továbbá [math] fm \geq \frac{m}{2} \Rightarrow fm \geq 3 [/math]

  • Most nézzük a baloldali részfát:
    • Ismert, hogy [math] b_v \geq 2^{fm(v)}-1 \Rightarrow 14 \geq 2^{fm(v)}-1 \Rightarrow fm \leq 3.907 \Rightarrow \Rightarrow fm \lt 4 [/math]


  • A 2 korlátot összevetve jön ki, hogy a bal és jobb részfa esetén [math] fm = 3.[/math]
  • Emiatt az eredeti fában pedig [math] fm = 4.[/math]

8. Feladat

TODO

Megoldás
TODO
A lap eredeti címe: „https://wiki.sch.bme.hu/index.php?title=Algoritmuselmélet_2010.11.19._PZH_megoldásai&oldid=168630”