Clasa VI/VII/VIII lecția 11 - 13 nov 2012

Introducere

• Se dă un test de evaluare a polițailor din România; ei dispun de o planșă cu găuri de diverse forme, rotunde, pătrate, triunghiulare, etc, precum și de formele care se potrivesc în aceste găuri. Polițaii trebuie să pună formele potrivite în găurile potrivite. În urma testului rezultă că există două feluri de polițai: inteligenți și puternici.
• Se dă un test de evaluare a elevilor de la Vianu în vederea selecției pentru un concurs. În urma acestui test a rezultat că există două feluri de elevi: unii care știu matematică dar nu știu informatică, și alții care nu știu matematică dar nu știu nici informatică.
• Sînt surprins de următoarele lucruri:
  • La problema antitir nimeni nu și-a dat seama că coordonatele țintei sînt medianele pe x, respectiv pe y (median = elementul din mijlocul unui vector sortat), problemă făcută la cerc, pe numele ei problema selecției.
  • Unii din voi au crezut că media coordonatelor este răspunsul la problemă, în ciuda faptului că unul din exemple demonstra că nu este cazul. Aceasta arată că informatica este precum credința: dacă crezi cu tărie, trebuie să fie adevărat, în ciuda tuturor dovezilor contrare.
  • La problema permutărilor unice, cei care nu ați știut formula nu ați încercat nimic plauzibil folosind recursivitate, făcută la cerc vreme de o lună.
• În lumina ultimelor revelații vom încerca să cimentăm mai bine materia care a intrat pe o ureche și a ieșit pe alta. Vă sugerez dopuri de urechi, pentru a astupa una din ele. Puteți face economie cumpărînd o pereche în doi, deoarece nu aveți nevoie decît de una. Cînd vin din San Francisco promit să vă păstrez perechea pe care mi-o dau pe avion (nefolosită).

Clasa a șasea

Exerciții recapitulative

Rezolvați în timpul cercului următoarele probleme:

• Problema nr01, campion, concursul .campion 2005. O problemă de baze de numerație. Rezolvare aici [1]
• ceas2, campion, OJI 2007 clasa 7. Problema conține toate ingredientele predate la cerc în ultimele lecții: conversii între bazele 2 și 10, lucrul cu matrice, lucrul cu caractere.

Temă clasa a șasea

• Probleme din urmă: joc16 (campion), xy (campion), trigrame (vianuarena), bile6 (campion) ONI 2012 clasa 7, folosind radix sort sau problema zigzag (campion) ONI 2012 clasa 7, folosind neapărat radix sort, tetris (campion) ONI 2009, clasa 6, pentru simulare
• Ce v-a rămas din clasă
• Opțional: macheta (campion) ONI 2011 clasa 8

Clasa a șaptea și a opta

Numere aleatoare

Numerele aleatoare (în engleză random numbers) sînt importante în informatică, avînd aplicații în jocuri, simularea fenomenelor fizice, criptografie. Quicksort folosește numere aleatoare pentru a selecta pivotul. De asemenea unul din algoritmii de selecție, făcut la cerc. În aceste cazuri numerele aleatoare minimizează șansa de a întîlni un caz defavorabil care ar duce la o complexitate pătratică în loc de n log n sau n. Să vedem cum putem folosi aceste numere.

• Funcția de bază este rand(). Ea returnează un număr aleator între 0 și un număr foarte mare, maximul fiind o constantă numită RAND_MAX. Pentru a genera un număr aleator între 0 si n-1 vom folosi expresia rand() % n. Pentru a genera un număr aleator în intervalul [a, b) (a inclusiv, b exclusiv) vom folosi expresia a + rand() % (b – a). Pentru a folosi funcția rand trebuie să includem header-ul stdlib: #include <stdlib.h>
• Un program care folosește rand() va genera aceleași valori la fiecare execuție. Uneori acest lucru deranjează. În aceste cazuri este nevoie să resetăm pornirea lui rand() înainte de prima folosire. Aceasta se face prin funcția srand(), care furnizează un nou element de pornire pentru secvența de numere aleatoare. Pentru a furniza un element de pornire diferit de fiecare dată cînd pornim programul ne vom folosi de funcția time() care returnează timpul curent. Exemplul tipic de folosire al lui srand() este srand( time( NULL ) ). Pentru funcția time() trebuie să includem headerul time.h: #include <time.h>
• Exemplu de folosire: se citește n și k, să se afișeze k numere aleatoare între 0 și n-1. Numerele trebuie să fie diferite de fiecare dată cînd se execută programul.

Exerciții recapitulative

Vom rezolva problemele de la testul de calificare pentru concursul de la Șumen (cu trimitere la vianuarena, să ia 100 de puncte).

