👤
a fost răspuns

#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 :

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

Vă mulțumim pentru vizita pe site-ul nostru dedicat Informatică. Sperăm că informațiile prezentate v-au fost utile. Dacă aveți întrebări suplimentare sau nevoie de ajutor, vă rugăm să ne contactați cu încredere. Așteptăm cu drag să reveniți și nu uitați să ne salvați în lista dumneavoastră de favorite!


En Studentsy: Alte intrebari