Informatică Algoritmi
Exercitii programare dinamica bac
Exercițiile de programare dinamică la bac implică rezolvarea problemelor prin descompunerea în subprobleme mai mici și stocarea rezultatelor pentru a evita recalculările. Acestea testează capacitatea de a identifica recurențe și de a construi tabele de soluții.
Probleme frecvente
- Șirul lui Fibonacci Calculează al n-lea termen folosind recurența F(n) = F(n-1) + F(n-2), cu F(0)=0, F(1)=1. Exemplu: F(5)=5, calculat din F(4)=3 și F(3)=2.
- Problema rucsacului 0-1 Pentru obiecte cu greutăți și valori, maximizează valoarea totală fără a depăși capacitatea. Folosești un tabel dp[i][w] pentru primele i obiecte și greutatea w.
- Cea mai lungă subsecvență comună Găsește lungimea celei mai lungi subsecvențe comune a două șiruri. Recurența: dacă caracterele sunt egale, LCS(i,j)=1+LCS(i-1,j-1), altfel max(LCS(i-1,j), LCS(i,j-1)).
Pași de rezolvare
- 1 Definește subproblemele Identifică cum poți descompune problema în părți mai mici; de exemplu, pentru Fibonacci, subproblemele sunt F(k) pentru k<n.
- 2 Stabilește recurența Scrie o formulă care exprimă soluția unei subprobleme în funcție de altele; pentru rucsac, dp[i][w] = max(dp[i-1][w], val[i] + dp[i-1][w-greutate[i]]).
- 3 Implementează bottom-up Calculează soluțiile de la cele mai mici la cele mai mari, stocând într-un tabel; pentru Fibonacci, folosești un vector care se completează de la 0 la n.
Exersează recurențele și implementarea tabelelor pentru a rezolva rapid la examen.