Clasa a V-a lecția 42 - 24 mai 2018
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]