Clasa a V-a lecția 42 - 28 mai 2013
Tema - verificare
Discuție despre compus și prime. Restul le vom discuta mai jos.
Lecție
Exerciții cu vectori (continuare)
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; 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:
- Răstoarnă vectorul v.
- Răstoarnă subvectorul v[0..n-k-1]
- 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.
Interclasare vectori (merge)
Dați doi vectori ordonați crescător construiți un al treilea vector ordonat crescător cu elementele din primii doi vectori. Sînt permise elemente duplicat.
O soluție ar fi să copiem toate elementele în cel de-al treilea vector și apoi să îl ordonăm. Există însă o soluție mai bună, bazată pe faptul că vectorii sînt deja ordonați. Să observăm că primul element din vectorul final este minimul dintre primele elemente din vectorii inițiali. Îl putem deci copia și apoi îl eliminăm din vectorul din care face parte. Apoi reluăm procedura. La un moment dat unul din vectori se va goli. În acel moment copiem ceea ce a rămas din vectorul nevid. Vom folosi trei indici i1, i2 și i3 care vor avansa în vectorii corespunzători, pe măsură ce selectăm elemente. Iată soluția:
// avem vectorii v1 de n1 elemente si v2 de n2 elemente
// vrem sa construim vectorul v3 de n1 + n2 elemente
i1 = 0;
i2 = 0;
i3 = 0;
while ( i1 < n1 && i2 < n2 ) { // mai avem elemente in ambii vectori?
if ( v1[i1] < v2[i2] ) { // daca v1 are elementul mai mic
v3[i3] = v1[i1]; // il copiem
i1++; // si avansam pe urmatorul element
} else { // altfel v2 are elementul cel mai mic
v3[i3] = v2[i2]; // il copiem
i2++; // si avansam pe urmatorul element
}
i3++; // avansam si in vectorul v3
}
// in acest moment unul din vectorii v1, v2 este sigur vid, posibil amindoi
while ( i1 < n1 ) { // incercam sa copiem elementele ramase in v1, daca exista
v3[i3] = v1[i1];
i1++;
i3++;
}
while ( i2 < n2 ) { // incercam sa copiem elementele ramase in v2, daca exista
v3[i3] = v2[i2];
i2++;
i3++;
}
n = n1 + n2;
O idee similară se folosește și la problema portofel, pe care o aveți ca temă.
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ă (numerele sînt foarte mici).
Temă
Rezolvați următoarele probleme:
