Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: Patrate perfecte  (Citit de 43843 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
MciprianM
Nu mai tace
*****

Karma: 87
Deconectat Deconectat

Mesaje: 324



Vezi Profilul
« : 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
  r=sqrt(n);
  daca r*r==n  scrie "Patrat perfect!\n"
  altfel  scrie "Nu e patrat perfect!\n"
Ma gandesc ca o cautare binara ar fi prea inceata:
Cod:
  int pas, i, n;
  citeste n
  pentru pas=1;pas*pas<=n;pas<<=1;
  pas>>=1;
  daca pas*pas==n scrie "Patrat perfect!\n"
  altfel pentru i=pas;pas;pas>>=1
             daca (i+pas)*(i+pas)<=n
                     i+=pas;
  daca i*i==n scrie "Patrat perfect!\n"
  altfel scrie "Nu este patrat perfect!\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;
  pentru i=p=1;p<n;p+=((i<<1)|1),++i;
 
 daca p==n  scrie "Patrat perfect!\n"
 altfel scrie "Nu este patrat perfect!\n"

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?
Memorat
alexandru92
Nu mai tace
*****

Karma: -191
Deconectat Deconectat

Mesaje: 496



Vezi Profilul
« Răspunde #1 : 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; Smile ..... mi se pare destul de eficient.....
floor(x) - returneaza numarul  mai mic egal ca <=x. (floor(11.2)=11)
Memorat
sima_cotizo
Nu mai tace
*****

Karma: 219
Deconectat Deconectat

Mesaje: 596



Vezi Profilul
« Răspunde #2 : 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... 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 Wink

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.
« Ultima modificare: Martie 05, 2009, 15:07:38 de către Sima Cotizo » Memorat
Mishu91
Nu mai tace
*****

Karma: 169
Deconectat Deconectat

Mesaje: 751



Vezi Profilul
« Răspunde #3 : 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. Wink



PS: Foarte tare faza cu sirul care converge la sqrt(a)   Thumb up
« Ultima modificare: Martie 05, 2009, 15:12:11 de către Andrei Misarca » Memorat
MciprianM
Nu mai tace
*****

Karma: 87
Deconectat Deconectat

Mesaje: 324



Vezi Profilul
« Răspunde #4 : 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).
Memorat
alexandru92
Nu mai tace
*****

Karma: -191
Deconectat Deconectat

Mesaje: 496



Vezi Profilul
« Răspunde #5 : Martie 05, 2009, 19:55:02 »

Citat din mesajul lui: Sima Cotizo
PS : Alexandru, omul intreba in PascalC++...
Si eu in ce limbaj .........am scris?? Nu stiu pascal Tongue. Daca nu vrei sqrt ... poti folosii powl, ridici la 1/2 Tongue
Memorat
devilkind
Echipa infoarena
Nu mai tace
*****

Karma: 284
Deconectat Deconectat

Mesaje: 1.240



Vezi Profilul
« Răspunde #6 : 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.
Memorat
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines