Pagina informaticii

Teste de informatică pentru liceu, articole C#, C/C++, PHP

Şirul lui Hamming

Şirul lui Hamming se defineşte ca fiind mulţimea de numere H = {2i * 3j * 5k / i, j, k sunt numere naturale}. Deci primii 10 termeni ai acestui şir sunt 1, 2, 3, 4, 5, 6, 8, 9, 10, 12. În continuare voi prezenta un algoritm de complexitate pătratică şi apoi unul de complexitate liniară care generează termenii mai mici sau egali cu un M ai acestui şir.

Generarea termenilor şirului Hamming se bazează pe următoarea definiţie a şirului:

  1. 1 este termen al şirului (deoarece 1 = 20 * 30 * 50)
  2. Dacă x este un termen al şirului, atunci 2 * x, 3 * x şi 5 * x sunt termeni ai şirului
  3. Şirul conţine numai numere care îndeplinesc punctele 1. şi 2.

Vom genera termenii şirului într-un vector t. Iniţial, în t se găseşte numai valoarea 1. La fiecare pas al algoritmului, un termen al şirului va fi depus în vector. Ideea este că următorul termen generat se obţine dintr-un termen deja generat t[i] înmulţit cu 2, 3 sau 5. De aici am putea scrie o primă rezolvare care la fiecare pas se înmulţesc cu 2, 3 şi 5 toţi termenii deja generaţi ai şirului şi se determină un nou termen al şirului care este minim posibil, dar strict mai mare decât ultimul termen deja generat. Mai jos este ilustrată funcţia care implementează această idee, complexitatea fiind pătratică

void Hamming(int *t, int &p, int M)
{
  int x, ultimul, i, minim ;
  t[0] = 1 ;
  p = 1 ;
  ultimul = 1 ; // ultimul termen generat al sirului
  while (ultimul <= M)
  {
    minim = 2000000000 ;
    for (i=0 ; i<p ; i++)
    {
      x = 2 * t[i] ;
      if ((minim > x) && (x > ultimul))
        minim = x ;
    x = 3 * t[i] ;
    if ((minim > x) && (x > ultimul))
        minim = x ;
    x = 5 * t[i] ;
    if ((minim > x) && (x > ultimul))
      minim = x ;
    }
    if (minim <= M) t[p++] = minim ;
    ultimul = minim ;
  }
}

Algoritmul liniar se bazează pe faptul că pentru generarea următorului termen nu se va face căutare printre toţi termenii deja generaţi ai şirului, ci numai într-o mulţime de 3 termeni candidaţi {x2, x3, x5} (toţi cei 3 termeni fiind mai mari decât ultimul termen deja generat al şirului), unde

  • x2 este cea mai mică valoare de forma 2 * t[i]
  • x3 este cea mai mică valoare de forma 3 * t[i]
  • x5 este cea mai mică valoare de forma 5 * t[i]

La fiecare pas vom alege minimul dintre x2, x3 şi x5, urmând ca acea valoare aleasă dintre x2, x3, x5 să fie înmulţită cu 2, 3 sau 5 pentru a se obţine alt candidat. Funcţia care generează acest şir în complexitate liniară este descrisă mai jos:

void Hamming(int *t, int &p, int M)
{
  int x, x2, x3, x5, i, j, k ;
  x = 1 ;
  t[0] = 1 ;
  p = 1 ;
  x2 = 2 ; i = 0 ;
  x3 = 3 ; j = 0 ;
  x5 = 5 ; k = 0 ;
  while (x < M)
  {
    // determin in x valoarea minim{x2, x3, x5}
    if (x2 <= x3 && x2 <= x5) x = x2;
    if (x3 <= x2 && x3 <= x5) x = x3;
    if (x5 <= x2 && x5 <= x3) x = x5;
    //depun valoarea minima in tablou
    if (x <= M) t[p++] = x ;
    // pas urmator pentru minim{x2, x3, x5}
    if (x == x2) x2 = t[++i] * 2;
    if (x == x3) x3 = t[++j] * 3;
    if (x == x5) x5 = t[++k] * 5;
  }
}

Recomand pentru înţelegerea mai bună a algoritmului liniar o verificare a funcţiei pas cu pas pentru un M dat.

Despre autor
Author

Dan Pracsiu deţinător www.dponline.ro
Profesor, Liceul Teoretic "Emil Racoviță" Vaslui
Membru în Comisia Naţională a Olimpiadelor de Informatică
Pasiuni: istoria, călătoriile, fotografia, muzica clasică

Comentarii (4)
  • Avatar

    Anonim 7-7-2012 19:6:10

    La programul cu complexitate patratica nu cumva ai uitat sa il cresti pe "p"?
    Daca rulezi programul fara sa il cresti nu va avea loop la infinit?
    Si de ce la ultima functie if l-ai facut pe t[p++] = minim si nu t[i++] = minim?

    Oricum, multumesc. Acum inteleg mult mai bine sirul lui Hamming.

  • Avatar

    Anonim 7-7-2012 19:13:0

    Si nu este mai sigur sa il declari pe minim = M + 1 ? In felul acesta ar fuctiona pentru orice numar M.

  • Avatar

    Anonim 7-7-2012 19:22:17

    Si nu este mai sigur sa il declari pe minim = M + 1 ? In felul acesta ar fuctiona pentru orice numar M.

  • Avatar

    Dan P. 9-7-2012 10:5:4

    La prima intrebare: Nu, nu am uitat sa-l cresc pe p. Verifica mai bine! La a doua intrebare: Initializarea cu 2 miliarde nu a fost pentru mine esntiala. Ideea era sa fie o valoare foarte mare. E bine M + 1. Dar esentialul este algoritmul liniar

Scrie un comentariu
Nume:

Comentariu:

15 + 10 =