Быстрое возведение в степень

@05126619z · Регистрация: 12.03.2023

Студворк — интернет-сервис помощи студентам

Быстрое возведение в степень
Возводить в степень можно гораздо быстрее, чем за n умножений! Для этого нужно воспользоваться следующими рекуррентными соотношениями:

an=(a2)n/2 при чётном n,

an=a⋅an−1 при нечётном n.

Реализуйте алгоритм быстрого возведения в степень. Если вы всё сделаете правильно, то количество умножений будет иметь порядок log2n.

Нельзя использовать встроенную операцию возведения в степень; в силу особенностей тестирующей системы избегайте слова pow в названии функции.

Входные данные

Вводится действительное число a и целое неотрицательное число n.

Выходные данные

Выведите ответ задачи.

Примеры
Ввод
2
7
Вывод
128

Ввод
1.00001
100000
Вывод
2.71827

Мой код выводит единицу на втором тесте:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>
int powder(int a, int n)
{
    if (n == 0)
        return 1;
    else
        return a*powder(a, n-1);
}
int main(){
    float a;
    long long n;
    std::cin >> a >> n;
    std::cout << powder(a,n);
}

@gunslinger · 30.03.2023, 13:16

В функции powder тип переменной a замени на double (или float).
Плюс также измени тип возвращаемого функцией значения.

Байт · 30.03.2023, 15:40

Сообщение от gunslinger

В функции powder тип переменной a замени на double (или float).

Что совершенно очевидно, если внимательно почесть задание

Сообщение от 05126619z

Вводится действительное число a и целое неотрицательное число n.

Ну, и не flout, конечно.
И в коде ТС никакого ускорения нет

C++
1
2
3
4
5
6
7
8
double powder(double a, int n)
{
    if (n == 0)
        return 1;
    double a2 = (n%2) ? a : 1;
    double p = powder(a, n/2);
    return a2*p*p;
}

Вот так оно получше будет

Добавлено через 2 минуты
На просторах форума встречалось много-много раз

@05126619z · 30.03.2023, 15:45 **[ТС]**

Исправил

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
double der(double a, long long n)
{
    if (n == 0)
        return 1;
    else if (n % 2 == 0)
        return der(a*a, n/2);
    else
        return a*der(a, n-1);
}
int main(){
    double a;
    long long n;
    std::cin >> a >> n;
    std::cout << der(a,n);
}

Новые блоги и статьи Все статьи Все блоги /
Фото: Daniel Greenwood kumehtar 13.11.2025	Расскажи мне о Мире, бродяга kumehtar 12.11.2025 — Расскажи мне о Мире, бродяга, Ты же видел моря и метели. Как сменялись короны и стяги, Как эпохи стрелою летели. - Этот мир — это крылья и горы, Снег и пламя, любовь и тревоги, И бескрайние. . .	PowerShell Snippets iNNOKENTIY21 11.11.2025 Модуль PowerShell 5. 1+ : Snippets. psm1 У меня модуль расположен в пользовательской папке модулей, по умолчанию: \Documents\WindowsPowerShell\Modules\Snippets\ А в самом низу файла-профиля. . .	PowerShell и онлайн сервисы. Валюта (floatrates.com руб.) iNNOKENTIY21 11.11.2025 PowerShell функция floatrates-rub Примеры вызова: # Указанная валюта 'EUR' floatrates-rub -Code 'EUR' # Список имеющихся кодов валют floatrates-rub -Available function floatrates-rub {	PowerShell и онлайн сервисы. Погода (RP5.ru) iNNOKENTIY21 11.11.2025 PowerShell функция Get-WeatherRP5rss для получения погоды с сервиса RP5 Примеры вызова Get-WeatherRP5rss с указанием id 5484 — Москва (восток, Измайлово) и переносом строки:. . .
PowerShell и онлайн сервисы. Погода (wttr) iNNOKENTIY21 11.11.2025 PowerShell Функция для получения погоды с сервиса wttr Примеры вызова: Погода в городе Омск с прогнозом на день, можно изменить прогноз на более дней, для этого надо поменять запрос:. . .	PowerShell и онлайн сервисы. Валюта (ЦБР) iNNOKENTIY21 11.11.2025 # Получение курса валют function cbr (] $Valutes = @('USD', 'EUR', 'CNY')) { $url = 'https:/ / www. cbr-xml-daily. ru/ daily_json. js' $data = Invoke-RestMethod -Uri $url $esc = 27 . . .	И решил я переделать этот ноут в машину для распределенных вычислений Programma_Boinc 09.11.2025 И решил я переделать этот ноут в машину для распределенных вычислений Всем привет. А вот мой компьютер, переделанный из ноутбука. Был у меня ноут асус 2011 года. Со временем корпус превратился. . .	Мысли в слух kumehtar 07.11.2025 Заметил среди людей, что по-настоящему верная дружба бывает между теми, с кем нечего делить.	Новая зверюга volvo 07.11.2025 Подарок на Хеллоуин, и теперь у нас кроме Tuxedo Cat есть еще и щенок далматинца: Хочу еще Симбу взять, очень нравится. . .

@gunslinger place status here 3185 / 2219 / 640 Регистрация: 20.07.2013 Сообщений: 5,984
	30.03.2023, 13:16
	В функции powder тип переменной a замени на double (или float). Плюс также измени тип возвращаемого функцией значения. 1

Опции темы

Быстрое возведение в степень

Решение