Clasa VI/VII/VIII lecția 21 - 19 feb 2013

Anunț: cine vrea să lucreze extra, contactați-mă pe email (cristian@francu.com) pentru a-mi cere idei de probleme de rezolvat.

Clasa a șasea, a șaptea și a opta

Test: rezolvați problema creioane la vianuarena (ONI 2008, clasa a 6-a). Timp de lucru: o oră. Atenție: problema este modificată. Cei de a șasea: scopul este să luați 80p. Ceilalți: 100p

Discuție despre rezolvarea problemei. Varianta forță brută și varianta folosind memoizare și analiză amortizată. Iată că se poate întîlni așa ceva, chiar și la clasa a șasea :-)

Memoizare

Memoizare este metoda prin care atunci cînd calculăm valoarea unui calcul scump, de obicei făcut într-o funcție, o păstrăm într-un tablou pentru a economisi timp în caz că acel calcul trebuie refăcut în viitor, respectiv atunci cînd funcția este chemată cu aceiași parametri. Un exemplu de folosire a memoizării este cînd scriem o funcție recursivă care să calculeze 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. Putem însă modifica 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 ) // calculat deja
    return val[n];
  return val[n] = fib( n-1 ) + fib( n-2 );
}

Clasa a șasea

Deși am discutat despre rezolvarea problemei prieteni dată la olimpiada pe sector constat ca nimeni nu a reușit să o facă de 100p. Îngrijorător, cu atît mai mult cu cît nu este o problemă grea. Iată o rezolvare posibilă [1]

Clasa a șaptea

Discuție despre rezolvarea problemei taxe la campion, deoarece nimeni nu pare să o fi rezolvat.

Clasa a opta

Deși am discutat despre rezolvarea problemei fermier data trecută, constat că nu mulți au și rezolvat-o. Iată o soluție bazată pe ceea ce am discutat, care deși nu folosește sort() este comparabilă ca lungime cu celelalte soluții de 100p. Dacă ar fi folosit sort() această sursă ar fi avut 36 de linii scrise aerisit, cu multe linii goale și 0.68KB. Rezolvare aici [2]

Rămîn în continuare uimit de dorința voastră obsesivă de a folosi procedura încorporată de sortare, chiar și la vianuarena unde nu sînteți în concurs ci doar vă exersați cunoștințele. Deduc ca sînteți rezolvitori de probleme și nu informaticieni: nu doriți să învățați să scrieți o sortare, ci doar să o folosiți, ca niște utilizatori. Prin extrapolare, dacă ar exista o funcție de bibliotecă solveAll() care v-ar rezolva orice problemă de la olimpiadă, campion, infoarena, etc, atunci informatica ar înceta brusc să prezinte vreun interes pentru voi, deoarece nu ați mai avea ce rezolva. În fine ați fi liberi să faceți ceea ce vreți cu adevărat în viață. Gîndiți-vă la asta. Nu e prea tîrziu să vă schimbați pasiunea. Informatica este cu mult mai mult decît un biet concurs. Dacă nu vă place să scrieți o sortare, poate nu aveți ce căuta la acest cerc (amenințare directă, nevoalată). Pentru cei ce au uitat criteriile de selecție la cerc vă rog să vi le împrospătați aici și să vă revizuiți atitudinea.

Discuție despre rezolvarea problemei piramida la vianuarena. Rezolvarea care nu se bazează pe faptul că L este mic, sau pe sort() din C, sau pe string.h, așa cum ar trebui să vă obișnuiți și voi. Soluție aici [3]

Teme

Teme clasa a șasea

• Terminați problema creioane (ONI 2008, clasa a 6-a) la vianuarena.
• Problema tablou (ONI 2008, clasa a 6-a) la campion.
• Opțional: problema fermier (OSI 2013, clasa a 8-a) la vianuarena.
• Opțional: problema raze (ONI 2010, clasa a 8-a) la campion.

Teme clasa a șaptea

• Terminați problema creioane (ONI 2008, clasa a 6-a) la vianuarena.
• Terminați problema taxe (ONI 2009 clasa a 7-a) la campion.
• Opțional: problema fermier (OSI 2013, clasa a 8-a) la vianuarena.
• Opțional: problema raze (ONI 2010, clasa a 8-a) la campion.
• Opțional: probleme date la baraj la ONI în anii trecuți, vezi teme clasa a 8-a, ultima opțiune.

Teme clasa a opta

• Terminați problema creioane (ONI 2008, clasa a 6-a) la vianuarena.
• Dacă nu le-ați făcut de 100p la olimpiadă terminați problemele fermier și piramida, date la olimpiada pe sector.
• Opțional: problema optim (baraj ONI 2012) la campion folosind programare dinamică.
• Opțional: problema cifreco (baraj ONI 2012) la campion folosind metoda tabelară din programarea dinamică.
• Opțional: alte probleme de baraj ONI (toate la campion):
  • joc18 (ONI 2011 baraj)
  • poteci (ONI 2011 baraj)
  • bila (ONI 2010 baraj)
  • dartz (ONI 2010 baraj)
  • flori (ONI 2010 baraj)