👤
a fost răspuns

Să se scrie o funcție RECURSIVA IN C++ numită putere care primește 3 numere naturale a,b,c și calculează restul împărțirii lui [tex]a^{b}[/tex] la c.

***Funcția trebuie să se numească putere.
***Funcția trebuie să primească 3 parametri de tip int și să returneze un int care să stocheze numărul cerut

Restricții
***1 ≤ a ≤ 100
***2 ≤ c ≤ 1000
***0 ≤ b ≤ 1 000 000 000

Exemplu
putere(3, 6, 100) va returna 29.

Cum să calculezi eficient și corect!

Dacă încerci să îl ridici pe a la puterea b prin înmulțiri repetate, vei vedea că programul tău va fi lent și vei primi limită de timp depășită când trimiți.

Poți să calculezi [tex]a^{b}[/tex] mai eficient folosindu-te de următoarea proprietate: [tex]a^{b}[/tex] = [tex]a^{b/2}[/tex] ∗ [tex]a^{b/2}[/tex] în cazul în care b este par, altfel [tex]a^{b}[/tex] = a ∗ [tex]a^{b-1}[/tex] . Acest lucru este ușor de demonstrat dacă ne bazăm pe faptul că [tex]a^{b}[/tex] ∗ [tex]a^{c}[/tex] = [tex]a^{b+c}[/tex] .

Atenție! Deoarece numerele cresc foarte mult atunci când le înmulțim, trebuie să ai grijă ca valoarea lor să poată fi memorată într-o variabilă de tip int.

Pentru a face acest lucru poți să te bazezi pe faptul că a ∗ b și RA ∗ RB au același rest prin împărțirea la c , unde prin RA am notat restul lui a la împărțirea cu c și prin RB restul la împărțirea cu c al lui b.

DORESC SERIOZITATE! LA CEA MAI BUNA SOLUTIE PUN COROANA!!!

Răspuns :

void putere(unsingned long long int a, unsingned long long int b, unsingned long long int c)  {  

   unsigned long long int x;

   if (b==0)  cout<<0<<endl;

   else {

       if (b%2==0) x=putere(a, b/2)*putere(a, b/2);

       else  x=a*power(a, b/2)*power(a, b/2);

   }

   cout<<x%c;

}

Vă mulțumim că ați vizitat site-ul nostru web care acoperă despre Informatică. Sperăm că informațiile furnizate v-au fost utile. Nu ezitați să ne contactați dacă aveți întrebări sau aveți nevoie de asistență suplimentară. Ne vedem data viitoare și nu ratați să marcați.


Zone Alte intrebari