Vectori de frecventa/caracteristici

Pasii ce trebuiesc urmati pentru utilizarea vectorilor caracteristici/de frecventa sunt:

1. identificarea lungimii vectorului (v[10], v[100]…);
2. initializarea vectorului cu 0;
3. citirea datelor de intrare si actualizarea vectorului de frecventa;
4. parcurgerea vectorului de frecv si afisarea modificarilor.

Astfel:

• i = numar;
• v[i] = frecventa numarului.

 

De exemplu ,acest algoritm va forma cel mai mic numar format din cifrele unui numar citit la tastatura:

int main()
{
 int v[10],c,i;
 long long x;
 for(i=0;i<=9;i++)
 v[i]=0;
 fin>>x;
 while(x!=0)
 {
    c=x%10;
    x=x/10;
    v[c]++;
 }
 for(i=9;i>=0;i--)
 if(v[i]!=0){fout<<i;v[i]--;}
 return 0;
}

sau, pentru a forma numarul cu cifrele distincte:

int main()
{
 int v[10],c,i;
 long long x;
 for(i=0;i<=9;i++)
 v[i]=0;
 fin>>x;
 while(x!=0)
 {
 c=x%10;
 x=x/10;
 v[c]=1;
 }
 for(i=9;i>=0;i--)
 if(v[i])fout<<i;
 return 0;
}

Interclasare

   Metoda interclasarii foloseste cel putin 2 vectori ordonati pentru a creea un alt vector ordonat ce contine toate elementele acestora.

Acest exemplu foloseste 2 vectori ordonati crescator si formeaza un al treilea continand toatele elementele lor in ordine crescatoare.

int main()
{
 int a[20],b[30],c[50],m,n,i,j,k;
 cin>>n>>m;
 for(i=1;i<=n;i++)fin>>a[i];
 for(j=1;j<=m;j++)fin>>b[j];
 i=1;j=1;k=0;
 while(i<=n&&j<=m)
 {
     if(a[i]<=b[j])c[++k]=a[i++];
     else c[++k]=b[j++];
 }
 while(i<=n)c[++k]=a[i++];
 while(j<=m)c[++k]=b[j++];
 for(i=1;i<=k;i++)
     cout<<c[i]<<' ';
 return 0;
}

explicatie: a=1,3,5,7,8;       b=2,4,6,8;        c=1,2,3,4,5,6,7,8.

---

-a crescator;                                                                                                                                                           b descrescator;                                                                                                                                                     c crescator:

int main()
{
 int a[20],b[30],c[50],i,j,n,m,k;
 fin>>n>>m;
 for(i=1;i<=n;i++)fin>>a[i];
 for(j=1;j<=m;j++)fin>>b[j];
 i=1;j=m;k=0;
 while(i<=n&&j>=1)
 {
     if(a[i]<b[j])c[++k]=a[i++];
     else c[++k]=b[j--];
 }
 while(i<=n)c[++k]=a[i++];
 while(j>=1)c[++k]=b[j--];
 for(i=1;i<=k;i++)fout<<c[i]<<' ';
 return 0;
}

---

-a descrescator;                                                                                                                                                     b descrescator;                                                                                                                                                     c crescator:

int main()
{
 int a[20],b[30],c[50],n,m,j,i,k;
 fin>>n>>m;
 for(i=1;i<=n;i++)fin>>a[i];
 for(j=1;j<=m;j++)fin>>b[j];
 i=n;j=m;k=0;
 while(i>=1&&j>=1)
 {
     if(a[i]<b[j])c[++k]=a[i--];
     else c[++k]=b[j--];
 }
 while(i>=1)c[++k]=a[i--];
 while(j>=1)c[++k]=b[i--];
 for(i=1;i<=k;i++)
     fout<<c[i]<<' ';
 return 0;
}

---

-a crescator;                                                                                                                                                           b descrescator;                                                                                                                                                     c descrescator:

int main()
{
 int a[20],b[30],c[50],m,n,i,j,k;
 fin>>n>>m;
 for(i=1;i<=n;i++)fin>>a[i];
 for(j=1;j<=m;j++)fin>>b[j];
 i=n;
 j=1;k=0;
 while(i>=1&&j<=m)
 {
 if(a[i]>b[j])c[++k]=a[i--];
 else if(a[i]==b[j]){c[++k]=a[i--];j++;}
 else c[++k]=b[j++];
 }
 while(i>=1)c[++k]=a[i--];
 while(j<=m)c[++k]=b[j++];
 for(i=1;i<=k;i++)
 fout<<c[i]<<' ';
 return 0;
}

Sortare prin selectie

Sortare prin selectia elementului maxim:

int main()
 {
 int maxi,p,i,n,v[100],j,aux;
 cin>>n;
 for(i=1;i<=n;i++)
  cin>>v[i];
 for(i=n;i>=2;i--)
 {
  maxi=v[1];p=1;
  for(j=1;j<=i;j++)
  if(v[j]>maxi)
  {
   maxi=v[j];
   p=j;
  }
  aux=v[i];
  v[i]=v[p];
  v[p]=aux;
 }
 for(i=1;i<=n;i++)
  cout<<v[i]<<' ';
 return 0;
 }