• Problema Numărul de permutări unice (npermunic) de la vianuarena. Pentru a exersa ideea de recursivitate vom presupune că nu știm formula. Ce putem face în acest caz?
  • Să găsim o formulă de recurență și să o implementăm recursiv. Aceasta va depăși timpul.
  • Să optimizăm acea formulă pentru a nu recalcula valori deja calculate. Pentru aceasta vom folosi un tabel de valori. Cum ajungem de la un vector de frecvențe la un indice în tabel? O variantă ar fi să folosim un număr în bază variabilă: cifra k a vectorului de frecvențe se înmulțește cu produsul (p_k-1+1)∙(p_k-2+1)∙...∙(p₀+1). Varianta aceasta va trece mai multe teste.
  • Ultima optimizare: U([2,3]) este totuna cu U([3, 2]). Ce-ar fi să sortam listele înainte de a le căuta în tabelul de valori precalculate? Această variantă trece toate testele.
• Problema Antitir de la vianuarena.
  • Primul lucru de observat este faptul că dacă mișcăm ținta pe orizontală suma se modifică strict în funcție de valorile pe axa x. Această observație ne permite să reducem problema de la o problemă în plan la una liniară: să se găsească punctul pe o axă a cărui sumă a distanțelor la n puncte este minimă. Aplicînd de două ori această subproblemă vom găsi coordonatele țintei de sumă minimă.
  • Al doilea lucru de observat: să ne uităm la numerele sortate pe axă. Să pornim cu ținta din punctul x₀ (de coordonată minimă). Să considerăm suma în acest punct ca fiind S. Dacă ne deplasăm spre dreapta cu o unitate cum va varia suma S? Ea va crește cu o unitate din cauza punctului x₀ și va scădea cu n-1 unități datorită celorlalte puncte. Per total suma va scădea pe măsura ce ne deplasăm la dreapta. Cînd ajungem în punctul x₁, lucrurile se schimbă: cînd ne deplasăm la dreapta suma crește cu două unități și scade cu n-2. Scade în continuare, dar mai puțin. Pînă cînd scade suma S? Pînă cînd ajungem la punctul de la jumate. În acest moment, mergînd spre dreapta, suma S va crește cu n/2 unități din cauza punctelor din stînga și va scădea cu n/2 unități datorită elementelor din dreapta. Deci nu va mai scădea. Dacă continuăm să mergem spre dreapta suma S va începe să crească. De aici rezultă că elementul căutat este elementul din mijloc în vectorul sortat.
  • În urma acestor două observații rezultă algoritmul final, de complexitate liniară: vom găsi elementul din mijloc, numit și median, pentru fiecare din coordonate, folosind algoritmul de selecție predat într-o lecție anterioară. Apoi vom calcula suma distanțelor lui la toate punctele.
  • Implementarea găsirii medianului se poate face în două feluri. Metoda modernă face mai puține interschimburi:

  i = start; j = end;
  while ( c[i] < pivot ) i++;
  while ( c[j] > pivot ) j--;
  while ( i <= j ) {
    aux = c[i];
    c[i] = c[j];
    c[j] = aux;
    i++; j--;
    while ( c[i] < pivot ) i++;
    while ( c[j] > pivot ) j--;
  }
  // [start...j] contine numere mai mici sau egale cu pivotul
  // [i...end]   contine numere mai mici sau egale cu pivotul
  // e posibil sa fie o pozitie intre j si i; acolo ar fi pivotul
  if ( (i - j) == 2 ) { // intre ele e pivotul
    if ( (j + 1) == med )
      return pivot;
  }
  if ( med <= j )
    end = j;
  else
    start = i;
}

Temă clasa a șaptea

• Rămasă din urmă: mesaj3 (campion) ONI 2011 clasa 7
• Rămase din urmă: problema bile6 (campion) ONI 2012 clasa 7, folosind neapărat radix sort sau problema zigzag (campion) ONI 2012 clasa 7, folosind neapărat radix sort
• Rămasă din urmă: problema tetris (campion) ONI 2009 clasa 6, pentru simulare
• antitir (vianuarena)
• Opțional: macheta (campion) ONI 2011 clasa 8
• Opțional: skyline la vianuarena

Temă clasa a opta

• Ramase din urmă: macheta (campion) oni 2011 clasa 8, skyline (vianuarena)
• Rămasă din urmă: problema bile6 ONI 2012 clasa 7, folosind neapărat radix sort
• npermunic și antitir la vianuarena
• Opțional: puncte5
• Opțional: zeratul
• Opțional: taburet baraj 2011, canonizare, vedere în spațiu