Clasa a VI-a lecția 2 - 25 sep 2013
Tema - rezolvări
Discuție despre temă, cu analiza complexității timpului:
Rezolvări aici [1].
Învățăminte
- Declararea vectorilor cu inițializare, ca în rezolvarea problemei anterioare.
- Dimensiunile diverselor tipuri: în code::blocks int are 4 octeți, long long are 8 octeți.
- Estimarea numărului care încape pe un număr dat de biți folosind formula 210 ≈ 103
Rezolvări aici [2]
Lecție
Recapitulare cunoștințe informatică
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ță.
Interclasare vectori (merge)
Dați doi vectori sortați crescător construiți un al treilea vector sortat care să conțină toate elementele din cei doi vectori. Sînt permise elemente duplicat. Exemplu: dați vectorii 1 4 6 9 și 2 4 5 9 12 rezultatul este vectorul 1 2 4 4 5 6 9 9 12. Nu aveți voie să folosiți funcții de sortare din biblioteca C sau Pascal.
Am mai discutat despre această problemă anul trecut. 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 sigur vid, posibil amindoi
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++;
}
n = n1 + n2;
Ștergere element
Dat un vector v și un element e să se elimine din vector prima apariție a elementului e, în caz că acesta apare în vector. Exemplu: v = 5 9 2 7 9 3 5 7 4 si e = 9, la final v = 5 2 7 9 3 5 7 4
Soluție incorectă
O soluție foarte populară este să căutăm elementul în vector și, în momentul cînd îl găsim să-l ștergem:
for ( i = 0; i < n; i++ )
if ( v[i] == e ) {
for ( j = i + 1; j < n; j++ )
v[j-1] = v[j];
i = n;
}
Aceasta este o soluție urîtă deoarece:
- folosește for pentru un ciclu cu număr necunoscut de pași
- modifică variabila de ciclu, i
- nu folosește "cărămizile" învățate deja și anume căutarea unui element în vector și ștergerea unui element din vector
Soluție corectă
Ștergerea unui element din vector se face astfel:
- Vom avea două etape: căutare element în vector + eliminarea propriu zisă.
- În final numărul de elemente n se micșorează cu unu.
Iată implementarea corectă:
i = 0;
while ( i < n && v[i] != e )
i++;
if ( i < n ) {
for ( j = i + 1; j < n; j++ )
v[j-1] = v[j];
n--;
}
Recapitulare reguli de programare
- Variabilele simple nu se inițializează la declarare. Ele se inițializează cît mai aproape de secțiunea de program care le folosește. Cu alte cuvinte orice variabilă se inițializează cît mai jos posibil. De ce? Pentru citibilitatea codului. Imaginați-vă că la linia 300 vedem o instrucțiune a = a + y;. Ne punem întrebarea cu ce valoare a fost inițializată a. Imaginați-vă că trebuie să mergem cîteva pagini în sus pentru a constata că variabila a fost inițializată la declarare int a = 1;
- Vectorii încep de la 0, nu de la 1. Este o regulă importantă, nu o preferință personală. Avantaje: cînd folosim modulo, vectori caracteristici, etc.
- Reguli de indentare, exemple:
- Indentarea se face la două sau la patru spații. Două sînt suficiente pentru citibilitate. Atenție: setați code::blocks să nu folosească caractere TAB.
- Acolada deschisă se pune pe același rînd cu instrucțiunea precedentă.
- Acolada închisă se pune pe rîndul următor aliniată sub instrucțiunea de care aparține.
- Dacă după else urmează un if atunci if-ul se pune imediat după else pe aceeași linie, iar corpul de instrucțiuni aparținînd lui else se indentează cu două spații, nu cu patru. Astfel, în cazul unor instrucțiuni de genul if ... else if ... else if ... se evită migrarea codului către dreapta prin indentări inutile.
- Fără break/continue/return/goto în interiorul buclelor. Ele distrug programarea structurată și, implicit, zeci de ani de experiență ai omenirii.
- Folosim for pentru bucle cu număr cunoscut de pași, while în celelalte cazuri. Aceasta este o regulă de programare ordonată, care face codul mai citibil.
- Nu avem voie să modificăm variabila de buclă for. Dacă este un ciclu cu număr cunoscut de pași nu avem de ce să modificăm variabila.
- Cînd eliminăm un element din vector scădem lungimea lui (n--). În felul acesta n continuă să arate numărul de elemente din vector.
Constante in C
Constante în C: #define. Atunci cînd o constantă apare des în program este bine să îi dăm un nume cu #define. În felul acesta programul devine mai citibil, iar în cazul unei modificări ulterioare a constantei putem modifica într-un singur loc. Un mod special de a folosi constantele este la debug: cît timp facem corecții la program putem defini o constantă care să "activeze" instrucțiuni de tipărire de debug:
#define D 1 ... if ( D ) printf( "x=%d y=%d a=%d\n", x, y, a ) ...
La final, cînd considerăm că programul este corect tot ce avem de făcut este să modificăm constanta D în zero:
#define D 0
Observați folosirea lui 0 și 1 ca valori adevărat, respectiv fals.
Instrucțiunea switch
Despre instrucțiunea switch.
Tema
- Numărare: se dă un fișier care conține un șir de caractere. Caracterele permise sînt litere mici, cifre, spațiu, tab (\t) și linie nouă (\n). Să se numere cîte cuvinte și cîte numere se află în fișier. Exemple:
- 'abc123abc53zx' conține cuvintele abc abc zx și numerele 123 53
- 'asd 1 bx 120020ccc' conține cuvintele asd bx ccc și numerele 1 120020
- Fracție: date numerele naturale a și b, a < b, b diferit de zero, să se afișeze fracția a / b în notație zecimală cu virgulă și perioadă. Algoritmul folosit trebuie să aibă complexitate proporțională cu numărul de cifre afișate. Atenție: dacă veți folosi un vector pentru a memora resturile parțiale veți ajunge la o complexitate pătratică, nu liniară, așa încît nu folosiți vectori.
Soluții aici [3]
