Clasa a V-a lecția 39 - 26 mai 2015

Tema - rezolvări

Rezolvări aici [1]

Lecție

Vom discuta despre unele probleme clasice, cu sau fără vectori.

Putere

Calculați aⁿ î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 aⁿ = a^2*n/2 = (a²)^n/2
• Dacă n este impar, atunci n-1 este par și avem aⁿ = a * a^n-1 = a * a^2*(n-1)/2 = a * (a²)^(n-1)/2 = a * (a²)^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);
}

Secvență monotonă

Spuneți dacă o secvență de numere este monotonă. O secvență este monotonă dacă numerele ei sînt fie în ordine crescătoare fie în ordine descrescătoare. Secvența are cel puțin două numere. Nu aveți voie să folosiți tablouri (vectori sau matrice).

#include <stdio.h>

int main() {
  int n, a, b, i, cresc, monoton;
  scanf( "%d%d%d", &n, &a, &b );
  i = 2;
  // Ignoram toate elemente egale de la inceput, pentru a stabili monotonia sirului
  while (i < n && a == b) {
    a = b;
    scanf("%d", &b);
    ++i;
  }
  // Daca toate numerele sunt egale, secventa este monotona
  if (i == n) {
    printf("DA");
  } else {
    // Daca sirul tinde crescator, cresc = 1; Altfel, cresc = 0.
    if (a < b)
      cresc = 1;
    else
      cresc = 0;
    // Retinem monotonia initiala
    monoton = cresc;
    // Cat timp nu am terminat de parcurs sirul si este pastrata monotonia initiala
    while (i < n && monoton == cresc) {
      a = b;
      scanf("%d", &b);
      if (a < b)
        cresc = 1;
      else if (a > b)
        cresc = 0;
      ++i;
    }
    if (monoton == cresc)
      printf("DA");
    else
      printf("NU");
  }
  return 0;
}

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ă

Lucraţi la jocul Gold.