Note de curs, clasele 9-10, 25 ianuarie 2013

From Algopedia
Revision as of 17:52, 29 January 2013 by Cata (talk | contribs) (Created page with "== Arbori și recursivitate == * rezolvare detaliată (grafică) pentru aflarea diametrului unui arbore ** fiecare nod primește de la copii (1) adâncimea subarborelui și (2) ...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigationJump to search

Arbori și recursivitate

  • rezolvare detaliată (grafică) pentru aflarea diametrului unui arbore
    • fiecare nod primește de la copii (1) adâncimea subarborelui și (2) cea mai lungă cale cuprinsă integral în acel subarbore
    • nodul combină informațiile de la copii și le trimite în sus spre părinte
  • rezolvare detaliată pentru reconstituirea unui arbore din preordine + postordine
    • cu o stivă
  • rezolvare detaliată pentru reconstituirea unui arbore din preordine + inordine
    • cu o stivă (mici diferențe față de problema anterioară)

Programare dinamică

  • concept general
  • exemplu: Fibonacci implementat recursiv
    • desenarea arborelui pentru F(5)
    • complexitate exponențială căci numărul de apeluri este exponențial
  • recurență pentru Fibonacci, implementare liniară
  • numărul de parantezări corecte pentru n perechi de paranteze
    • listarea tuturor pentru n = 1, 2, 3, 4
    • deducerea recurenței

Teme

  • diagrame Voronoi pe arbore (orașe din care unele au benzinării)
    • la ce benzinărie merge fiecare oraș care nu are benzinărie proprie
    • câte noduri deservește fiecare benzinărie (orașele care au mai multe benzinării la distanță minimă se împart între ele cu virgulă)
  • Se dă un vector cu 2 * n elemente. Doi jucători aleg pe rând câte un număr de la capete. La final, jucătorul cu suma mai mare câștigă
    • să se demonstreze că primul jucător câștigă sau face remiză întotdeauna
    • să se determine scorul maxim pe care îl poate obține