👤
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 oferite v-au fost de ajutor. Nu ezitați să ne contactați pentru orice întrebare sau dacă aveți nevoie de asistență suplimentară. Vă așteptăm cu drag data viitoare și nu uitați să ne adăugați la favorite!


ID Learners: Alte intrebari