Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: care algoritm este mai performant?  (Citit de 5821 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
bar0by
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 2



Vezi Profilul
« : Februarie 27, 2014, 17:28:32 »

Care dintre acesti doi algoritmi este mai performant?  Think Multumesc.  Very Happy

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;
}
Memorat
PlayLikeNeverB4
Nu mai tace
*****

Karma: 212
Deconectat Deconectat

Mesaje: 719



Vezi Profilul
« Răspunde #1 : Februarie 27, 2014, 17:46:12 »

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.
Memorat
SRadu
Client obisnuit
**

Karma: 31
Deconectat Deconectat

Mesaje: 74



Vezi Profilul
« Răspunde #2 : Februarie 28, 2014, 13:51:04 »

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


Karma: 0
Deconectat Deconectat

Mesaje: 12



Vezi Profilul
« Răspunde #3 : Decembrie 08, 2015, 18:10:59 »

Stiu ca thread-ul e vechi, dar sunt curios cum se rezolva problema asta in timp liniar. Eu ma indoiesc ca se poate.
Memorat
freak93
Echipa infoarena
Nu mai tace
*****

Karma: 341
Deconectat Deconectat

Mesaje: 789



Vezi Profilul
« Răspunde #4 : Decembrie 08, 2015, 18:38:50 »

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).

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.
Memorat
coolback
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 3



Vezi Profilul
« Răspunde #5 : Februarie 28, 2019, 17:06:41 »

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?
Memorat
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines