Clasa a V-a lecția 36 - 2 mai 2020

From Algopedia
Jump to navigationJump to search
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

Lecţie

Nu există video. Lecția este doar teoretică și disponibilă online.

Instrucțiunea do-while

Instrucțiunea do-while în limbajul C implementează o structură repetitivă de tip REPEAT-UNTIL, care este o structură similară cu WHILE-DO. Iată schemele logice pentru cele două structuri alternative:

Schemă logică WHILE-DO
while ( <cond> ) {
  <prel>;
}
Schemă logică REPEAT-UNTIL
do {
  <prel>;
} while ( !<cond> );

Structura REPEAT-UNTIL repetă o secvenţă pînă cînd condiţia este adevărată. De aceea ieşirea din buclă se face pe "DA". Prin contrast, instrucţiunea do-while din C execută corpul buclei cîtă vreme condiţia este adevărată, de unde şi operatorul not (!) introdus în C.

Oricare din cele două structuri repetitive sînt suficiente pentru a descrie orice algoritm. Cu toate acestea, structura WHILE-DO este mai generală decît structura DO-UNTIL, deoarece corpul buclei REPEAT-UNTIL se execută cel puţin o dată, pe cînd bucla WHILE-DO poate să nu se execute nici o dată. Acesta este şi motivul pentru care nu am predat-o pînă acum.

Exemplu

Dîndu-se un număr n să se descompună în sumă de două pătrate perfecte nenule. Vom folosi următoarea metodă: vom căuta o descompunere n = a * a + b * b. Putem considera că a < b, fără a pierde din soluţii. Astfel, vom varia a * a de la 1 pînă la n / 2, verificînd dacă n - a * a este pătrat perfect. Această verificare se face extrăgînd radicalul şi verificînd că pătratul acestuia este chiar numărul original. Iată două variante de implementare, prima folosind while-do, iar a doua folosind do-while:

Implementare cu WHILE-DO Implementare cu REPEAT-UNTIL
  a = 1;
  d = n - a * a;
  b = sqrt( d );
  while ( b * b < d && 2 * a * a < n ) {
    a++;
    d = n - a * a;
    b = sqrt( d );
  }
  a = 0;
  do {
    a++;
    d = n - a * a;
    b = sqrt( d );
  } while ( b * b < d && 2 * a * a < n );

Se observă că varianta cu do-while este ceva mai scurtă, deoarece nu repetă instrucţiunile care calculează valoarea lui b. Aceste cazuri, în care do-while este preferabilă lui while-do apar mai rar în practică.

Operații elementare pe vectori - continuare

Interclasare vectori (merge)

Dați doi vectori ordonați crescător construiți un al treilea vector ordonat crescător cu elementele din primii doi vectori. Sînt permise elemente duplicat.

O soluție ar fi să copiem toate elementele în cel de-al treilea vector și apoi să îl ordonăm. Există însă o soluție mai bună, bazată pe faptul că vectorii sînt deja ordonați. Să observăm că primul element din vectorul final este minimul dintre primele elemente din vectorii inițiali. Îl putem deci copia și apoi îl eliminăm din vectorul din care face parte. Apoi reluăm procedura. La un moment dat unul din vectori se va goli. În acel moment copiem ceea ce a rămas din vectorul nevid. Vom folosi trei indici i1, i2 și i3 care vor avansa în vectorii corespunzători, pe măsură ce selectăm elemente. Iată soluția:

