Clasa a VI-a lecția 26 - 10 mar 2014

Lecție

Concurs

Concurs clasa a 6^a

• creioane dată la ONI 2008 clasa a 6^a

Memoizare

Memoizarea este o metodă de a face un program mai rapid fără a-i schimba modul în care el funcționează. Ideea ei este ca atunci cînd efectuăm un calcul scump să păstrăm valoarea calculată într-un tablou pentru a economisi timp în cazul cînd în viitor vom avea din nou nevoie de acea valoare. Să o învățăm prin exemple.

Exemplul 1

Să presupunem că ni se dau n numere a₀, a₁, ..., a_n-1 și ni se cere să afișăm factorialele acelor numere modulo k. O soluție naivă ar putea fi următoarea:

for ( i = 0; i < n; i++ ) {
  p = 1;
  for ( j = 2; j < a[i]; j++ )
    p = (p * j) % k;
  printf( "%d ", p );
}

Să calculăm complexitatea tipului de execuție: pentru fiecare număr a_i vom face O(a_i) înmulțiri, drept pentru care complexitatea soluției este O(suma(a_i)). Desigur că putem face un program mai eficient care calculează un vector fact[i] unde fact[i] este i! (i factorial). Acest vector se poate calcula în O(max(a_i)), după care printr-o parcurgere a numerelor a_i vom putea calcula rezultatul ceea ce duce la o complexitate optimă de O(n + max(a_i)).

Însă în unele cazuri nu este ușor să schimbăm radical programul pentru a scrie o soluție mai eficientă decît soluția naivă. Cum putem folosi tehnica memoizării pentru a modifica foarte puțin soluția brută și a o aduce la complexitate optimă? Am putea ca de fiecare dată cînd calculăm a_i! să păstrăm rezultatul într-un vector la poziția a_i. Vom păstra, de asemenea și toate factorialele intermediare calculate pe parcurs. Atunci cînd vom avea nevoie de calculul unui factorial vom merge în jos pînă la primul factorial calculat. Iată implementarea:

fact[1] = 1; // pentru a ne opri la final
for ( i = 0; i < n; i++ ) {
  j = a[i];
  while ( fact[j] == 0 )      // cautam in jos primul factorial calculat
    j--;
  p = fact[j];
  for ( j++; j <= a[i]; j++ ) // calculam toate valorile pina la a[i]
    fact[j] = (fact[j-1] * j) % k;
  printf( "%d ", fact[j] );
}

Ce complexitate în timp are această soluție? Deoarece ea nu repetă calcule în vectorul fact rezultă că fiecare element al vectorului va fi calculat cel mult odată, în timp O(1), deci soluția va fi optimă, O(n+max(a_i)). Observați că am obținut aceeași complexitate optimă dar fără a schimba structura algoritmului nostru naiv, ci doar memorînd rezultate parțiale într-un vector. Aceasta este exact ideea memoizării.

Exemplul 2

O astfel de problemă este și problema creioane. Rezolvarea forță brută este relativ ușor de scris, dar nu se va încadra în timp pentru teste mari deoarece are complexitate O(n²). O putem însă modifica ca atunci cînd calculăm înălțimea unei grămezi de creioane să calculăm înălțimea fiecărui creion din grămadă. În acest fel vom avea O(1) calcule per element, ceea ce duce la o soluție optimală liniară, O(n).

Temă

Tema 26 clasa a 6^a

• creioane dată la ONI 2008 clasa a 6^a
• bila1 ONI 2010 baraj gimnaziu

Atenție! La această problemă se vor adăuga problemele de la concursul pe care îl vom da săptămîna aceasta.

Rezolvări aici [1]