Алгоритмы на С++
Решение задачи 2 главы 3
Быстрое возведение в степень. Даны \(a\) и \(N\). Вычислите \(a^N\) без использования логарифма и экспоненты.
Приведем два решения данной задачи: рекурсивное и итеративное.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
double power(double a, int n) { if (!n) return 1; // www.itmathrepetitor.ru if (n%2) return a*power(a*a,n/2); return power(a*a,n/2); } double power2(double a, int n) { double res=1; // www.itmathrepetitor.ru if (n%2) res=a; while (n>1) { n/=2; a*=a; if (n%2) res*=a; } return res; } void itmathrepetitor_ru() { double a; int n; cout<<"input a: "; cin>>a; // www.itmathrepetitor.ru cout<<"input n: "; cin>>n; cout<<power(a,n)<<endl; cout<<power2(a,n)<<endl; } |