Предмет: Информатика,
автор: deochan
Быстрое возведение в степень Возводить в степень можно гораздо быстрее, чем за n умножений! Для этого нужно воспользоваться следующими рекуррентными соотношениями: an=(a2)n/2 при чётном n, an=a∗an−1 при нечётном n. Реализуйте алгоритм быстрого возведения в степень. Если вы всё сделаете правильно, то количество умножений будет иметь порядок log2n. Нельзя использовать операцию возведения в степень. Входные данные: Вводится действительное число a и целое неотрицательное число n. Выходные данные: Выведите ответ на задачу.
Примеры: Ввод 2 7 Вывод 128 Ввод 1.00001 100000 Вывод 2.71827
Ответы
Автор ответа:
8
/*Простейшая реализация. Подразумевается, что вводятся корректные данные, 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;
}
Приложения:

Похожие вопросы
Предмет: Русский язык,
автор: elenadneprovsk
Предмет: Английский язык,
автор: Septimus
Предмет: Другие предметы,
автор: ghj555
Предмет: Алгебра,
автор: Altern