Note de curs, clasele 9-10, 25 ianuarie 2013
From Algopedia
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