infoarena

Care dintre acesti doi algoritmi este mai performant?  :-k Multumesc.  :D

Problema: Se considera un vector cu n elemente intregi. Sa se elimine cat mai putine elemente de la extremitatiile vectorului astfel incat cele doua valori ramasa la "capete" sa fie consecutive.
Exemplu: Pentru n=9 si vectorul (8,2,4,5,2,5,3,4,6) se va afisa: (2,4,5,2,5,3).

Primul algoritm determina pentru fiecare element din vector pozitia elementului "pereche", adica a elementului cel mai apropriat de ultimul element, cu proprietatea ca valoarea absoluta a diferentei lor este egala cu 1.

#include<iostream>
#include<math.h>
int main() {
int a[100],min,n,i,j,poz1,poz2,x;
cin>>n;
min=n; poz1=0; poz2=-1;
for(i=0;i<n;i++) cin>>a;
for(i=0;i<n;i++) {
  for(j=n-1;j>=i;j--)
    if (abs(a-a[j])==1) x=j,break;
  if(n-x<min) min=n-x, poz1=i, poz2=x;
}
for(i=p1;i<=p2;i++)
  cout<<a<<' ';
return 0;
}

Urmatorul algoritm simuleaza stergerea primului element si verificarea cerintei, stergerea ultimului element si verificarea, stergerea primelor doua elemente, stergerea primului si al ultimului element, stergerea ultimelor doua elemente, stergere primelor trei, primelor doua si al ultimului, primului si al ultimelor doua, ultimelor trei si asa mai departe (neconsiderand faptul ca in urmatorul algoritm mut elementele vectorului si nu ca in precedentul):

#include<iostream>
#include<math.h>
int main()
{
   int a[100],n,i,j,ok=0;
   std::cout<<"Dati numarul de componente al tablouli unidimensional: ",std::cin>>n;
   for(i=0;i<n;i++) std::cout<<"a["<<i+1<<"]=",std::cin>>a;
   for(i=0;i<n-1 && !ok;i++)
      for(j=0;j<i && !ok;j++)
         if(abs(a[i-j]-a[n-1-j])==1)
         {
            n=n-j //sterg ultimele j elemente deoarece am gasit a[i-j] si a[n-j-1] consecutive
                                i=i-j; //voi folosi variabilele i si j pentru a muta elementele pe a[0],a[1],... incepand cu elementul a[i-j]
            for(j=i;j<n;j++) a[j-i]=a[j];
            n-=i; //in final micosrez numarul elementelor cu i care este de fpat i-j de inainte.
                                ok=1; //iar cu variabila ok stabilesc faptul ca nu mai este nevoie sa continui cautarea.
         }
   for(i=0;i<n;i++) std::cout<<a<<" ";
   std::cout<<std::endl;      
   return 0;
}

Nu are nicio importanta ca muti elementele in al doilea algoritm deoarece le muti o singura data. Ca sa poti compara performanta algoritmilor ar fi util sa inveti despre complexitatea algoritmilor. Ambii algoritmi fac in cel mai rau caz in jur de N^2 pasi. Primul algoritm se comporta bine cand cele doua capete sunt la sfarsit (face aproximativ N pasi in acest caz) iar al doilea atunci cand capetele sunt cat mai departate. Apropo, cred ca la al doilea algoritm ai niste greseli la implementare.

Citeste despre complexitatea algoritmilor si dupa aceea incearca sa rezolvi problema in timp liniar(se poate).

Stiu ca thread-ul e vechi, dar sunt curios cum se rezolva problema asta in timp liniar. Eu ma indoiesc ca se poate.

Se poate rezolva cu hashuri in timp liniar.

Parcurgi de la stanga la dreapta si marchezi intr-un hash prima pozitie pe care intalnesti o valoare (o structura utila pentru asta in C++ este unordered_map (http://www.cplusplus.com/reference/unordered_map/unordered_map/?kw=unordered_map)).

Apoi parcurgi de la dreapta la stanga si pentru fiecare valoare intalnita v, te uiti in hash dupa v - 1. Actualizezi raspunsul cu distanta dinre pozitia curenta si pozitia lui v - 1 (pe care o iei din hash).

Nu cred ca se poate liniar fara hashuri.

Cred ca ar fi o idee buna daca ai verifica daca a=a[n]+1, altfel sa elimine elemente pe rand cu o variabila de control: pt k = 0 sa elimine ultimul element si pt k=1 primul element pana la cealalta extremitate  si dupa sa-l elimine. Este o idee buna?