Clasa a VI-a lecția 25 - 19 mar 2015

Tema - comentarii

Problema covor

Comentarii generale

Ați ignorat rezolvarea discutată: doar doi dintre elevii de la cercul unu au implementat rezolvarea optimă, bazată pe formule matematice, discutată la cerc. Oare de credeți că am discutat acea variantă, ca să avem cu ce umple două ore? Dragilor, dacă nu vreți să studiați lucruri grele puteți să studiați abecedarul. Sau astrologia. Pentru mediocritate nu aveți nevoie să veniți la acest cerc: ea se află peste tot în jurul vostru. Cercul înseamnă dorința de a vă autodepăși. Voi nu vreți să vă autodepășiți, ci să scăpați de teme.

Programare aproximativă: unii din voi au un stil de programare aproximativă care nu își are locul la cerc. În fapt nu își are locul nicăieri în lume, cu atît mai puțin la acest cerc. Scrieți bucle fără a gîndi pînă la capăt condiția de oprire, apoi adăugați un steguleț pentru a ieși forțat. Faceți afișări în interiorul buclei, la momentul cînd ați găsit soluția, în loc să le faceți corect, după ce ați ieșit din buclă. Scrieți cod lung, încîlcit, care provine dintr-o lene de a gîndi.

Comentarii particulare

• Tinca: felicitări, ești unul din cei doi elevi care au avut curajul să încerce rezolvarea optimă discutată la cerc. Tu spui că subiectele au fost penibile, dar nu ai reușit să iei decît 86p. Deci cum ești tu? :)
• Mirică: rezolvarea foarte bună, dar nu ai avut curajul să încerci rezolvarea optimă discutată la cerc. Ai preferat suta de puncte provocării intelectuale. Știm cum stăm :)
• Alăzăroaie: bravo, ai avut curajul să încerci varianta optimă. Cred că greșeala este pe cazul "întors". Verifică formulele cu programul prezentat mai jos.
• Ichim: soluția ta este plauzibilă. Dar nici tu nu ai avut curajul să încerci rezolvarea optimă discutată la cerc. Păcat. Cred că dacă te străduiai să obții formulele matematice ai fi luat mai multe puncte (mai ales că nu erai în concurs)
• Fares: rezolvarea ta este tehnic corectă. Însă este încîlcită. Tipărești rezultatul în buclă, deși el este un singur număr. Folosești un steguleț. Și nici nu ai avut curajul să încerci rezolvarea optimă discutată la cerc.
• Zahiu: rezolvarea clasică, nu cea optimă. Stegulețe inutile, afișări în bucla de calcul, cazuri tratate particular în mod inutil. Un exemplu de programare aproximativă la cel mai înalt nivel. Ești fratele lui Fares cumva? Aveți stilul aproape identic.
• Mocioi: rezolvare bună, corectă. Fără nici o legătură cu rezolvarea optimă discutată. Ești printre cei mai buni elevi din țară și totuși te-ai mulțumit cu o rezolvare mediocră.
• Nanu: rezolvare corectă, clasică. Nici tu nu ai încercat soluția optimă. Atenție la indentare, nu este opțională.
• Băncuță: rezolvare corectă, clasică. Nu ai încercat soluția optimă.
• Georgescu: o soluție deosebită. Ca și mulți colegi ai tăi nu ai avut curajul să încerci soluția optimă discutată la cerc, dar ai o soluție altfel decît ceilalți.
• Cioltan: rezolvare corectă, dar neoptimă, n-ai incercat nimic din ce am vorbit la cerc.
• Dumitriu: la fel.
• Cazacu: n-ai rezolvat-o. Frumos.
• Costescu: la fel.
• Mușat: n-ai rezolvat-o.
• Pițur: la fel.

Aceste comentarii sînt făcute cu 10 ore înainte de închiderea temei. Unii din voi veți rezolva problema în aceste zece ore. Însă este o idee foarte proastă. Cam ce puteți rezolva în grabă, în ultima clipă?

Tema - rezolvări

Rezolvări aici [1]

Lecție

Concurs

Concurs 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

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

Atenție! La această temă se vor adăuga problemele de la concursul ce va urma.

Rezolvări aici [2]