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ă.