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;

}

Answer 2

Ниже приведена реализация алгоритма быстрого возведения в степень на языке Python:

pythonCopy code
def fast_power(a, n):
    if n == 0:
        return 1
    
    if n % 2 == 0:
        half_power = fast_power(a * a, n // 2)
        return half_power
    else:
        return a * fast_power(a, n - 1)

# Чтение входных данных
a, n = map(float, input().split())

# Вызов функции и вывод результата
result = fast_power(a, int(n))
print(result)

Примеры использования:

makefileCopy code
Input:
2 7
Output:
128

Input:
1.00001 100000
Output:
2.71827

В данной реализации используется рекурсия для вычисления степени числа. Если степень n равна нулю, то функция возвращает 1. В противном случае, если n чётное, рекурсивно вызывается функция fast_power для a^2 и n/2. Если n нечётное, рекурсивно вызывается функция fast_power для a и n-1, а результат умножается на a. Этот процесс повторяется до достижения базового случая (когда n становится равным 0), после чего результат возвращается из рекурсии.