Tablouri unidimensionale / Secvențe în vectori


Editat de Candale Silviu (silviu) la data 2019-01-28
Etichete: nicio etichetă

Definiție: Fie X[] un vector cu n element. Se numește secvență a vectorului X o succesiune de elemente consecutive din X, în ordinea din X.

Orice secvență a unui vector este unic determinată de doi indici st ≤ dr, ai primului, respectiv ultimului element din secvență.

Exemplu: Fie vectorul X[]=(10,20,30,40,50,60,70,80). Atunci:

  • (10,20,30,40), (30,40,50,60,70), (10,20,30,40,50,60,70,80), (50), (80) reprezintă secvențe ale lui X
  • (10,30,40,20) nu reprezintă secvență în X – ordinea valorilor nu este cea din X
  • (10,20,40,50) nu reprezintă secvență în X – valorile nu sunt consecutive în X
  • (10,20,30,35,40) nu reprezintă secvență în X – avem o valoare care nu apare în X

Definiție: Prin lungimea unei secvențe se înțelege numărul de elemente care formează secvența. Lungimea secvenței delimitate de indicii st și dr este dr - st + 1.

Numărul de secvențe ale unui vector

Cum determinăm numărul total de secvențe ale unui vector cu n elemente? O modalitate este următoarea:

  • sunt n secvențe de lungime 1 – fiecare element în parte.
  • sunt n-1 secvențe de lungime 2 – cele determinate de indicii 1 2, 2 3, …, n-1 n
  • sunt n-2 secvențe de lungime 3 – secvențele 1 3, 2 4, …, n-2 n
  • sunt două secvențe de lungime n-1 – secvențele 1 n-1 și 2 n
  • este o secvența de lungime n – întreg vectorul.

În total vor fi \( n + (n-1) + … + 2 + 1 = \frac{n \cdot (n+1)}{2} \) secvențe!

Secvență de lungime maximă

O problemă care apare frecvent este următoarea:

Fie X[] un vector cu elemente de un anumit tip. Să se determine cea mai lungă secvență din vector în care toate elementele au o anumită proprietate (sunt pare, impare, prime, nule, ordonate crescător, egale etc.).

Problema are mai multe soluții, cu complexități diverse. În toate soluțiile vom determina smax și dmax – indicele elementului din stânga, respectiv din dreapta al secvenței de lungime maximă. Inițial smax = 1 și dmax = 0, astfel încât lungimea secvenței delimitate de st și dr să fie dr-st+1 = 0.

În cele ce urmează vom numi secvență candidat o secvență de elemente din vector care respectă regula dată, deci ar putea fi răspunsul căutat.

Soluție \( O(n^3) \)

  • smax←1, dmax←0
  • considerăm toate perechile de indici i ≤ j
    • dacă secvența delimitată de i și j este secvență candidat
      • dacă j - i + 1 > dmax - smax + 1
        • actualizăm rezultatele: smax ← i, dmax ← j

Secvență C++ (vectorul are elemente numere naturale, se cere cea mai lungă secvență cu elemente impare; dacă sunt mai multe, o reținem pe cea mai din stânga.):

int n, X[100], smax , dmax;
//citire n, X
smax = 1, dmax = 0;
for(int i = 0 ; i < n ; i ++)
    for(int j = i ; j < n ; j ++)
    {
        bool pp = true;
        for(int k = i ; k <= j ; k ++)
            if(X[k] % 2 != 1)
                pp = false;
        if(pp)
            if(j - i + 1 > dmax - smax + 1)
                smax = i, dmax = j;
    }

Soluție \( O(n^2) \)

  • smax←1, dmax←0
  • parcurgem șirul cu un indice i
    • dacă elementul X[i] respectă regula
      • X[i] reprezintă capătul din stânga al unei secvențe candidat
      • determinăm X[j] – capătul din dreapta al celei mai lungi secvențe candidat care începe la poziția i
      • dacă j - i + 1 > dmax - smax + 1
        • actualizăm rezultatele: smax ← i, dmax ← j

Secvență C++:

int n, X[1000], smax , dmax;
//citire n, X
smax = 1, dmax = 0;
for(int i = 0 ; i < n ; i ++)
    if(X[i] % 2 == 1)
    {
        int  j = i;
        while(j + 1 < n && X[j + 1] % 2 == 1)
            j ++;
        if(j - i + 1 > dmax - smax + 1)
            smax = i, dmax = j;
    }

Soluție \( O(n) \)

Această soluție este o rafinare a celei anterioare. Observăm că dacă secvența delimitată de i j este candidat, atunci secvențele i+1 j, i+2, j, etc. sunt și ele secvențe candidat, dar nu pot fi mai lungi decât secvența i j și le putem ignora.

Secvență C++:

int n, X[100000], smax , dmax;
//citire n, X
smax = 1, dmax = 0;
for(int i = 0 ; i < n ; i ++)
    if(X[i] % 2 == 1)
    {
        int  j = i;
        while(j + 1 < n && X[j + 1] % 2 == 1)
            j ++;
        if(j - i + 1 > dmax - smax + 1)
            smax = i, dmax = j;
        i = j;
    }

Fișiere atașate


Vezi și:

Editat de Candale Silviu (silviu) la data 2019-01-28