Clasa a V-a lecția 42 - 24 mai 2018

From Algopedia
Jump to navigationJump to search

Tema - rezolvări

Rezolvări aici [1]

Lecție

<html5media height="720" width="1280">https://www.algopedia.ro/video/2017-2018/2018-05-24-lectie-info-42-720p.mp4</html5media>Vom discuta despre unele probleme clasice.

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 42: 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

Rezolvări aici [2]