Bete2

Problema revine la numărarea tripleţilor de forma a = b + c în mulţimea numerelor date şi poate fi abordată în mai multe feluri. Vom prezenta câteva posibilităţi,

Varianta 1

Cea mai simplă rezolvare se bazează pe trei for-uri. Înaintea aplicării algoritmului de mai jos, şirul se sortează descrescător.

Algoritm Bete(n, lung, nr):
  Ordonare(n, lung)	{ ordonăm şirul lungimilor în ordine crescătoare }
  nr = 0
  Pentru i = 1, n - 2 execută
    Pentru j = i + 1, n - 1 execută
      Pentru k = j + 1, n execută
        Dacă lung[i] = lung[j] + lung[k] atunci
          nr ++	       { în nr numărăm posibilităţile de a forma tripleţii de forma a = b + c }
        sfârşit dacă
      sfârşit pentru
    sfârşit pentru
  sfârşit pentru
Sfârşit algoritm

Cu această rezolvare se puteau obţine 40-50 puncte.

Varianta 2

Există şi posibilitatea generării tuturor submulţimilor având trei elemente care se acceptă pentru a fi numărate doar dacă au proprietatea cerută. Înainte de aplicarea algoritmului de mai jos, şirul se sortează descrescător.

Algoritm Generare(i):
  Pentru j = x[i - 1] + 1, n - 3 + i execută	{ şirul x are şi elementul x0 = 0, generăm mulţimi având 3 elemente }
    x[i] = j
    Dacă i < 3 atunci
      Generare(i + 1)
    altfel
      Dacă lung[x[1]] = lung[x[2]] + lung[x[3]] atunci
         nr ++
      sfârşit dacă
    sfârşit dacă
  sfârşit pentru
Sfârşit algoritm

Cu această rezolvare se putea obţine aproximativ acelaşi punctaj ca soluţia precedentă.

Varianta 3

Îmbunătăţim varianta 1 reducându-i complexitatea de la Θ(n3) la Θ(n2 log n). Acest lucru este posibil înlocuind al treilea for cu algoritmul căutării binare. Cu această rezolvare se puteau obţine 100 puncte.

Varianta 4

Algoritmul poate fi îmbunătăţit în continuare prin înlocuirea căutării binare cu tabele de dispersie, obţinându-se un algoritm cu ordinul de execuţie O(n2) care ar obţine tot 100 de puncte.