
Interclasarea a doi vectori în C++
Se dau doi vectori cu numere naturale ordonate crescător. Se dorește formarea unui alt vector care să conțină valorile din ambii vectori, tot în ordine crescătoare.
Exemplu. Dacă avem vectorii a = (1, 2, 5, 9)
și b = (3, 4, 5, 7)
,
atunci vectorul rezultat este c = (1, 2, 3, 4, 5, 5, 7, 9)
.
O metodă ar fi să lipim al doilea vector de primul, după care să sortăm elementele. Deși această soluție funcționează, rezolvarea problemei devine mai complicată. În plus, nu se folosește deloc de faptul că vectorii sunt inițial sortați crescător.
În această lecție învățăm metoda eficientă de rezolvare a acestei probleme, cu ajutorul interclasării.
Algoritmul pentru interclasarea a doi vectori
Interclasarea a doi vectori constă în parcurgerea concomitentă a vectorilor, selectând pe rând elementul mai mic dintre elementul curent din primul vector și din al doilea. Iată o animație care demonstrează această idee:
Vector | Valoare |
---|---|
a | (11, 22, 55, 99) |
b | (33, 44, 55, 77) |
c | (1, 2, 3, 4, 5, 5, 7, 9) |
Explicarea algoritmului de interclasare
Să zicem că avem cei doi vectori ordonați crescător:
-
a
, de lungimen
; -
b
, de lungimem
;
Vom crea un al treilea vector, c
, de lungime k
, care să rețină la final
interclasarea.
- Inițial, vectorul
c
este gol (k = 0
); - Parcurgem vectorii
a
șib
concomitent, cu uni
și unj
; cu alte cuvinte, cât timpi <= n && j <= m
(cât timp suntem în ambii vectori):- Comparăm
a[i]
cub[j]
(elementele curente din cei doi vectori); - Adăugăm elementul mai mic la
c
; dacăa[i] < b[j]
:- Adăugăm la
c
elementula[i]
(k++, c[k] = a[i]
); - Creștem
i
cu1
(i++
);
- Adăugăm la
- În caz contrar, dacă
b[j] ≤ a[i]
:- Adăugăm la
c
elementulb[j]
(k++, c[k] = b[j])
; - Creștem
j
cu1
(j++
);
- Adăugăm la
- Comparăm
- Verificăm dacă în vreunul dintre vectori au rămas elemente nepuse;
- Dacă
i <= n
atunci mai avem elemente în vectorula
, pe care le adăugăm înc
, pe rând; - Dacă
j <= m
atunci mai avem elemente în vectorulb
, pe care le adăugăm înc
, pe rând;
- Dacă
- Vectorul
c
este format.
Implementarea în C++
#include <iostream>
using namespace std;
//Declarăm cei trei vectori
int a[101], b[101], c[201], n, m, k; //Vectorul c trebuie să aibă lungimea dublă, ca să încapă elementele din ambele mulțimi
int main()
{
//Citim vectorii a și b
cin >> n;
for(int i = 1; i <= n; i++)
cin >> a[i];
cin >> m;
for(int i = 1; i <= m; i++)
cin >> b[i];
//Începem interclasarea
int i = 1, j = 1;
while(i <= n && j <= m) { //Comparăm elementele a[i] și b[j] din vector
//Luăm mereu elementul mai mic
if(a[i] < b[j]) {
k++;
c[k] = a[i];
i++;
} else {
k++;
c[k] = b[j];
j++;
}
}
while(i <= n) { //Dacă intrăm în acest while, atunci vectorul b s-a epuizat, dar au rămas elemente în vectorul a, pe care le adăugăm pe rând ca mai sus
k++;
c[k] = a[i];
i++;
}
while(j <= m) { //Dacă intrăm în acest while, atunci vectorul a s-a epuizat, dar au rămas elemente în vectorul b, pe care le adăugăm pe rând ca mai sus
k++;
c[k] = b[j];
j++;
}
//Afișăm vectorul final
for(int i = 1; i <= k; i++)
cout << c[i] << " ";
return 0;
}
Aplicații cu interclasarea a doi vectori
Reuniunea a două mulțimi prin interclasare
Dându-se doi vectori ordonați crescător reprezentând două mulțimi, să se afișeze mulțimea ce reprezință reuniunea lor. Testează-ți rezolvarea pe această pagină.
Exemplu: Pentru mulțimile a = (1, 2, 3, 4)
și b = (3, 5, 6)
, avem
reuniunea lor c = (1, 2, 3, 4, 5, 6)
.
Rezolvare: Să notăm cei doi vectori a
și b
, iar cel răspuns c
.
Observăm că dacă făceam interclasarea vectorilor folosind algoritmul clasic,
obțineam un vector cu toate elementele din ambii, în ordine crescătoare (în
exemplul de mai sus, interclasarea clasică ar fi fost c = (1, 2, 3, 3, 4, 5, 6)
). Fiind vorba de mulțimi, toate elementele vectorului răspuns trebuie să
fie distincte — mai precis, singura diferență pe care trebuie să o facem față
de algoritmul clasic este să ne asigurăm că nu băgăm niciodată două elemente
egale unul după altul.
Implementare în C++
//Reuniunea a două mulțimi
#include <iostream>
using namespace std;
//Declarăm cei trei vectori
int a[101], b[101], c[201], n, m, k;
int main()
{
//Citim vectorii a și b
cin >> n;
for(int i = 1; i <= n; i++)
cin >> a[i];
cin >> m;
for(int i = 1; i <= n; i++)
cin >> b[i];
//Interclasarea
int i = 1, j = 1;
while(i <= n && j <= m) {
if(a[i] == b[j]) { //Nu băgăm ambele elemente, ci doar pe unul dintre ele
k++;
c[k] = a[i]; //sau b[j]
i++;
j++;
} else if(a[i] < b[j]) {
k++;
c[k] = a[i];
i++;
} else {
k++;
c[k] = b[j];
j++;
}
}
while(i <= n) {
k++;
c[k] = a[i];
i++;
}
while(j <= m) {
k++;
c[k] = b[j];
j++;
}
for(int i = 1; i <= k; i++)
cout << c[i] << " ";
return 0;
}
Intersecția a două mulțimi prin interclasare
Dându-se doi vectori ordonați crescător reprezentând două mulțimi, să se afișeze mulțimea ce reprezință intersecția lor. Testează-ți rezolvarea pe această pagină.
Exemplu: Pentru mulțimile a = (1, 2, 3, 4, 5)
și b = (3, 5, 6)
, avem
intersecția lor c = (3, 5)
.
Rezolvare: Intersecția a două mulțimi este similar cu algoritmul pentru reuniune:
- dacă întâlnim elemente egale în cele două mulțimi, adăugăm unul dintre ele în mulțimea
c
; - dacă elementul curent din primul vector este mai mic decât cel din al doilea vector, trecem la următorul element din primul vector;
- dacă elementul curent din al doilea vector este mai mic decât cel din primul vector, trecem la următorul element din al doilea vector;
- la final, dacă se termină unul dintre vectori, nu mai trebuie să iterăm printre elementele sale, deoarece nu sunt egale cu niciunul din elementele celui de al doilea vector.
Implementare în C++
//Intersecția a două mulțimi
#include <iostream>
using namespace std;
//Declarăm cei trei vectori
int a[101], b[101], c[201], n, m, k;
int main()
{
//Citim vectorii a și b
cin >> n;
for(int i = 1; i <= n; i++)
cin >> a[i];
cin >> m;
for(int i = 1; i <= n; i++)
cin >> b[i];
//Interclasarea
int i = 1, j = 1;
while(i <= n && j <= m) {
if(a[i] == b[j]) {
k++;
c[k] = a[i]; //sau b[j]
i++;
j++;
} else if(a[i] < b[j]) {
i++;
} else {
j++;
}
}
for(int i = 1; i <= k; i++)
cout << c[i] << " ";
return 0;
}
Probleme propuse
Setul de probleme 144 nu a fost găsit.
Alte resurse sau bibliografie
DS
Autorul acestei lecții
Dominic Satnoianu
Această lecție a fost redactată de către Dominic Satnoianu.
© 2021 – 2025 Aspire Education Labs SRL. Toate drepturile rezervate.
Așa cum este specificat și în termeni și condiții, conținutul acestei pagini este protejat de legea drepturilor de autor și este interzisă copierea sau modificarea acestuia fără acordul scris al autorilor.
Încălcarea drepturilor de autor este o infracțiune și se pedepsește conform legii.
Comentarii 0