Note de curs, clasele 11-12, 7 decembrie 2012
From Algopedia
Jump to navigationJump to search
Programare dinamică
- distanța Levenshtein
- operație suplimentară: inversarea a două caractere
- cea mai lungă subsecvență comună
- memorie O(n) dacă se cere doar lungimea
- trucuri pentru aflarea subsecvenței când memoria disponibilă este mai mică decât O(m * n)
- cel mai lung subșir crescător
- observație: este cea mai lungă subsecvență comună între V și V sortat
- graf permutare - clică maximă
- nu întotdeauna trebuie să ne repezim la programare dinamică
- exemplu: dintr-un vector de 2 * n numere, doi jucători aleg pe rând câte un număr de la capăt. Cel care obține suma mai mare câștigă
- greedy: să se găsească o strategie de câștig pentru primul jucător
- PD: să se găsească scorul maxim pe care îl poate obține primul jucător
Teme
- Se dau 12 bile, toate identice ca aspect, din care 11 au aceeași greutate, iar una este mai grea sau mai ușoară. Se dă o balanță cu două talere. În trei cântăriri, să se afle care este bila diferită și dacă este mai grea sau mai ușoară.
- Să se calculeze numărul de circuite hamiltoniene într-o rețea de 4 * n orașe.
