infoarena

Care e cel mai rapid mod de a testa daca un numar e patrat perfect?
Eu fac asa:
Ma gandesc ca o cautare binara ar fi prea inceata:

M-am gandit si asa: Diferenta dintre 2 patrate perfecte consecutive este un numar impar.
  (n+1)²-n²=n²+2n+1-n²=2n+1.
De unde verific asa:

Prima solutie are complexitate O(1), dar ma gandesc ca dureaza prea mult din cauza functie sqrt(), iar a doua si a treia O(log n), respectiv O(sqrt(n)).
Nici una nu mi se pare suficient de rapida, mai ales ca iau TLE la o problema de pe TIMUS.
Ma poate ajuta cineva cu vreo imbunatatire?

pai...ca sa verific daca e patrat perfect fac if(powl(floor(sqrt(n)),2)==n)  return 0; else return 1; :) ..... mi se pare destul de eficient.....
floor(x) - returneaza numarul  mai mic egal ca <=x. (floor(11.2)=11)

Nu sunt 100% sigur cum este determinat radicalul cu functia sqrt, dar poti incerca sa il implementezi de mana:

Iei un sir x_n=.5*(x_n-1+a/x_n-1), unde a este numarul al carui radical il cauti. x0 poate fi ce valoare vrei tu. Intr-a 11-a inveti ca sirul va tinde la sqrt(a). Poti citi mai multe aici (http://web01.shu.edu/projects/reals/numseq/answers/convseq3.html)... o sa vezi si ca in cativa pasi (vreo 4) gasesti o aproximare destul de buna pt sqrt(2).

Sper sa te ajute aceasta idee ;)

PS : Alexandru, omul intreba in PascalC++... oricum pare ca stie de sqrt(n) si vrea o imbunatatire a acestei functii, nu o alta metoda de a scrie acelasi lucru.

din cate stiu sqrt lucreaza pe numere reale si este destul de incet.
Poti incerca sa cauti binar rezultatul. ;)



PS: Foarte tare faza cu sirul care converge la sqrt(a)   :thumbup:

@sima_cotizo: Inteleg cat de cat si Pascal.
@alexandru: Cam asa ceva scriu si eu, doar ca in C++.
@Mishu: Am scris si cautare binara.
Oricum cea mai tare(nu cea mai rapida totusi) idee e cea cu sirul care are limita sqrt(a).
Pana acuma tot prima mea metoda merge mai repede. Poate tre sa incerc alt algoritm pt. problema mea. In linii mari problema care nu o pot rezolva destul de rapid e sa determin daca un numar n se poate scrie ca suma de 2 patrate perfecte(daca n=a²+b²).

Si eu in ce limbaj .........am scris?? Nu stiu pascal :P. Daca nu vrei sqrt ... poti folosii powl, ridici la 1/2 :P

problema cu acele functii este ca lucreaza pe numere reale si sunt destul de incete. Gandeste-te in felul asta, functia sqrt sta sa iti calculeze nush cate zecimale, cand pe tine nu te intereseaza decat sa vezi daca e intreg. De aceea ideea lu coty cu sirul care converge la sqrt e o idee buna (ma gandisem si eu mai demult la ea dar nu am fost la destule ore de analiza incat sa o pun si in practica). Cred ca totusi ca daca verifici cu cautare nu ar trebuie sa fie probleme.