Titlul: Patrate perfecte Scris de: MciprianM din Martie 05, 2009, 14:37:33 Care e cel mai rapid mod de a testa daca un numar e patrat perfect?
Eu fac asa: Cod: citeste n Cod: int pas, i, n; M-am gandit si asa: Diferenta dintre 2 patrate perfecte consecutive este un numar impar. (n+1)2-n2=n2+2n+1-n2=2n+1. De unde verific asa: Cod: int i, p; 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? Titlul: Răspuns: Patrate perfecte Scris de: alexandru din Martie 05, 2009, 14:49:47 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) Titlul: Răspuns: Patrate perfecte Scris de: Sima Cotizo din Martie 05, 2009, 14:49:53 Nu sunt 100% sigur cum este determinat radicalul cu functia sqrt, dar poti incerca sa il implementezi de mana:
Iei un sir xn=.5*(xn-1+a/xn-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 Titlul: Răspuns: Patrate perfecte Scris de: Andrei Misarca din Martie 05, 2009, 15:02:44 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: Titlul: Răspuns: Patrate perfecte Scris de: MciprianM din Martie 05, 2009, 15:26:55 @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=a2+b2). Titlul: Răspuns: Patrate perfecte Scris de: alexandru din Martie 05, 2009, 19:55:02 Citat din mesajul lui: Sima Cotizo PS : Alexandru, omul intreba in Si eu in ce limbaj .........am scris?? Nu stiu pascal :P. Daca nu vrei sqrt ... poti folosii powl, ridici la 1/2 :P Titlul: Răspuns: Patrate perfecte Scris de: Savin Tiberiu din Martie 05, 2009, 19:58:39 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.
|