Clasa a V-a lecția 22 - 19 feb 2013
Anunț: uitați-vă pe rezolvările la teme postate pe acest site și comparați-le cu rezolvările voastre, încercînd să vă dați seama de diferențe și de ce sau dacă rezolvarea mea este mai bună. De multe ori rezolvarea voastră este ineficientă si lungă, de multe ori dublă sau triplă ca număr de linii. Nu postez aceste rezolvări pentru mine, ci pentru voi, pentru a putea învăța ceva. Chiar dacă ați rezolvat problemele trebuie să vă uitați și la rezolvările postate aici.
Tema – verificare
Am discutat soluțiile problemelor rude și vampiri. Rezolvări aici [1]
Lecție
Vectori
Uneori avem nevoie să lucrăm cu multe variabile de același tip. De exemplu, la problema cifre1 (vianuarena), unii dintre voi au simțit nevoia să folosească zece variabile, s0, s1, ..., s9, corespunzătoare numărului de apariții al respectivelor cifre într-un număr. Cele zece variabile au ceva în comun: toate reprezintă sume de același tip, enumerate la rînd conform cifrelor. Această situație apare foarte des în algoritmi. Astfel a apărut conceptul de vectori.
Definiție: vectorii sînt o colecție de valori de același tip (întreg, caracter, sau alte tipuri), valori ce pot fi accesate după un indice, sau poziție, care se mai cheamă și indicele în vector al acelei valori.
Exemplu:
În acest exemplu avem un vector v care conține n valori de tip întreg. Cele n valori pot fi accesate folosind indicele lor, sau poziția lor, de la 0 la n-1, înscrisă în desen sub fiecare din căsuțe. Elementul de pe poziția 2 este accesat ca v[2]. Așa cum la matematică scriem
v = v0, v1, v2, ..., vn-2, vn-1
în limbajul C scriem
v[0], v[1], v[2], ..., v[n-2], v[n-1]
În cazul nostru v[0] are valoarea 9, v[1] are valoarea 5, v[2] are valoarea 12, și așa mai departe.
Observație importantă: pozițiile, sau indicii elementelor încep de la zero, nu de la unu. Astfel, dacă avem un vector de 10 elemente, ele vor fi numerotate de la 0 la 9. Elementul v[10] nu există, deorece ar fi al 11-lea element.
De ce se întîmplă acest lucru? Nu ar fi mai natural ca primul element să fie elementul unu, și nu elementul zero? Răspunsul este nu. Gîndiți-vă că deși parterul este primul etaj nu îi spunem etajul unu, ci parter. Etajul unu este următorul. De ce facem așa? Pentru că așa ne-am obișnuit. Americanii consideră parterul ca etajul unu. Nu există o regulă. Cînd avem o secvență de elemente le putem numerota fie ca "al cîtelea element este", caz în care primul element va fi unu, fie ca "distanța lui față de începutul secvenței", caz în care primul element este zero.
O variabilă de tip vector stochează mai multe valori. De aceea tipul vector se mai numește și tip compus de date, prin opoziție cu tipurile simple de date pe care le-am învățat pînă acum, respectiv întreg și caracter, care stochează o singură valoare.
Declararea vectorilor
Ca orice variabilă C, vectorii trebuie declarați. Vectorul din exemplul de mai sus se declară astfel:
int v[100];
Numărul dintre parantezele pătrate reprezintă numărul de elemente (valori) al vectorului, iar int reprezintă tipul fiecărei valori. Să nu uităm că toate valorile unui vector trebuie să aibă același tip. Nu se poate ca v[1] să fie de tip int, iar v[2] de tip char. Nu uitați că ultimul element din acest vector este v[99], deoarece v[100] ar fi in afara vectorului.
În ce secțiune a programului C declarăm vectorii? În mod normal vectorii se declară împreună cu celelalte variabile la începutul programului C, imediat după main(). Dar noi vom face o excepție de la regulă și-i vom declara imediat înainte de main(), astfel:
#include <stdio.h>
int v[100];
int main() {
...
return 0;
}
Există două motive pentru aceasta:
- Vectorii ocupă mai multă memorie decît variabilele simple, ceea ce duce la probleme cu compilatoarele comisiei de corectură la olimpiada de informatică și alte concursuri. Veți înțelege mai multe pe măsură ce învățăm despre limbajul C.
- Variabilele declarate în afara lui main() sînt automat inițializate cu zero. De cele mai multe ori vrem ca toate elementele unui vector să fie la început zero. Această declarare ne scutește să mai scriem instrucțiuni speciale pentru aceasta.
Atribuirea vectorilor
Cum dăm valori unui vector? Fiecare element al vectorului este o variabilă separată, care poate fi atribuită, citită sau scrisă întocmai ca o variabilă de tipul vectorului. Exemple:
v[3] = 23; v[i] = v[i] + 1;
Citirea vectorilor
Citirea mai multor valori dintr-un fișier și introducerea lor într-un vector se face similar cu citirea unei secvențe: vom citi mai întîi numărul de elemente, n și apoi cele n elemente, de la 0 la n-1:
fscanf( fin, "%d", &n ); for ( i = 0; i < n; i++ ) fscanf( fin, "%d", &v[i] );
Acum înțelegeți de ce v-am cerut ca la citirea unei secvențe de numere să variați contorul de la 0 la n-1 și nu de la 1 la n: deoarece la citirea unui vector este important acest lucru și am vrut să vă obișnuiesc corect :-) Remarcați faptul că nu putem folosi o singură instrucțiune de citire pentru întregul vector. Valorile vectorului trebuie citite separat.
Afișarea vectorilor
Afișarea valorilor vectorului este similară cu citirea. Vom scrie în fișierul de ieșire fiecare valoare, pe rînd:
for ( i = 0; i < n; i++ ) fprintf( fout, "%d ", v[i] );
Inițializarea vectorilor
Precum am văzut dacă declarăm vectorii deasupra lui main() ei vor fi automat inițializați cu zero. Cum procedăm dacă avem nevoie ca valorile vectorului să fie inițializate cu o altă valoare? Iată un exemplu care inițializează toate valorile vectorului v cu 1:
for ( i = 0; i < n; i++ ) v[i] = 1;
Maximul dintr-un vector
Exercițiu: să se citească un vector de n elemente și să se afișeze valoarea maximă din acest vector. Precum știm, nu avem nevoie să folosim un vector pentru această problemă. O vom face pentru a ne obișnui cu vectorii. Iată soluția:
#include <stdio.h>
int v[100];
int main() {
FILE *fin, *fout;
int n, i, max;
fin = fopen( "maxim.in", "r" );
fscanf( fin, "%d", &n );
for ( i = 0; i < n; i++ )
fscanf( fin, "%d", &v[i] );
fclose( fin );
max = v[0];
for ( i = 1; i < n; i++ )
if ( max < v[i] )
max = v[i];
fout = fopen( "maxim.out", "w" );
fprintf( fout, "%d", max );
fclose( fout );
return 0;
}
Suma elementelor unui vector
Exercițiu: să se citească un vector de n elemente și să se afișeze suma elementelor lui. La fel, nu avem nevoie de vector, dar îl vom folosi pentru a ne obișnui. Iată soluția:
#include <stdio.h>
int v[100];
int main() {
FILE *fin, *fout;
int n, i, sum;
fin = fopen( "suma.in", "r" );
fscanf( fin, "%d", &n );
for ( i = 0; i < n; i++ )
fscanf( fin, "%d", &v[i] );
fclose( fin );
sum = 0;
for ( i = 0; i < n; i++ )
sum = sum + v[i];
fout = fopen( "suma.out", "w" );
fprintf( fout, "%d", sum );
fclose( fout );
return 0;
}
Căutarea unui element în vector
Exercițiu: se citesc n, e și k numere naturale, iar apoi se citesc n numere. Să se spună prima poziție după poziția k pe care apare elementul e. Dacă ajungem la ultima poziție, n-1, avem voie să începem din nou cu zero, deoarece se consideră că cele n numere sînt așezate în cerc. Dacă elementul e nu se află în vector vom afișa poziția n (în afara vectorului).
Soluție: vom citi cele n valori într-un vector, iar apoi vom porni de la poziția k și vom înainta fie pînă ce găsim elementul e, fie pînă cînd ajungem la poziția k din nou. Avansul indicelui i se va face modulo n. Iată soluția:
#include <stdio.h>
int v[100];
int main() {
FILE *fin, *fout;
int n, i, e, k;
fin = fopen( "poz.in", "r" );
fscanf( fin, "%d%d%d", &n, &e, &k );
for ( i = 0; i < n; i++ )
fscanf( fin, "%d", &v[i] );
fclose( fin );
i = k;
if ( v[i] != e ) { // daca pe pozitia k nu avem e
i = (i + 1) % n; // avansam indicele i
while ( i != k && v[i] != e ) // cita vreme nu ne-am intors la k
i = (i + 1) % n; // si v[i] diferit de k, avansam i
}
if ( v[i] != e ) // daca nu am gasit e, setam i pe n
i = n;
fout = fopen( "poz.out", "w" );
fprintf( fout, "%d", i );
fclose( fout );
return 0;
}
Observăm că pentru a începe din nou de la zero atunci cînd i devine n este deajuns să aplicăm funcția %n lui i. Acest lucru este posibil tocmai pentru că indicii vectorului v încep de la 0.
Vectori de frecvență (vectori caracteristici)
Vectorii de frecvență sînt vectori ale căror elemente au o semnificație specială: valoarea de pe poziția i arată numărul de apariții (sau frecvența) lui i într-o altă entitate, de obicei o secvență de numere, sau un număr. De exemplu, dacă avem o secvență de 10 numere cuprinse între 0 și 4 putem construi un vector de 5 elemente în care v[i] reprezintă numărul de apariții ale numărului i în secvența originală. Exemplu:
Fie secvența
3 2 0 3 4 1 2 0 2 2
Atunci vectorul ei de frecvență, sau vectorul caracteristic este
v[0] este 2 deoarece 0 apare de două ori în secvența originală, v[1] este 1 deoarece 1 apare o dată, 2 apare de 4 ori, 3 apare de 2 ori și 4 apare o dată. Observați că suma elementelor vectorului a este egală cu numărul de numere din secvența originală.
Exemplu: numărul maxim de apariții al unei culori într-o secvență
Se citește la intrare un număr n și apoi n culori. Cele n culori sînt codificate cu numere între 0 și 14. Să se afișeze în ordine crescătoare toate culorile care apar de cele mai multe ori în secvență.
Exemplu: pentru secvența
22 4 2 9 8 2 5 8 10 14 12 14 6 12 14 8 3 7 2 0 13 14 8
Vom afișa:
8 14
deoarece culorile 8 și 14 apar de 4 ori în secvență, iar toate celelalte culori apar de mai puține ori.
Rezolvare: vom crea un vector caracteristic a de 15 elemente, inițializat cu zero. Apoi vom citi rînd pe rînd culorile, în variabila c, adunînd 1 la a[c]. În final a[c] va conține numărul de apariții ale culorii c. Pentru a afla culoarile care apar de cele mai multe ori vom căuta maximul în acest vector, apoi, la o a doua parcurgere vom afișa toate pozițiile pe care a[i] este maxim. Iată soluția:
#include <stdio.h>
int a[15];
int main() {
FILE *fin, *fout;
int n, i, c, max;
// citim secventa de culori si construim vectorul de frecventa
fin = fopen( "culori.in", "r" );
fscanf( fin, "%d", &n );
for ( i = 0; i < n; i++ ) {
fscanf( fin, "%d", &c );
a[c]++;
}
fclose( fin );
// cautam maximul in vectorul de frecventa
max = a[0];
for ( c = 1; c < 15; c++ )
if ( a[c] > max )
max = a[c];
// afisam toate pozitiile c pentru care a[c] == max
fout = fopen( "culori.out", "w" );
for ( c = 0; c < 15; c++ )
if ( a[c] == max )
fprintf( fout, "%d ", c );
fclose( fout );
return 0;
}
Tema
Începeți să rezolvați din următoarea listă de probleme la vianuarena. Nu trebuie să le rezolvați pînă mîine! Aceasta este o listă de lucru cu probleme pe care le vom relua mîine, iar ceea ce nu terminăm vă vor rămîne ca temă pentru marți.
Probleme și exerciții
- cfdist (numărul de elemente al mulțimii cifrelor unui număr)
- maxnr (cel mai mare număr care se poate forma cu cifrele unui număr)
- minnr (cel mai mic număr care se poate forma cu cifrele unui număr)
- cfcomune (numărul de cifre comune distincte a două numere). Bonus: încercați să o rezolvați folosind un singur vector de zece elemente binare (aveți voie să stocați doar zero sau unu în acel vector)
- cifre1 (rezolvată cu vectori de frecvență de data aceasta)
- culori (să se afișeze o secvență de culori codificate cu numere mai mici ca 100 în ordinea lor crescătoare)
- minnrk (cel mai mic număr care se poate forma cu k din cifrele n)
Rezolvări aici [2]
