Perechi consecutive de 2/3 numere

• 2 numere:

Dacă începem de la i=1, numărul consecutiv lui v[i] (primul număr din pereche) va fi v[i+1] (al doilea număr din pereche) și vom merge până la i=n-1.

Dacă începem de la i=2, numărul consecutiv lui v[i-1] (primul număr din pereche) va fi v[i] (al doilea număr din pereche) și vom merge până la i=n.

• 3 numere:

Dacă începem de la i=1, numerele consecutive lui v[i] (primul număr din pereche) vor fi v[i+1] (al doilea număr din pereche) și v[i+2] (al treilea număr din pereche) și vom merge până la i=n-2.

Dacă începem de la i=2, numerele consecutive lui v[i-1] (primul număr din pereche) vor fi v[i] (al doilea număr din pereche) și v[i+1] (al treilea număr din pereche) și vom merge până la i=n-1.

Dacă începem de la i=3, numerele consecutive lui v[i-2] (primul număr din pereche) vor fi v[i-1] (al doilea număr din pereche) și v[i] (al treilea număr din pereche) și vom merge până la i=n.

 

Operații cu mulțimi (5/5): diferența

Pentru a realiza intersecția a 2 vectori (mulțimi), vom construi un al treilea vectori în care adăugăm doar elementele ce aparțin primului vector și nu celui de-al doilea.

#include <iostream>

using namespace std;

int main()
{
    unsigned a[101],b[101],c[202],n,m,k=0,i,j,ok;
    cin>>n;
    for(i=1;i<=n;++i)cin>>a[i];
    cin>>m;
    for(i=1;i<=m;++i)cin>>b[i];
    for(i=1;i<=n;++i)
    {
        ok=1;
        for(j=1;j<=m&&ok==1;++j)if(a[i]==b[j])ok=0;
        if(ok==1)c[++k]=a[i];
    }
    for(i=1;i<=k;++i)cout<<c[i]<<" ";
    return 0;
}

Operații cu mulțimi (4/5): intersecția

Pentru a realiza intersecția a 2 vectori (mulțimi), vom construi un al treilea vectori în care adăugăm doar elementele comune.

#include <iostream>

using namespace std;

int main()
{
    unsigned a[101],b[101],c[202],n,m,k=0,i,j,ok;
    cin>>n;
    for(i=1;i<=n;++i)cin>>a[i];
    cin>>m;
    for(i=1;i<=m;++i)cin>>b[i];
    for(i=1;i<=n;++i)
    {
        ok=0;
        for(j=1;j<=m&&ok==0;++j)if(a[i]==b[j])ok=1;
        if(ok==1)c[++k]=a[i];
    }
    for(i=1;i<=k;++i)cout<<c[i]<<" ";
    return 0;
}

Operații cu mulțimi (3/5): reuniunea

Pentru a realiza reuniunea a doi vectori (mulțimi) vom construi un al treilea vector în care mai întâi inserăm toate elementele primului vector, apoi le adăugăm pe cele care fac parte din al doilea dar nu din primul.

#include <iostream>

using namespace std;

int main()
{
    unsigned a[101],b[101],c[202],n,m,k,i,j,ok;
    cin>>n;k=n;
    for(i=1;i<=n;++i)cin>>a[i];
    cin>>m;
    for(i=1;i<=m;++i)cin>>b[i];
    for(i=1;i<=n;++i)c[i]=a[i];
    for(i=1;i<=m;++i)
    {
        ok=1;
        for(j=1;j<=n&&ok==1;++j)if(a[j]==b[i])ok=0;
        if(ok==1)c[++k]=b[i];
    }
    for(i=1;i<=k;++i)cout<<c[i]<<" ";
    return 0;
}

Operații cu mulțimi (2/5): construire de mulțime

Pentru a construi o mulțime dintr-un vector, va trebui să luăm un nou vector în care vor apărea elementele primului vector, repetate doar o dată.

#include <iostream>

using namespace std;

int main()
{
    unsigned v[101],u[101],n,i,j,k=0,ok;
    cin>>n;
    for(i=1;i<=n;++i)cin>>v[i];
    for(i=1;i<=n;++i)
    {
        ok=1;
        for(j=1;j<=k&&ok==1;++j)if(u[j]==v[i])ok=0;
        if(ok==1)u[++k]=v[i];
    }
    for(i=1;i<=k;++i)cout<<u[i]<<" ";
    return 0;
}

Operații cu mulțimi (1/5): verificare

Pentru a verifica dacă un vector este o mulțime, trebuie să verificăm dacă există sau nu doi termeni egali între ei. Dacă da, atunci vectorul nu este o mulțime.

#include <iostream>

using namespace std;

