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.