Clasa a VI-a lecția 25 - 05 apr 2016

Temă

Tema 23 clasa a 6^a

• factk .campion 2004
• fact ONI 2006 clasa a 9^a
• trei divizori

Rezolvări aici: [1]

Lecție

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

Un exemplu avansat de folosire a memoizării, de clasa a 7^a, pentru cei care știu funcții și recursivitate este o funcție cunoscută care calculează al n-ulea număr din șirul lui Fibonacci. Un mod naiv și direct de a scrie funcția este:

int fib( int n ) {
  if ( n == 1 || n == 2 )
    return 1;
  return fib( n-1 ) + fib( n-2 );
}

Problema cu această implementare este că va chema de multe ori funcția fib cu aceleași valori, refăcînd frecvent aceleași calcule. De exemplu, fib(n-2) se va calcula de două ori, fib(n-3) se va calcula de 3 ori, iar fib(n-4) se va calcula de 5 ori! Faceți desenul și convingeți-vă. Numărul de apeluri crește exponențial.

O soluție ar fi să implementăm funcția nerecursiv, așa cum deja știm. În unele cazuri acest lucru complică foarte mult codul, deoarece implică o schimbare radicală. Putem însă modifica puțin funcția fib pentru a memora valoarea o dată calculată, astfel încît la un următor apel să o returneze direct. Pentru aceasta vom folosi un vector de valori, să-i spunem val, în care vom memora valorile șirului lui Fibonacci gata calculate. Iată modifcarea:

int val[1000] = { 1, 1 };

// exemplu de funcție fibonacci implementată folosind memoizare
int fib( int n ) {
  if ( val[n] == 0 ) // inca necalculat
    val[n] = fib( n-1 ) + fib( n-2 ); // il calculam in tabel
  return val[n]; // returnam valoarea din tabel
}

Exemplul 3

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 25 clasa a 6^a

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

Rezolvări aici [2]