int main()
{
    unsigned v[101],n,i,j,ok=1;
    cin>>n;
    for(i=1;i<=n;++i)cin>>v[i];
    for(i=1;i<=n-1&&ok==1;++i)
        for(j=i+1;j<=n&&ok==1;++j)
        if(v[i]==v[j])ok=0;
    if(ok==1)cout<<"Vectorul este o multime.";
    else cout<<"Vectorul nu este o multime.";
    return 0;
}

Căutarea binară

Căutarea binară a unui număr într-un vector constă în verificarea egalității dintre acel număr și termenul de la mijlocul vectorului. Pentru ca acest tip de căutare să funcționeze este important ca termenii vectorului să respecte o anumită regulă (să fie ordonați). Dacă are loc egalitate, înseamnă că am găsit numărul. Dacă nu, îl vom căuta fie în partea dreaptă a vectorului, fie în partea stângă (se determină partea prin compararea numărului cu mijlocul). Dacă vectorul are n termeni, atunci numărul maxim de pași efectuați va fi log₂(n).

De exemplu, programul următor caută numărul x într-un vector ordonat crescător prin căutarea binară.

(Căutarea binară presupune eliminare de secvențe. Variabila st va reprezenta poziția capătului stâng al secvenței în care căutăm numărul, iar dr va fi poziția capătului drept al acestei secvențe. m=(st+dr)/2 va fi deci poziția termenui din mijloc.)

#include <iostream>

using namespace std;

int main()
{
    unsigned v[101],n,ok=0,x,st=1,dr,m,i;
    cin>>x>>n;
    dr=n;
    for(i=1;i<=n;++i)cin>>v[i];
    while(ok==0&&st<=dr)
    {
        m=(st+dr)/2;
        if(v[m]==x)ok=1;
        else if(v[m]>x)dr=m-1;
        else st=m+1;
    }
    if(ok==0)cout<<"Numarul "<<x<<" nu exista in vector.";
    else cout<<"Numarul "<<x<<" exista in vector.";
    return 0;
}

Se poate spune despre căutarea binară că folosește metoda Divide et Impera.

Căutarea secvențială

Căutarea secvențială a unui număr într-un vector constă în compararea fiecărui termen al vectorului cu acel număr, iar când are loc egalitate înseamnă că am găsit numărul în vector. Dacă vectorul are n termeni, atunci numărul maxim de pași efectuați va fi n.

Programul următor caută un număr x într-un vector prin căutarea secvențială.

#include <iostream>

using namespace std;

int main()
{
    unsigned v[101],n,i,ok=0,x;
    cin>>x>>n;
    for(i=1;i<=n&&ok==0;++i)
    {
        cin>>v[i];
        if(v[i]==x)ok=1;
    }
    if(ok==0)cout<<"Numarul "<<x<<" nu exista in vector.";
    else cout<<"Numarul "<<x<<" exista in vector.";
    return 0;
}

Sortare prin metoda bulelor (Bubble Sort)

Sortarea unui vector prin metoda bulelor constă în compararea fiecărui termen cu cel ce îl urmează, iar dacă nu îndeplinesc o anumită condiție, sunt interschimbate prin regula paharului. Când se ajunge la sfârșitul vectorului, se verifică dacă acesta este ordonat corect.

De exemplu, programul următor sortează prin metoda bulelor un vector cu n termeni (n<=100) în ordine crescătoare.

#include <iostream>

using namespace std;

int main()
{
    int v[101],n,i,ok=0;
    cin>>n;
    for(i=1;i<=n;++i)cin>>v[i];
    while(ok==0)
    {
        ok=1;
        for(i=1;i<=n-1;++i)
            if(v[i]>v[i+1])
        {
             v[0]=v[i];
             v[i]=v[i+1];
             v[i+1]=v[0];
             ok=0;
        }
    }
    for(i=1;i<=n;++i)cout<<v[i]<<" ";
    return 0;
}

Următorul videoclip reprezintă o metodă unică și interesantă prin care putem înțelege Bubble Sort: https://www.youtube.com/watch?v=lyZQPjUT5B4&feature=youtu.be .

Sortare prin interschimbare directă

Sortarea unui vector prin interschimbarea directă constă în ordonarea acestuia după un anumit criteriu prin compararea unui termen cu fiecare termen ce îl urmează până la ultimul din vector, iar dacă cei doi termeni nu îndeplinesc criteriul, sunt interschimbați direct (prin regula paharului).

De exemplu, programul următor sortează prin interschimbare directă un vector cu n termeni (n<=100) în ordine crescătoare.

#include 

using namespace std;

int main()
{
    int v[101],n,i,j;
    cin>>n;
    for(i=1;i<=n;++i)cin>>v[i];
    for(i=1;i<=n-1;++i)
        for(j=i+1;j<=n;++j)
           if(v[i]>v[j])
    {
        v[0]=v[i];
        v[i]=v[j];
        v[j]=v[0];
    }
    for(i=1;i<=n;++i)cout<<v[i]<<" ";
    return 0;
}