Note de curs, clasele 9-10, 1 februarie 2013
From Algopedia
Jump to navigationJump to search
Teme din trecut
- centrul / bicentrele unui arbore
- diagrame Voronoi pe arbore (castele pe o hartă)
- încă nu s-au făcut, rămân pentru viitor
Programare dinamică
- repetarea exemplului introductiv: fibonacci(n) recursiv / nerecursiv
- subprobleme repetate, fiecare din ele rezolvată recursiv
- joc cu 2n numere
- dacă se cere doar victoria, dar nu la scor maxim, se poate face în O(n) (suma elementelor de pe poziții pare / impare)
- cel mai lung subșir crescător
- discuție sumară în O(n2)
- discuție detaliată în O(n log n)
- planificarea petrecerii companiei (dinamică pe arbore)
- dându-se n, să se tipărească un număr în baza 10 care folosește doar cifrele 0 și 1 și care se divide cu n
- dacă se cere cel mai mic număr -- programare dinamică
- dacă se cere orice număr -- principiul lui Dirichlet (generăm maxim n numere de forma 111...1 și facem diferența)
- distanța Levenshtein
- observație: necesită doar memorie O(n) dacă se cere doar distanța, nu și operațiile
Teme
- Se dă un vector V cu n elemente. Să se tipărească o submulțime cu sumă maximă, divizibilă cu n
- Se dă o rețea de 4 x n noduri, toate conectate pe cele 4 direcții. Să se spună câte cicluri hamiltoniene există.