Contact și feedback

Nu obții 100 de puncte sau ai nelămuriri în privința problemelor? Scrie-mi pe Instagram.


Ai găsit o greșeală, vrei să raportezi un utilizator sau vrei să comunici altceva? Folosește formularul de contact.


Vrei să ne transmiți o părere despre platformă? Folosește formularul de feedback.

Shortcuturi

Folosește următoarele shortcuturi pentru a naviga mai ușor pe platformă.

Generale

Meniu shortcuturi?
Căutare probleme sau utilizatori/
Navigare printre rezultatele căutării↑, ↓
Meniu de contact și feedbackCTRL + Shift + F
Ieșire din meniuriEsc

Editor probleme

Setări editorCTRL + Shift + S
Schimbare stil editorCTRL + Shift + E
Șabloane de codCTRL + Shift + 1/2/3
Golire editorCTRL + Shift + 4

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 lungime n;
  • b, de lungime m;

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 și b concomitent, cu un i și un j; cu alte cuvinte, cât timp i <= n && j <= m (cât timp suntem în ambii vectori):
    • Comparăm a[i] cu b[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 elementul a[i] (k++, c[k] = a[i]);
      • Creștem i cu 1 (i++);
    • În caz contrar, dacă b[j] ≤ a[i]:
      • Adăugăm la c elementul b[j] (k++, c[k] = b[j]);
      • Creștem j cu 1 (j++);
  • Verificăm dacă în vreunul dintre vectori au rămas elemente nepuse;
    • Dacă i <= n atunci mai avem elemente în vectorul a, pe care le adăugăm în c, pe rând;
    • Dacă j <= m atunci mai avem elemente în vectorul b, pe care le adăugăm în c, pe rând;
  • 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

# Problemă Dificultate
5. Timbre Ușoară (2 )
287. Interclasare 3 Medie (4 )
285. Intersectia multimilor Ușoară (2 )
284. Reuniunea multimilor Ușoară (2 )
693. Partitura Grea (8 )
Vrei mai multe probleme? Pe această pagină găsești întreaga listă de probleme propuse.

Alte resurse sau bibliografie

Obține medalia mult dorită. Devino As la olimpiadă.

Curs complet de olimpiadă, pregătit de olimpici de la Oxford și TU Delft.

Cuprinsul lecției

Se încarcă…

Citește și

Interclasarea a doi vectori în C++Cea mai lungă secvență de elemente crescătoare în C++Recursivitate în C++Câte numere naturale sunt într-un interval dat? (C++)Rădăcina cubică a unui număr în C++ (cube root)Numărul aranjamentelor în C++ (formula aranjamentelor)Cum să calculezi instant 2 la puterea N în C++Cel mai puțin semnificativ bit în C++Transformarea unei litere mari în literă mică în C++Codul ASCII (tabel complet)Verifică dacă un bit de pe o anumită poziție este 1 sau 0 în C++Tipul struct în C++. Ce sunt structurile de date neomogeneTransformarea unui număr din baza 2 în baza 10 în C++Bordarea unei matrice în C++Șirul lui Fibonacci în C++Operații cu numere mari în C++ - Toate funcțiile explicateVerificare dacă un număr este palindrom în C++Oglinditul recursiv al unui număr în C++Afișarea elementelor unui vector recursiv în C++Căutare binară în C++CMMDC recursiv a două numere naturale în C++Instrucțiunea do while (structuri repetitive)Aplicații cu ciurul lui Eratostene în C++: suma divizorilor, numărul divizorilorCe înseamnă variabilă globală și locală în C++?CMMMC a două numere în C++ (cel mai mic multiplu comun)Maximul și minimul a n valori în C++Inversarea unui vector în C++Instrucțiunea while (structuri repetitive)Complexitatea unui algoritm (timp și spațiu) în C++Instrucțiunea for (structuri repetitive)Aflarea sumei primelor N sume GaussVerifică dacă un număr dat este o putere de 2 în C++Funcții predefinite în C++ (matematice, șiruri de caractere)Interschimbarea a două variabile în C++ (3 metode)Maximul și minimul a trei valori în C++Verifică dacă un număr aparține șirului Fibonacci în C++De ce cer unele probleme răspunsul modulo 666013 sau modulo 1.000.000.007?Inversarea unui șir de caractere în C++Indicatorul lui Euler în C++Numărul de cifre ale factorialului unui numărInstrucțiunea continue (structuri repetitive)Matrice pătratice în C++. Diagonala principală și secundarăVerificare dacă șir de caractere este palindrom în C++Verificarea unui an bisect în C++Calculul combinărilor de n luate câte k (nCk) în C++Numărul de divizori al unui număr în C++Tipuri de date în C++: numere întregi, reale, caractere și alteleNumărul permutărilor în C++ (formula permutărilor)Verifică dacă o literă este mică sau mare în C++Ce este o funcție void în C++?Do while vs while în C++ - Care e diferența?Verificare număr prim în C++ (Clasa a IX-a)Numărul combinărilor în C++ (formula combinărilor)Afișarea divizorilor primi ai unui număr în C++Materia pentru olimpiada de informatică - tot ce trebuie să știiVerifică dacă un număr este par sau impar fără modulo în C++Verifică dacă un caracter este cifră în C++Vectori de frecvență (de apariții) în C++Ce înseamnă endl în C++?Valoarea absolută (modulul) unui număr în C++Divide et Impera (metodă de programare C++)Citește un șir de caractere cu spații în C++Instrucțiunea de decizie în C++: if, else, switch, caseAlgoritm recursiv pentru căutare binară (clasa a X-a)Cifra de control a unui numărPointer în C++. Variabile de tipul char * (char steluță)Cum să afișezi partea întreagă a unui număr real în C++Combinatorică în C++: permutări, aranjamente, combinări și alteleAl N-lea termen dintr-o progresie aritmeticăNumere triunghiulare. Verificarea unui număr triunghiularMediana unui șir de valori în C++Maximul și minimul unui vector în C++Aria și circumferința unui cerc în C++Instrucțiunea break (structuri repetitive)Cum să citești și să afișezi în fișiere în C++Suma elementelor unui vector recursiv în C++Suma 1 + 2 + 3 + ... + N în C++Ridicarea la putere în timp logaritmic în C++. Exponențiere rapidăNumărul de divizori al numerelor de la 1 la N (Folosind ciurul lui Eratostene)Matrice Fibonacci - al n-lea termen Fibonacci în timp logaritmicGenerarea șirului Fibonacci generalizat în C++Oglinditul unui număr în C++Verifică dacă trei puncte sunt coliniare C++Cel mai mare divizor comun (CMMDC) a două numere în C++Verifică dacă un caracter este literă în C++Numărul de apariții al unui număr într-un vector în C++Maximul și minimul a două valori în C++Suma divizorilor numerelor de la 1 la N (Folosind ciurul lui Eratostene)Ciurul lui Eratostene în C++Numărul minim de peroane pentru o gară în C++Tutorial instalare CodeBlocks (ușor) - Introducere în informatică C++Șiruri de caractere în C++. Tot ce trebuie să știiCel mai semnificativ bit în C++Numărul de divizori primi ai unui număr în C++Comentarii în C++Vectorii în C++: declarare și parcurgereVerifică dacă o literă este vocală în C++Sortare crescătoare recursivă în C++ - Merge sort și Bubble sortAflă secolul unui an citit de la tastatură în C++Ce este o variabilă unsigned în C++?Al N-lea termen Fibonacci în C++Cel mai mic/mare divizor prim al numerelor de la 1 la N (Folosind ciurul lui Eratostene)Cifra maximă a unui număr recursiv în C++Aria unui triunghi folosind coordonatele acestora în C++Suma numerelor naturale dintr-un interval dat în C++Cifra maximă și minimă a unui număr în C++Transformarea unui număr din baza 10 în baza 2 în C++Indicatorul lui Euler al numerelor de la 1 la N (Folosind ciurul lui Eratostene)Radicalul unui număr în C++ (rădăcina pătrată)Citirea și afișarea matricelor în C++Prima cifră a unui număr în C++Cel mai frecvent element dintr-un șir în C++Cel mai mic număr cu suma cifrelor N în C++Copiuțe: Cifrele unui numărFactorialul unui număr în C++Funcții în C++. Ce sunt subprogrameleTransformarea unei litere mici în literă mare în C++Suma divizorilor unui număr în C++Cifrele unui număr. Prelucrarea cifrelor unui număr în C++Structuri repetitive (while, do while, for, etc)Distanța dintre două puncte în C++Vectorii în C++: citire și afișareMatrice în C++. Declararea și parcurgerea tablourilor bidimensionaleAl N-lea termen dintr-o progresie geometrică

© Drepturi de autor

Echipa InfoAs își rezervă drepturile de autor pentru conținutul acestei pagini. Copierea conținutului fără acordul scris expres al InfoAs reprezintă o încălcare a Legii 8/1996 și va fi tratată ca atare.

Trimite lecția

Toată lecția

Doar videoclipul pe YouTube

Informatica devine ușoară cu InfoAs

Intră în cont