Clasa a VI-a lecția 3: Difference between revisions
No edit summary |
(No difference)
|
Latest revision as of 15:04, 22 October 2017
Parcurgerea circulara a unui vector
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.
Probleme cu secvente - continuare
Secvență crescătoare prin rotație
Verificare secvență crescătoare prin rotație. O secvență este crescătoare prin rotație dacă fie este crescătoare (nedescrescătoare, include mai mic sau egal), fie poate fi făcută crescătoare prin rotații succesive (permutări circulare). Am discutat despre rezolvarea liniară, care nu necesită vectori.
#include <stdio.h>
int main() {
int n, i, a, b, primul, caderi;
scanf( "%d%d", &n, &a );
primul = a;
caderi = 0; // de cite ori gasim un numar mai mic ca cel din-naintea lui
i = 1;
while ( i < n && caderi < 2 ) {
scanf( "%d", &b );
if ( a > b )
++caderi;
a = b;
++i;
}
if ( caderi == 0 ) // daca e complet crescatoare, OK
printf( "DA\n" );
else if ( caderi > 1 ) // daca descreste de doua ori, nu este crescatoare
printf( "NU\n" );
else if ( primul >= b ) // daca creste o data depinde de capete
printf( "DA\n" );
else
printf( "NU\n" );
return 0;
}
Algoritmi de sortare
Căutare binară
Căutarea binară este un mod mai rapid de a căuta pe ce poziție se află un element într-un vector.
Ce complexitate are căutarea clasică a unui element într-un vector? Deoarece elementul se poate afla pe orice poziție în vector, iar noi căutăm liniar elementele, unul după altul, rezultă că, pe medie, vom face n / 2 comparații atunci cînd elementul se află în vector. Aceasta înseamnă o complexitate de O(n). Putem să rezolvăm această problemă mai rapid?
Putem, cu condiția ca vectorul să fie ordonat. Să ne folosim de o analogie: cum căutam un cuvînt în dicționar? Dicționarul are circa 60000 de cuvinte. Dacă am căuta la rînd, liniar, ne-ar lua zile să-l găsim. Și atunci deschidem dicționarul undeva, să spunem la mijloc. Ne uităm la ce literă sîntem, să spunem 'm'. Dacă noi căutăm 'gorilă', știm că 'g' < 'm', deci vom căuta la stînga, eliminînd jumate din dicționar. Vom continua la fel, deschidem undeva la jumate în jumatea rămasă și vedem iarăși la ce literă sîntem. Atunci cînd ajungem la litera 'g' vom continua cu a doua literă. În acest fel vom găsi cuvîntul rapid, probabil în jumate de minut, în loc de zile.
Aceasta este metoda căutării binare. Dacă vectorul nostru este ordonat, putem căuta mai întîi la jumate. Dacă elementul din vector este mai mic decît elementul căutat înseamnă că trebuie să ne uităm în jumătatea dreaptă, altfel ne uităm în cea stîngă. Apoi, în vectorul rămas, vom repeta algoritmul. La fiecare pas vom înjumătăți numărul de numere rămase. Ne oprim atunci cînd subvectorul rămas are fix un element. Dacă este elementul căutat, returnăm poziția sa, altfel el nu există. Iată o implementare posibilă:
Atenție: stînga este prima poziție in vectorul căutat, iar dreapta este prima poziție în afara vectorului căutat. Dacă respectați această convenție evitați bug-urile de final de căutare cînd indicii rămîn pe loc și o condiție incorectă in while poate să ducă la o buclă infinită.
stinga = 0;
dreapta = n;
while ( dreapta - stinga > 1 ) {
mijloc = (stinga + dreapta) / 2;
if ( v[mijloc] > e )
dreapta = mijloc;
else
stinga = mijloc;
}
if ( e == v[stinga] ) {
... găsit, procesare aici ...
}
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).
Interclasare vectori
Dați doi vectori sortați crescător construiți un al treilea vector sortat care să conțină toate elementele din cei doi vectori. Sînt permise elemente duplicat. Exemplu: dați vectorii 1 4 6 9 și 2 4 5 9 12 rezultatul este vectorul 1 2 4 4 5 6 9 9 12. Nu aveți voie să folosiți funcții de sortare din biblioteca C sau Pascal.
Am mai discutat despre această problemă anul trecut. 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;TEMA
1) Probleme cu secvente
2) Probleme cu sortari
3) Rotiri multiple
