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;
}

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.

Sortere prin interchimbare directa

for(i=1;i<=n-1;i++)
 {
    for(j=i+1;j<=n;j++)
    {
       if(v[i]>v[j])
       {
          aux=v[i];
          v[i]=v[j];
          v[j]=aux;
       }
    }
 }

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