// avem vectorii v1 de n1 elemente si v2 de n2 elemente
// vrem sa construim vectorul v3 de n1 + n2 elemente
i1 = 0;
i2 = 0;
i3 = 0;
while ( i1 < n1 && i2 < n2 ) { // mai avem elemente in ambii vectori?
  if ( v1[i1] < v2[i2] ) {     // daca v1 are elementul mai mic
    v3[i3] = v1[i1];           // il copiem
    i1++;                      // si avansam pe urmatorul element
  } else {                     // altfel v2 are elementul cel mai mic
    v3[i3] = v2[i2];           // il copiem
    i2++;                      // si avansam pe urmatorul element
  }
  i3++;                        // avansam si in vectorul v3
}
// in acest moment unul din vectorii v1, v2 este vid
while ( i1 < n1 ) { // incercam sa copiem elementele ramase in v1, daca exista
  v3[i3] = v1[i1];
  i1++;
  i3++;
}
while ( i2 < n2 ) { // incercam sa copiem elementele ramase in v2, daca exista
  v3[i3] = v2[i2];
  i2++;
  i3++;
}
n3 = n1 + n2;

O idee similară se folosește și la problema portofel, pe care o aveți ca temă.

Putere

Calculați an în mod cît mai eficient (a și n numere naturale). Problema este cunoscută şi sub numele de ridicare la putere în timp logaritmic. Ideea din spatele acestei rezolvări este următoarea:

  • Dacă n este par, atunci an = a2*n/2 = (a2)n/2
  • Dacă n este impar, atunci n-1 este par și avem an = a * an-1 = a * a2*(n-1)/2 = a * (a2)(n-1)/2 = a * (a2)n/2

În formulele de mai sus am considerat că / este împărțirea întreagă din limbajul C. De aceea atunci cînd n este impar (n-1)/2 este totuna cu n/2. Se observă că indiferent de paritatea lui n, la fiecare pas al iterației putem transforma a în a * a și apoi putem împărți n la 2. Doar în cazurile cînd n este impar vom acumula valoarea curentă a lui a la produsul calculat. Iată soluția bazată pe această idee:

#include <stdio.h>

int main() {
    int a, n;
    scanf("%d%d", &a, &n);

    int p = 1;
    while (n > 0) {
        if (n % 2 == 1)
            p = p * a;
        a = a * a;
        n = n / 2;
    }
    printf("%d", p);
}

Paranteze

Dată o secvență de 0 și 1, unde 0 înseamnă paranteză deschisă '(', iar 1 înseamnă paranteză închisă ')', spuneți dacă secvența reprezintă o expresie corectă de paranteze și dacă da calculați numărul maxim de paranteze una într-alta. Exemplu: 0 1 0 0 1 0 1 1 este corectă și are factorul de imbricare de 2, pe cînd secvența 0 0 0 1 1 1 0 este incorectă. Nu aveți voie să folosiți tablouri (vectori sau matrice).

Putem rezolva problema observînd următoarele reguli valabile pentru orice expresie corectă:

  • oriunde "rupem" expresia, în partea stîngă vom avea un număr de paranteze deschise mai mare sau egal cu cele închise
  • la final numărul de paranteze închise trebuie să fie egal cu cele închise

Dacă ambele condiții se îndeplinesc expresia e corectă. Prima condiție trebuie îndeplinită pentru fiecare poziție de rupere.

#include <stdio.h>

int main() {
  int n, a, i, sum, max;
  scanf("%d", &n);
  max = sum = i = 0;
  while ( i < n && sum >= 0 ) {
    if ( sum > max )
      max = sum;
    scanf( "%d", &a );
    if ( a == 0 )
      ++sum;
    else
      --sum;
    ++i;
  }
  if ( sum == 0 )
    printf("Parantezarea este corecta, avand factorul de imbricare %d", max);
  else
    printf("Parantezarea este incorecta");
}

Temă de gîndire pentru acasă: cum generalizăm? Avem paranteze rotunde, pătrate și acolade, aceeași cerință.

Temă

Tema 36: să se rezolve următoarele probleme (program C trimis la vianuarena):

  • puteri2 dată la olimpiada pe școală 2012, clasa a 8a
  • incalceala dată la olimpiada pe școală 2012, clasa a 7a
  • abc1 dată la olimpiada pe școală 2015, clasa a 9a
  • portofel dată la concursul Marele Premiu (PACO) 2013, clasa a 5a
  • împletire dată la olimpiada pe școală Tudor Vianu 2018, clasa a 9a

Rezolvări aici [1]