Clasa a IX-a lecția 19

From Algopedia
Jump to: navigation, search

Teorie

Vectori

Uneori avem nevoie să lucrăm cu multe variabile de același tip. De exemplu, la problema cifre 3 am putea folosi zece variabile, a_0, a_1, ..., a_9, aparițiilor respectivelor cifre în numărul a. Similar pentru b. Apoi am putea facel calculul care cifre apar în a şi nu apar în b pe baza acestor variabile. Cele zece variabile au ceva în comun: toate reprezintă sume de același tip, enumerate la rînd conform cifrelor. Unii din voi au şi rezolvat-o aşa. 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:

Exemplu de vector cu n elemente

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

  1. 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.
  2. 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] );

// Varianta C++

fin>>n;
for ( i = 0; i < n; i++ )
  fin>>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;

Dar daca dorim sa initializam un vector cu alte valori?

int v[4] = {1,2,3,4};

Aici am initializat un vector cu 4 elemente. Aceasta initializare este echivalenta cu urmatoarele atribuiri: v[0] = 1, v[1] = 2, v[2] = 3, v[3] = 4

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 şi e numere naturale, iar apoi se citesc n numere. Să se spună prima poziție pe care apare elementul e. 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 0 și vom înainta fie pînă ce găsim elementul e, fie pînă cînd iesim din vector, adica cand ajungem pe pozitia n. Iată soluția:

#include <stdio.h>

int v[100];

int main() {
  FILE *fin, *fout;
  int n, i, e;

  fin = fopen( "cautare.in", "r" );
  fscanf( fin, "%d%d", &n, &e );
  for ( i = 0; i < n; i++ )
    fscanf( fin, "%d", &v[i] );
  fclose( fin );

  i = 0;
  while ( i < n && v[i] != e ) // cita vreme sintem inca in vector
      i++;                     // si nu l-am gasit pe e, avansam i

  fout = fopen( "cautare.out", "w" );
  fprintf( fout, "%d", i );
  fclose( fout );

  return 0;
}

Parcurgerea vectorilor

Pentru a prelucra toate elementele unui vector, in problemele de mai sus am parcurs aceste elemente incepând de la primul element, aflat pe prima poziţie v[0], pana la ultimul element, v[n-1], folosind o structura repetitiva cu numar cunoscut de pasi de tip for ( vezi algoritmul care calculeaza suma tuturor elementelor. Pentru a gasi insa un element in vector, am parcurs elementele pornind de la elementul v[0] si am continuat cautarea cata vreme nu am gasit elementul cautat. Astfel ca parcurgerea cauarea a fost intrerupta in momentul in care am gasit elementul cautat. Structura repetitiva in acest caz, a fost o structura repetitiva cu numar necunoscut de pasi, conditionata de gasirea sau nu a elementului cautat.

In funcţie de cerinţa problemei, parcurgea elementelor poate fi facută diferit:

Parcurgea in ordine inversa a elementelor

 for ( i = n - 1; i >= 0; i-- )
   cout<< v[i] << " ";

Parcurgea elementelor de pe pozitii impare/ pare

 // Elementele de pe pozitii impare
 // pornim de la primul element, la noi acesta este pe pozitia 0
 for ( i = 0; i < n; i = i + 2 )
   cout<< v[i] << " ";
// Elementele de pe pozitii pare
 // pornim de la al doilea element, la noi acesta este pe pozitia 1
 for ( i = 1; i < n; i = i + 2 )
   cout<< v[i] << " ";

Aplicatii laborator

Probleme usoare

Paritate1: Se dă un șir cu n elemente, numere naturale. Determinați diferența în valoare absolută dintre numărul de valori pare din șir și numărul de valori impare din șir. R: problema nu necesita memorarea datelor intr-un vector.

Afisare0: Se citește un vector cu n elemente, numere naturale. Să se afișeze elementele din vector care sunt multipli ai ultimului element.

Afisare: Se citește un vector cu n elemente, numere naturale. Să se afișeze elementele cu indici pari în ordinea crescătoare a indicilor, iar elementele cu indici impari în ordinea descrescătoare a indicilor.

Afisare1 Se citește un vector cu n elemente, numere naturale. Să se afișeze elementele vectorului în următoarea ordine: primul, ultimul, al doilea, penultimul, etc.

MinMax0 Să se determine maximul şi minimul valorilor elementelor unui vector.

PozMinMax Să se determine indicele maximului şi cel al minimului valorilor elementelor unui vector.

Numarare6: Se citește un vector cu n elemente, numere naturale. Să se determine câte elemente ale vectorului sunt egale cu diferența dintre cea mai mare și cea mai mică valoare din vector.

AfisareMinMax: Se citește un vector cu n elemente, numere naturale distincte. Să se afișeze elementele cuprinse între elementul cu valoarea minimă și cel cu valoare maximă din vector, inclusiv acestea.

Suma2: Se citește un vector cu n elemente, numere naturale. Să se determine suma valorilor elementelor cuprinse între primul și ultimul element par al vectorului, inclusiv acestea.

Numarare2: Se dă un vector cu n numere naturale. Să se determine câte dintre elemente au valoarea strict mai mare decât media aritmetică a elementelor vectorului.

Probleme medii

  • mcub Problema nu necesita neaparat memorarare datelor intr-un vector, solutia optima necesitand parcurgea elementelor o singura data.

Probleme dificile

Tema

De pe pbinfo rezolvati uramtoarele probleme : NumarMunte , Triunghiuri , UEMM , Zone , PozitieX , Unice1

Probleme de concurs