Clasa a V-a lecția 6 S19

Lecție

Parcurgerea circulara a unui vector. Pana acum am folosit vectorii pentru a memora elementele ce se afla intr-un sir liniar, precum un sir de numere. Exista si situatii in care trebuie sa memoram date pentru elemente ce se afla intr-un cerc, ceea ce inseamna ca, daca ne-am imagina un prim element din cercul respectiv, ultimul element ar fi vecin cu acesta. Pentru a memora astfel de date, vom folosi tot un vector ca pana acum, insa va trebui sa tinem const ca ultimul element, v[n-1] este vecin cu primul element, v[0].

Parcurgerea unui vector circular

Presupunem ca avem n copii intr-un cerc si ca dorim sa aflam care este al k-lea copil, incepand numaratoarea de la primul copil, unde poate fi si mai mare decat n. - varianta simulare, pas cu pas - varianta cu k%n

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.

//VARIANTA ISA
#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;
  while ( i < n + k && v[i % n] != e )  // cita vreme nu am parcurs toate cele n elemente
      i++;                              // 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;
}

Temă

Rezolvați următoarele probleme:

• felinare dată la ONI 2008 clasa a 5-a
• culori1 dată la ONI 2012 clasa a 5-a
• panglica dată la ONI 2002 clasa a 5-a
• defrag dată la OJI 2015 clasa a 9-a : ( pentru superavansati - Parcurgere circulara a liniilor unei matrice )

Rezolvări aici [1]