Question

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

Answer 1

Ответ:

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

}

Answer 2

Конечно, вот пример реализации алгоритма быстрого возведения в степень на C++:

cppCopy code
#include <iostream>

double fastPower(double a, int n) {
    if (n == 0) {
        return 1;
    } else if (n % 2 == 0) {
        double half_pow = fastPower(a, n / 2);
        return half_pow * half_pow;
    } else {
        return a * fastPower(a, n - 1);
    }
}

int main() {
    double a;
    int n;
    std::cin >> a >> n;

    double result = fastPower(a, n);
    std::cout << result << std::endl;

    return 0;
}

Этот код сначала определяет функцию fastPower, которая рекурсивно вычисляет степень числа a с использованием описанных вами рекуррентных соотношений. Затем в функции main считываются входные данные (число a и степень n), вызывается fastPower и результат выводится на экран.

При вводе примера 2 7 программа выведет 128, как и ожидается.