Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: Eficienta Lee recursiv vs Lee liniar  (Citit de 843 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
xVladdy
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 1



Vezi Profilul
« : Februarie 27, 2019, 21:16:34 »

Tocmai astazi am invatat cum se face algoritmul lui Lee folosind coada. Dar am dat de o problema (nush daca putem chiar asa Confused):

Algoritmul recursiv mi s-a spus ca ar folosi mai multa memorie si nu ar fi tocmai eficient. Un exemplu de implementare in C++ arata ceva de genul:

Cod:
void lee(int x, int y, int k)
{
      mat[x][y]=k;
      if(k<mat[x+1][y]) lee(x+1, y, k+1);
      if(k<mat[x-1][y]) lee(x-1, y, k+1);
      if(k<mat[x][y+1]) lee(x, y+1, k+1);
      if(k<mat[x][y-1]) lee(x, y-1, k+1);
}
Acest algoritm functioneaza pe o matrice unde spatiile libere sunt egale cu n*m, iar spatiile inchise cu -1. Evident, matricea este bordata.

Al doilea algoritm (si cel pe care l-am vazut foarte mult pe internet) presupune folosirea unei cozi unde se afla vecinii elementului.
Cod:
void Fill(int x, int y)
{
    int a=harta[x][y];
    coord aux, urm;
    harta[x][y]=0;
    aux.x=x; aux.y=y;
    coada.push(aux); // de aici pornim
    while(!coada.empty()) // cat timp mai avem vecini
    {
        aux.x=coada.front().x; //cout<<coada.front().x<<' ';
        aux.y=coada.front().y; //cout<<coada.front().y<<"   ";
        coada.pop();
        for(int dir=0; dir<4; dir++)
        {
            urm.x=aux.x+dx[dir];
            urm.y=aux.y+dy[dir];
            if(ok(urm.x, urm.y) && harta[urm.x][urm.y]==a)
            {
                harta[urm.x][urm.y]=0;
                coada.push(urm);
            }
        }
    }
}
Teoretic este un algoritm de fill, dar cu cateva modificari poate deveni foarte usor Lee.

Intrebarea mea este: care dintre acesti algoritmi este mai eficient din punctul de vedere al memoriei folosite? Care dintre ei este mai rapid?
Memorat
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

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