Clasa a V-a lecția 34 - 11 apr 2020

From Algopedia
Revision as of 17:06, 9 February 2021 by Mihai (talk | contribs) (→‎Concurs - rezolvări)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigationJump to search

Lecție

Nu există video. Lecția este doar teoretică și disponibilă online.

Vector mulțime

Se dă un vector v de n elemente. Să se transforme într-un vector mulțime. Cu alte cuvinte, să se elimine duplicatele din vector. Un vector mulțime este un vector în care orice element apare o singură dată.

Avem mai multe soluții posibile. O primă soluție se bazează pe vectori de frecvență. Putem construi un vector de apariții ale elementelor din v. Apoi vom colecta elementele din vectorul de apariții înapoi in v. Această soluție funcționează pentru valori relativ mici ale elementelor din v.

Dacă valorile din v sînt prea mari pentru a folosi un vector de frecvență, atunci putem să verificăm fiecare element din vector și să îl copiem în alt vector, w, numai dacă el nu apare deja în vectorul w. Iată această soluție:

// avem vectorul v de n elemente, vrem sa il transformam in vector multime
m = 0; // numarul de elemente al vectorului w
for ( i = 0; i < n; i++ ) { // fiecare element din v va fi cautat in w
  j = 0;
  while ( j < m && w[j] != v[i] )
    j++;
  if ( j == m ) { // daca elementul v[i] nu exista in vectorul w, il adaugam
    w[m] = v[i];
    m++;
  }
}

Observație importantă: vectorul w are întotdeauna lungime mai mică sau cel mult egală cu vectorul v.

De aceea putem să nu folosim un vector diferit w, ci să lucrăm chiar pe vectorul v! Codul este identic cu cel de mai sus, înlocuind w cu v:

// avem vectorul v de n elemente, vrem sa il transformam in vector multime
m = 0; // numarul de elemente al vectorului multime
for ( i = 0; i < n; i++ ) { // fiecare element din v va fi cautat in multime
  j = 0;
  while ( j < m && v[j] != v[i] )
    j++;
  if ( j == m ) { // daca elementul v[i] nu exista in multime, il adaugam
    v[m] = v[i];
    m++;
  }
}
// in final vectorul v de lungime m contine multimea vectorului original

Căutare subvector în vector

Dați doi vectori, p (vectorul de căutat) și v (vectorul în care se caută) să se spună de cîte ori apare vectorul p în v. De exemplu dacă p = [1, 2, 1] și v = [1, 2, 1, 2, 1, 3, 1, 2, 1] atunci p apare de 3 ori in v.

Să observăm că aparițiile vectorului p în vectorul v pot fi suprapuse, ca în exemplul de mai sus. Un algoritm direct este să încercăm toate pozițiile de suprapunere ale vectorului p peste vectorul v și să testăm dacă toate elementele din p se potrivesc cu cele din v:

   1, 2, 1, 2, 1, 3, 1, 2, 1
0: 1, 2, 1
1:    1, 2, 1
2:       1, 2, 1
3:          1, 2, 1
4:             1, 2, 1
5:                1, 2, 1
6:                   1, 2, 1

Suprapunînd vectorul p peste v observăm că avem potriviri la pozițiile 0, 2 și 6. Iată programul pentru această metodă:

// avem vectorul v de n elemente si vectorul de cautat p, de m elemente
nr = 0;                                // numarul de aparitii este initial zero
for ( poz = 0; poz < n – m + 1; poz++ ) {   // pentru fiecare pozitie posibila
  i = 0;
  while ( i < m && p[i] == v[poz + i] ) // ne oprim la prima inegalitate
    i++;
  if ( i == m )                         // daca toate elementele au fost egale
    nr++;                               // am mai gasit o aparitie a lui p in v
}
// acum nr contine numarul de aparitii ale lui p in v

Vom vedea în anii următori că există și algoritmi mai eficienți pentru rezolvarea acestei probleme.

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.

Un vector v1 este lexicografic mai mic decît alt vector v2 dacă v1 și v2 sînt egale de la 0 la i-1, iar poziția i este fie în afara vectorului v1, fie v1[i] < v2[i]. Vom compara elementele vectorilor pe aceleași poziții cîtă vreme sînt egale, oprindu-ne la prima diferență, sau cînd unul din vectori se termină. Acolo vom decide care din vectori este mai mic.

Iată programul:

// avem vectorii v1 de n1 elemente si v2 de n2 elemente
i = 0;
while ( i < n1 && i < n2 && v1[i] == v2[i] ) // cita vreme avem egalitate
  i++;                                       // avansam i
// pentru ca v1 sa fie primul in ordine lexicografica trebuie ca
// fie i sa fi depasit ultimul element din v1, fie ca v1[i] < v2[i]
// pentru a doua conditie e nevoie ca v2 sa aiba ceva pe pozitia i
if ( i == n1 || (i < n2 && v1[i] < v2[i]) )
  m = 0;
else
  m = 1;

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].

O soluție ar putea fi să rotim vectorul cîte o poziție de k ori. Această soluție face multe deplasări, respectiv k∙n. Un algoritm mai bun este următorul:

  1. Răstoarnă vectorul v.
  2. Răstoarnă subvectorul v[0..n-k-1]
  3. Răstoarnă subvectorul v[n-k..n-1]

De ce funcționează acest algoritm?

Care este numărul de deplasări ale acestui algoritm? Demonstrați că este 3∙n.

Sortarea prin selecție (select sort)

Se dă un vector de n elemente. Să se sorteze prin metoda selecției. Prin sortare înțelegem ordonare crescătoare a elementelor vectorului. Metoda selecției este următoarea: vom găsi maximul din vector, împreună cu poziția sa. Apoi vom interschimba maximul cu ultimul element din vector. Astfel ne vom asigura că ultimul element este chiar cel corect în vectorul ordonat. Ne-a rămas astfel un vector cu n-1 elemente, care trebuie sortat. Vom proceda la fel: vom găsi maximul în subvectorul de n-1 elemente, precum și poziția lui, și-l vom muta la coadă, rezultînd un vector de n-2 elemente. Continuăm procedura pînă ce vectorul este sortat.

Iată o exemplificare grafică:

9 2 8 3 6 5 3 9 6 |
6 2 8 3 6 5 3 9 | 9
6 2 8 3 6 5 3 | 9 9
6 2 3 3 6 5 | 8 9 9
5 2 3 3 6 | 6 8 9 9
5 2 3 3 | 6 6 8 9 9
3 2 3 | 5 6 6 8 9 9
3 2 | 3 5 6 6 8 9 9
2 | 3 3 5 6 6 8 9 9
| 2 3 3 5 6 6 8 9 9

Iată programul:

// avem vectorul v de n elemente
for ( u = n – 1; u > 0; u-- ) { // pozitia ultimului element din subvector
  max = v[0];
  p = 0;                        // p este poziția maximului
  for ( i = 1; i <= u; i++ )
    if ( v[i] > max ) {         // memoram noul maxim si pozitia lui
      max = v[i];
      p = i;
    }
  // interschimbam maximul de pe pozitia p cu ultimul element, pe pozitia u
  v[p] = v[u];
  v[u] = max;
}

Vă recomand folosirea algoritmului de sortare prin selecție și nu a sortării cu bule, deoarece face mai puține operații. În practică el este de cinci pînă la zece ori mai rapid. Desigur, și mai rapidă este sortarea prin vectori de frecvență, numită și sortare prin numărare, atunci cînd ea poate fi aplicată (cînd numerele sînt foarte mici).

Temă

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

  • siruri1 dată la OJI 2004 clasa a 7a
  • case1 dată la ONI 2009 clasa a 5a
  • arme dată la OJI 2012 clasa a 7a, ca aplicație a sortării prin selecție

Rezolvări aici [1]