Bella at 14:00, 28 February 2018

2018-02-28T14:00:58Z

New page

= Tema - rezolvări =

= 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 <tt>n</tt>, <tt>e</tt> și <tt>k</tt> numere naturale, iar apoi se citesc <tt>n</tt> numere. Să se spună prima poziție după poziția <tt>k</tt> pe care apare elementul e. Dacă ajungem la ultima poziție, <tt>n-1</tt>, avem voie să începem din nou cu zero, deoarece se consideră că cele <tt>n</tt> numere sînt așezate în cerc. Dacă elementul <tt>e</tt> nu se află în vector vom afișa poziția <tt>n</tt> (în afara vectorului).

Soluție: vom citi cele <tt>n</tt> valori într-un vector, iar apoi vom porni de la poziția <tt>k</tt> și vom înainta fie pînă ce găsim elementul <tt>e</tt>, fie pînă cînd ajungem la poziția <tt>k</tt> din nou. Avansul indicelui <tt>i</tt> se va face modulo <tt>n</tt>. Iată soluția:

<syntaxhighlight>#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;
}</syntaxhighlight>

Observăm că pentru a începe din nou de la zero atunci cînd <tt>i</tt> devine <tt>n</tt> este deajuns să aplicăm funcția <tt>%n</tt> lui <tt>i</tt>. Acest lucru este posibil tocmai pentru că indicii vectorului <tt>v</tt> încep de la <tt>0</tt>.

<syntaxhighlight>
//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;
}</syntaxhighlight>

= Temă =
Rezolvați următoarele probleme:

* [http://varena.ro/problema/felinare felinare] dată la ONI 2008 clasa a 5-a
* [http://varena.ro/problema/culori1 culori1] dată la ONI 2012 clasa a 5-a
* [http://varena.ro/problema/panglica panglica] dată la ONI 2002 clasa a 5-a
* [http://varena.ro/problema/defrag defrag] dată la OJI 2015 clasa a 9-a : ( pentru superavansati - Parcurgere circulara a liniilor unei matrice )

Rezolvări aici [http://solpedia.francu.com/wiki/index.php/Clasa_a_V-a_lec%C8%9Bia_24_-_10_feb_2015]

Clasa a V-a lecția 6 S19 - Revision history

Bella at 14:00, 28 February 2018