Sortare prin selectia elementului minim:

int main()
{
 int n,i,mini,p,j,aux,v[100];
 cin>>n;
 for(i=1;i<=n;i++)
  cin>>v[i];
 for(i=1;i<=n-1;i++)
 {
  mini=v[i];
  p=i;
  for(j=i+1;j<=n;j++)
  if (v[j]<mini)
  {
   mini=v[j];
   p=j;
  }
  aux=v[i];
  v[i]=v[p];
  v[p]=aux;
 }
 for(i=1;i<=n;i++) cout<<v[i]<<' ';
 return 0;
}

Interschimbarea termenilor egal departati

Acest set de instrucțiuni ajută în cazul problemelor în care vectorul este ordonat crescător și vrem să îl ordonăm descrescător sau invers.

aux=v[i];
v[i]=v[n+1-i];
v[n+1-i];

Unde indicele n+1-i se deduce din interschimbarea lui v[1] cu v[n],v[2] cu v[n-1]…,iar for-ul se face de la i=1 până la n/2.

Sortarea de tip bubble

#include <iostream>
using namespace std;
int main()
{

    int n,i,v[100],ok,aux;
    cin>>n;
    for(i=1;i<=n;i++)
        cin>>v[i];
    do
    {
        ok=0;
        for(i=1;i<n;i++)
            if(v[i]>v[i+1])
            {
                aux=v[i];
                v[i]=v[i+1];
                v[i+1]=aux;
                ok=1;
            }
    }
    while(ok==1);
    for(i=1;i<=n;i++)
    cout<<v[i]<<' ';
    return 0;
}

Obs.

1. În cazul în care toate elementele sunt ordonate crescător, algoritmul realizează n-1 comparații și nicio interschimbare.

2. În cazul în care toate elementele sunt ordonate descrescător, algoritmul realizează:

n*(n-1) comparații

((n-1)*n)/2 interschimbări

Permutarea circulară la stânga

Deoarece numararea se face de la 1, v[0] nu va fi nefolosit; astfel, toate elementele vectorului se vor deplasa cu o pozitie spre stanga, iar apoi v[n] va prelua valoarea lui v[0].

In cazul in care numararea se va face incepand cu v[0], vom folosi o variabila auxiliara „aux”, care va prelua valoarea acestuia, se vor deplasa termenii, iar apoi v[n-1] (ultimul element din vector) va prelua la randul lui valoarea lui „aux”.

for(i=1;i<=n;i++)
    {
        v[i-1]=v[i];
        v[n]=v[0]
    }
        SAU
    aux=v[0]
    for(i=1;i<n;i++)
    {
        v[i-1]=v[i];
        v[n-1]=aux;
    }

Deplasarea la stânga

                       i ia valori de la k+1 la n; dupa eliminarea lui v[k] toti ceilalti termeni de dupa el se vor deplasa cu o pozitie spre stanga.

 for(i=k+1;i<=n;i++;)
    {
        v[i-1]=v[i];
        n--;
    }

Perechi de numere neconsecutive

• v[1]  v[2] ……. v[i]  v[i+1]  ……. v[n]

(v[i] , v[j])     j ia valori de la i+1 pana la n;

                        i ia valori de la 1 pana la n-1;

 

• v[1]  v[2]  ……. v[i-1]  v[i] …….v[n]

(v[i] , v[j])    j ia valori de la 2 pana la n;

                       i ia valori de la 1 pana la i-1;

Perechi de numere consecutive

Avem un vector cu urmatoarele elemente:

v[1]  v[2]  v[3]  v[4]  …… v[i-2]  v[i-1]  v[i] ….. v[n];

Perechi de 2 numere consecutive

(v[i-1] , v[i])        i va lua valori de la 2 pana la n;

(v[i] , v[i+1])        i va lua valori de la 1 pana la n-1;

Perechi de 3 numere consecutive

(v[i-2] , v[i-1] , v[i])          i va lua valori de la 3 la n;

(v[i-1] , v[i] , v[i+1])           i va lua valori de la 2 la n-1;

(v[i] , v[i+1] , v[i+2])          i va lua valori de la 1 la n-2;

Vectori-max si de cate ori apare

Acest program afiseaza elementul maxim si numarul lui de aparitii dintr-un vector

#include <iostream>

using namespace std;

int main()
{
    int n,i,maxi,k=0;
    cout<<"n=";cin>>n;
    int v[n];
    for(i=1;i<=n;i++)
    {
       cout<<"v["<<i<<"]=";
       cin>>v[i];
    }
    maxi=v[1];
    for(i=2;i<=n;i++)
    {
       if(v[i]>maxi)maxi=v[i];
       if(v[i]==maxi)k++;
    }
    cout<<maxi<<','<<k;
    return 0;
}