233372 afișări Candale Silviu (silviu) 19.04.2023 www.pbinfo.ro
Etichete: nicio etichetă

Considerăm două tablouri unidimensionale cu elemente numere întregi ordonate crescător. Se dorește construirea unui alt tablou, care să conțină valorile din cele două tablouri, în ordine.

O soluție foarte eficientă este interclasarea:

  • considerăm două tablouri, cu n, respectiv m elemente, ordonate crescător
  • cele două tablouri se parcurg concomitent;
  • se alege valoarea mai mică dintre cele două elemente curente
    • se adaugă în al treilea tablou
    • se avansează numai în tabloul din care am ales valoarea de adăugat
  • parcurgerea unuia dintre cele două tablouri se încheie
  • toate elementele din celălalt tablou, neparcurse încă, sunt adăugate în tabloul destinație
  • tabloul destinație are p = n + m elemente

Secvență C++ – tablourile a[] și b[] sunt indexate de la 0:

int n,a[100000], m , b[100000], p, c[200000];

//citire a[] cu n elemente, indexate de la 0
//citire b[] cu m elemente, indexate de la 0

int i = 0 , j = 0;
p = 0;
while(i < n && j < m)
    if(a[i] < b[j])
        c[p ++] = a[i ++];
    else
        c[p ++] = b[j ++];
while(i < n)
    c[p ++] = a[i ++];
while(j < m)
    c[p ++] = b[j ++];

Observație: Doar una dintre instrucțiunile while(i < n)... și while(j < m)... se va executa, deoarece exact una dintre condițiile i < n și j < m este adevărată. În prima structură repetitivă, la fiecare pas, doar una dintre variabilele i și j se mărește, deci la final una dintre condiții este adevărată și una este falsă.

Algoritmul de interclasare este foarte eficient. El are complexitate O(n+m). De asemenea, este posibilă și interclasarea valorilor din două fișiere, singura condiție este ca valorile să fie ordonate.


Probleme ataşate

Nr. Problema Clasa Dificultate Operații I/O
1 #0241 - Interclasare 9 ușoară fișiere
2 #0250 - Interclasare1 9 medie fișiere
3 #0251 - Interclasare2 9 medie fișiere
4 #0284 - Interclasare3 9 medie fișiere
5 #0530 - Multimi1 9 medie consola
6 #0242 - InterclasM 9 medie fișiere
233372 afișări Candale Silviu (silviu) 19.04.2023 www.pbinfo.ro