Clasa a V-a lecția 26 - 15 feb 2018

From Algopedia
Jump to navigationJump to search

Anunț

Duminică 18 februarie orele 15:30-18:30 voi organiza un nou concurs de pregătire pentru olimpiada locală la varena. Vă rog să faceți efortul să participați.

Tema - rezolvări

Rezolvări aici [1]

Lecție

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

În continuare vom discuta rezolvări ale unor probleme clasice cu vectori.

Căutare în vector

Se dă un vector v de n elemente și un extra element e. Să se găsească poziția p în v unde apare prima oară elementul e. Dacă elementul e nu apare p va avea valoarea n. O soluție elegantă care nu iese forțat din buclă și care nu folosește stegulețe este:

// avem vectorul v de n elemente si o valoare e de gasit in acest vector
p = 0;
while ( p < n && v[p] != e )
  p++;
// acum p este fie pozitia primei aparitii a lui e, fie n daca e nu exista in v

Inserare în vector

Se dă un vector v de n elemente, un extra element e și o poziție p. Să se insereze elementul e la poziția p. În final elementul e va fi pe poziția p în vector, iar elementele de la poziția p pînă la final vor fi deplasate spre final cu o poziție. Vom considera că p este o poziție validă, între 0 și n.

// avem vectorul v de n elemente si o valoare e de inserat la poziția p
for ( i = n - 1; i >= p; i-- ) // deplasăm elementele spre dreapta
  v[i+1] = v[i];
v[p] = e;
n++; // vectorul are acum n+1 elemente!

Ștergere din vector

Se dă un vector v de n elemente și o poziție p. Să se elimine elementul de la poziția p din vector. Elementele de la poziția p pînă la final se vor deplasa către începutul vectorului cu o poziție.

// avem vectorul v de n elemente si o poziție p ce trebuie eliminata
for ( i = p + 1; i < n; i++ ) // deplasam elementele spre stinga
  v[i-1] = v[i];
n--; // vectorul are acum n-1 elemente!

Răsturnare vector

Se dă un vector v de n elemente. Inversați poziția elementelor în vector. Avem mai multe soluții posibile, una foarte simplă este să folosim doi indici, unul care crește și unul care descrește. Vom interschimba elementele celor doi indici. Vom repeta acest lucru pînă ce indicii se întîlnesc.

// avem vectorul v de n elemente, vrem sa il rasturnam
i = 0;
j = n – 1;
while ( i < j ) {
  aux = v[i];
  v[i] = v[j];
  v[j] = aux;
  i++;
  j--;
}

Rotire vector

Se dă un vector v de n elemente. Să se rotească vectorul cu o poziție către început cu o poziție. De exemplu [1, 6, 2, 7, 4, 3, 2] se va transforma în [6, 2, 7, 4, 3, 2, 1].

// avem vectorul v de n elemente, vrem sa il rotim la stinga cu o pozitie
aux = v[0];
for ( i = 1; i < n; i++ )
  v[i-1] = v[i];
v[n-1] = aux;

Mutare zerouri la coadă

Se dă un vector v de n elemente. Să se modifice ordinea elementelor în vector astfel încît toate elementele zero să fie la coada vectorului. Celelalte elemente nu trebuie să își păstreze ordinea originală (pot fi în orice ordine). O soluție posibilă este să mergem cu doi indici, unul crescător și unul descrescător. Cel crescător avansează pînă ce găsește un zero. Apoi interschimbă cu celălalt indice, pe care îl scade.

// avem vectorul v de n elemente, vrem sa mutăm zerourile la coada
i = 0;
j = n – 1;
while ( i < j ) {
  if ( v[i] == 0 ) { // daca avem un zero pe pozitia i
    v[i] = v[j];     // il trecem la coada, interschimbind cu pozitia j
    v[j] = 0;
    j--;             // deoarece pe pozitia j avem un zero, putem sa scadem j
  } else
    i++;             // daca avem nonzero pe pozitia i putem avansa i
}

Comparație vectori

Dați doi vectori de caractere să se spună care este ordinea lor lexicografică. Cu alte cuvinte, ordinea în care vor apărea cele două cuvinte în dicționar.

Rămîne ca temă.

Rotire multiplă de vector *

Se dă un vector v de n elemente și un număr k. Să se rotească vectorul cu o poziție către început cu k poziții. De exemplu, pentru k=3 [1, 6, 2, 7, 4, 3, 2] se va transforma în [7, 4, 3, 2, 1, 6, 2].

Rămîne ca temă pentru cei dornici să se lupte cu o problemă grea.

Temă

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

  • compus problemă de exersat operațiile clasice pe vectori
  • felinare dată la ONI 2008 clasa a 5a
  • culori 1 dată la ONI 2012 clasa a 5a

Opțional, teme de gîndire:

  • Comparația a doi vectori: dați doi vectori, v de lungime m și w de lungime n să se spună dacă v este mai mic, egal, sau mai mare decît w. Gîndiți-vă cum ați face această problemă și încercați să scrieți o bucată de program C care să o rezolve.
  • Grea: rotk (rotație multiplă vector fără a face rotații repetate cu unu).

Rezolvări aici [2]