Clasa a V-a lecția 21 - 18 ian 2018

From Algopedia
Jump to navigationJump to search

Anunț

Uitați-vă vă rog 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 postată pe algopedia este mai bună. De multe ori rezolvarea voastră este ineficientă şi lungă, uneori 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 - rezolvări

Rezolvări aici [1]

Lecție

<html5media height="720" width="1280">https://www.algopedia.ro/video/2017-2018/2018-01-18-lectie-info-21-720p.mp4</html5media>

Vectori

Uneori avem nevoie să lucrăm cu multe variabile de același tip. De exemplu, la problema cifre comune am putea folosi zece variabile, a_0, a_1, ..., a_9, ce numără aparițiile respectivelor cifre în numărul a. Similar pentru b. Apoi am putea calcula numărul minim de apariții ale fiecărei cifre din a și b pe baza acestor variabile. Suma numărului minim de apariții este răspunsul la problemă. Unii din voi au şi rezolvat problema aşa, folosind 20 de variabile!

Cele zece variabile au ceva în comun: toate reprezintă valori de același tip, enumerate la rînd conform cifrelor. Această situație apare foarte des în algoritmi. De aceea a apărut conceptul de vector.

Definiție: vectorul este 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. El este totuna cu etajul zero. Etajul unu este următorul. De ce facem așa? Pentru că așa ne-am obișnuit. Americanii consideră parterul ca etajul unu, spre deosebire de noi. Deci nu există o regulă clară. 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. În cazul vectorilor există avantaje în a numerota elementele de la zero. Ele vor deveni evidente în următoarele lecții, este vorba despre parcurgerea circulara a vectorilor și alte relații matematice.

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] );

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 ş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 ajungem la poziția n, în afara vectorului. 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;
}

Căutarea unui element în vector după poziţia k

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( "cautarek.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 e, avansam i
  }

  if ( v[i] != e )                 // daca nu am gasit e, setam i pe n
    i = n;
  fout = fopen( "cautarek.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

Vectorul de frecvență al secvenței

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 culorile 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

Tema 21: să se rezolve următoarele probleme (program C trimis la vianuarena):

  • 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)
  • culori (să se afișeze o secvență de culori codificate cu numere mai mici ca 100 în ordinea lor crescătoare)

Rezolvări aici [2]