#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ăspunsuri la întrebare
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