Clasa VI/VII/VIII lecția 37 - 04 iun 2013

Tema - verificare

• Puzzle: avem 26 de bile care arată identic, una este ceva mai ușoară. Avem la dispoziție o balanță. Găsiți bila mai ușoară din trei cîntăriri.
• Un rege organizează o petrecere mare de ziua lui. Petrecerea începe peste 24 de ore. Regele află că una din cele 1000 de sticle de vin pe care le va servi este otrăvită. Otrava acționează ciudat: omul care bea chiar și cea mai mică cantitate din această otravă nu are nici un simptom vreme de 24 de ore, apoi moare subit. Regele are sclavi la dispoziție pe care îi poate folosi. Lui nu îi pasă cîți sclavi mor, dar îi pasă cîți sclavi beau vin, deoarece un sclav care a băut vin nu poate fi folosit la treabă, ci trebuie izolat spre observare. Care este numărul minim de sclavi cu care regele poate afla sticla otrăvită?
• Se dă un vector sortat de n elemente întregi distincte. Să se găsească dacă există indicele i astfel încît v[i] == i. Găsiți un algoritm divide et impera care are complexitate O(log n).
• Problema latin (generare pătrate latine de dimensiune 2ⁿ x 2ⁿ). Rezolvare: decît mult şi fără rost, mai bine puţin şi prost. Doar doi dintre voi au rezolvat-o şi fără a folosi divide et impera. Soluții aici [1]

Lecție - toate clasele

Aplicaţie a pointerilor: little endian sau big endian?

Scrieţi o funcție care determină dacă calculatorul pe care se excută ea reprezintă numerele în format little endian sau big endian. Little endian este reprezentarea în care octetul mai puțin semnificativ este primul (la adresă de memorie mai mică).

Rezolvare:

int isLittleEndian() {
  int n = 1;
  return *((char *)&n);
}

Sortare

Quick Sort

Am discutat despre cum funcționează algoritmul quick sort. Iată, mai jos, o implementare diferită de cea care se predă în școală, ceva mai simplă, mai eficientă și, cred, mai ușor de ținut minte. Această implementare este mai aproape de implementarea din lumea reală.

void myqsort( int begin, int end ) {
  int aux, b = begin, e = end,
    pivot = v[begin + rand() % (end - begin + 1)];

  while ( b <= e ) {
    while ( v[b] < pivot ) b++;
    while ( v[e] > pivot ) e--;
    if ( b <= e ) {
      aux = v[b]; v[b] = v[e]; v[e] = aux;
      b++; e--;
    }
  }
  // acum [begin..e] sint mai mici sau egale cu pivotul
  // si [b..end] sint mai mari sau egale cu pivotul
  if ( begin < e ) myqsort( begin, e );
  if ( b < end ) myqsort( b, end );
}

De remarcat, diferenţe faţă de implementarea clasică:

• ne oprim din căutare şi dacă găsim un element egal cu pivotul
• indicii vor înainta cel puţin o dată în interiorul buclei while
• apelurile recursive nu se fac, aşa cum ne-am aştepta, de la begin la b şi de la e la end, deoarece oprirea din buclă se face atunci cînd indicii se încalecă, ei vor fi în ordine inversă în final.

Ce complexitate are şi cîtă memorie foloseşte? Quick sort are timp O(log n) pe cazul mediu și O(n) pe cazul cel mai rău. El folosește O(log n) memorie pe cazul mediu și O(n) memorie pe cazul cel mai rău. Cu toate acestea, prin eliminarea recursiei la coadă, se demonstrează că quick sort folosește memorie O(log n) pe cazul cel mai rău. Pentru a ajunge la această memorie folosită trebuie să avem grijă ca al doilea apel recursiv să fie cu vectorul de lungime mai mare.

Aplicații quick sort

Pivotarea, al k-ulea element în vectorul sortat, folosind algoritmul quick select.

Temă

• Insist să rezolvaţi problema Latin.
• Problema ZParcurgere la vianuarena.
• Problema Tabela la vianuarena.
• Opțional: Problema Antitir la vianuarena, ca aplicație la quick select. Folosiți o modificare a algoritmului de pivotare prezentat mai sus.