„Algoritmuselmélet - ZH, 2013.04.03.” változatai közötti eltérés

A VIK Wikiből
← Régebbi szerkesztésÚjabb szerkesztés →
VizuálisWikiszöveges
Arklur (vitalap | szerkesztései)
381 szerkesztés
Arklur (vitalap | szerkesztései)
381 szerkesztés
41. sor: 41. sor:
**Az 5. sorban a gyökér a 6 lesz, így azt berajzoljuk a 9-es bal fiának. És itt látszik is, hogy hiba van, hiszen <math> < > < </math> sorrend van, ebből következik, hogy ilyen fa nem létezhet.
**Az 5. sorban a gyökér a 6 lesz, így azt berajzoljuk a 9-es bal fiának. És itt látszik is, hogy hiba van, hiszen <math> < > < </math> sorrend van, ebből következik, hogy ilyen fa nem létezhet.


::::::::::[[File:post_tabla.GIF|400px]] [[File:graf.png|300px]]
::::::::::[[File:post_tabla.png|400px]] [[File:graf.png|300px]]
}}
}}


A lap 2013. június 12., 20:55-kori változata

2013.04.03. ZH megoldásai

1. Feladat

TODO

Megoldás
TODO

2. Feladat

TODO

Megoldás
TODO

3. Feladat (Van megoldás)

Kaphatjuk-e az 1,7,3,6,11,15,22,17,14,12,9 számsorozatot úgy, hogy egy (a szokásos rendezést használó) bináris keresőfában tárolt elemeket posztorder sorrendben kiolvasunk?

Megoldás
Megjegyzés a feladathoz
  • Szokásos rendezést használó bináris keresőfa:
  • Postorder:
    • Rekurzívan . Magyarul előbb meglátogatja a gyökérnél kisebbeket, utána a nagyobbakat, és ezután jön csak a gyökér.
    • Egyik fontos tulajdonsága, hogy a gyökér az mindig a (figyelt) lista végén van.
  • Első lépésnek írjuk fel egy táblázatba a számokat (az oszlopszámot tudjuk, ez esetben 11, sorok száma meg majd alakul...).
  • A továbbiakban az i. sorban jelöljük, hogy melyik elem a gyökér (=), és hogy melyek a nála kisebbek (<), avagy nagyobbak (>) (a képen keretezéssel jelzem, hogy melyik az éppen figyelt lista). Ez azért hasznos, mert a posztorder bejárás során, ezzel a technikával mindig olyan sorrendet kell kapjunk, hogy , vagyis nem állhat fel olyan helyzet, hogy vagy .
    • Az 1. sorban a 9 lesz a gyökér. Felrajzoljuk a 9-t gyökérnek. (Bal oldalt lesz a hiba, de gyakorlásképp nézzük inkább a jobb oldalt.)
    • A 2. sorban a 12 lesz a gyökér, így a 12-est felrajzoljuk a 9-es jobb fiának. Nála csak a 11 a kisebb (a vizsgált listában), így a 11-t berajzoljuk a 12 bal fiának.
    • A 3. sorban 14 lesz a gyökér, így e 14-est felrajzoljuk a 12-es jobb fiának.
    • A 4. sorban a 17 lesz a gyökér, így ez a 14-es jobb fia lesz. A 15 és 22 pedig értelemszerűen a bal, és jobb fia lesz 17-nek.
    • Az 5. sorban a gyökér a 6 lesz, így azt berajzoljuk a 9-es bal fiának. És itt látszik is, hogy hiba van, hiszen sorrend van, ebből következik, hogy ilyen fa nem létezhet.
    • Fájl:Post tabla.png Fájl:Graf.png

    4. Feladat

    TODO

    Megoldás
    TODO

    5. Feladat

    TODO

    Megoldás
    TODO

    6. Feladat

    TODO

    Megoldás
    TODO

    7. Feladat

    TODO

    Megoldás
    TODO

    8. Feladat

    TODO

    Megoldás
    TODO
    A lap eredeti címe: „https://vik.wiki/index.php?title=Algoritmuselmélet_-_ZH,_2013.04.03.&oldid=168005”