#607

Se da un interval [a,b]. Afisati cate dintre numerele din intervalul [a,b] au proprietatea ca atat ele cat si rasturnatul lor sunt patrate perfecte (ex: 144 si 441). Se cere un algoritm eficient din punct de vederea al timpului de executie.

Exemplu: pentru intervalul [100,1000] sunt 10 astfel de numere.

Rezolvarea mea:

#include


using namespace std;


int main()

{int a, b, i, j, y=1, c=0, ct=0;

cin>>a>>b;

for(i=a;i<=b;i++)

for(j=1;j<=b;j++) if(j*j==i) { while(i!=0) {c=c*10+i%10;

i=i/10;}


while(y<=b) {if(y*y==c) ct++;

y++;

}

y=1;

}



cout<
return 0;

}

La final cand rulez programul si introduc 2 numere (precum 100, respectiv 1000), nu-mi afiseaza nimic

Răspuns:

#include <iostream>

#include <cmath>

using namespace std;

int a,b, c, pp, contor;

int main()

{

   cin >> a >> b;

   if (a>b) swap(a,b);

   c=sqrt(a);

   if (c*c<a) ++c;

   int pp=c*c;

   while (pp<=b)

   {

       int rast=0;

       while (pp)

       {

           rast=rast*10+pp%10;

           pp/=10;

       }

       if ((int)sqrt(rast)==sqrt(rast))

           {++contor;}

       ++c;

       pp=c*c;

   }

   cout << contor;

}

Explicație:

caut primul pătrat perfect din intervalul [a,b]. De exemplu, pentru a=200, b=500, primul pătrat perfect din interval este 225. cum îl găsim?

luăm partea intreagă a lui sqrt(200) şi o dăm unei varabile, fie c. Dacă c*c<a, atunci ++c;

Pentru a=200, c va fi 14. Deoarece 14*14<200, atunci ++c si devine 15, patratul căruia va fi primul pătrat perfect din interval. Mai luăm o variabilă pp, căria îi dăm valoarea c*c. Aflăm răsturnatul şi dacă e pătrat perfect creştem contorul care numără pătratele perfecte conform condiţiei.

Trecem la următorul pătrat perfect, crescând c şi pp=c*c.  

Aici e eficienţa, că după primul pătrat perfect găsit (225, care e 15²), nu cerctăm pe 226, ci pe 16*16, şamd...

Sper că am fost explicit... Succese în cercetare...  

Acum