Question

Быстрое возведение в степень Возводить в степень можно гораздо быстрее, чем за n умножений! Для этого нужно воспользоваться следующими рекуррентными соотношениями: an=(a2)n/2 при чётном n, an=a∗an−1 при нечётном n. Реализуйте алгоритм быстрого возведения в степень. Если вы всё сделаете правильно, то количество умножений будет иметь порядок log2n. Нельзя использовать операцию возведения в степень. Входные данные: Вводится действительное число a и целое неотрицательное число n. Выходные данные: Выведите ответ на задачу.
Примеры: Ввод 2 7 Вывод 128 Ввод 1.00001 100000 Вывод 2.71827

Answer 1

/*Простейшая реализация. Подразумевается, что вводятся корректные данные, n вмещается в int, а a и результат - в double. Визуализация зависимости числа операций умножения от степени n для чисел от 0 до 5000 прилагается */

#include <iostream>

double s_pow(double a, int power)

{

       if (power == 0)

       {

               return 1;

       }

       if (power % 2 == 0)

       {

               return s_pow(a * a, power / 2);

       }

       return a * s_pow(a, power - 1);

}

int main()

{

       double a;

       int n;

       std::cin >> a >> n;

       std::cout << s_pow(a, n);

       return 0;

}