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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

C++

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

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++

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

Новые блоги и статьи
Как проводить научные вычисления на Python InfoMaster 15.01.2025 Python стал одним из наиболее востребованных языков программирования в области научных вычислений благодаря своей простоте, гибкости и обширной экосистеме специализированных библиотек. Научные. . .	Создание игры типа Minecraft на PyGame/Python: пошаговое руководство InfoMaster 15.01.2025 В данном руководстве мы рассмотрим процесс создания игры в стиле Minecraft с использованием библиотеки PyGame на языке программирования Python. Этот проект идеально подходит как для начинающих. . .	Как создать свою первую игру в стиле Doom на Unreal Engine InfoMaster 15.01.2025 Разработка шутера от первого лица в стиле классического Doom представляет собой увлекательное путешествие в мир игрового программирования, где сочетаются творческий подход и технические навыки. . . .	Параллельное программирование: основные технологии и принципы InfoMaster 15.01.2025 Введение в параллельное программирование Параллельное программирование представляет собой фундаментальный подход к разработке программного обеспечения, который позволяет одновременно выполнять. . .	Как написать микросервис на C# с Kafka, MediatR, Redis и GitLab CI/CD InfoMaster 15.01.2025 В современной разработке программного обеспечения микросервисная архитектура стала стандартом де-факто для создания масштабируемых и гибких приложений. Этот подход позволяет разделить сложную систему. . .	Что такое CQRS и как это реализовать на C# с MediatR InfoMaster 15.01.2025 Концепция CQRS и её роль в современной разработке В современном мире разработки программного обеспечения архитектурные паттерны играют ключевую роль в создании масштабируемых и поддерживаемых. . .
Как настроить CI/CD с Azure DevOps InfoMaster 15.01.2025 CI/ CD, или непрерывная интеграция и непрерывное развертывание, представляет собой современный подход к разработке программного обеспечения, который позволяет автоматизировать и оптимизировать процесс. . .	Как настроить CI/CD с помощью Jenkins InfoMaster 15.01.2025 Введение в CI/ CD и Jenkins В современной разработке программного обеспечения непрерывная интеграция (CI) и непрерывная доставка (CD) стали неотъемлемыми элементами процесса создания качественных. . .	Как написать микросервис на Go/Golang с Kafka, REST и GitHub CI/CD InfoMaster 14.01.2025 Определение микросервиса, преимущества использования Go/ Golang Микросервис – это архитектурный подход к разработке программного обеспечения, при котором приложение состоит из небольших, независимо. . .	Как написать микросервис с нуля на C# с RabbitMQ, CQRS, Swagger и CI/CD InfoMaster 14.01.2025 В современном мире разработки программного обеспечения микросервисная архитектура стала стандартом де-факто для создания масштабируемых и гибких приложений. Этот архитектурный подход предполагает. . .	Как создать интернет-магазин на PHP и JavaScript InfoMaster 14.01.2025 В современном мире электронная коммерция стала неотъемлемой частью бизнеса. Создание собственного интернет-магазина открывает широкие возможности для предпринимателей, позволяя достичь большей. . .	Как написать Тетрис на Ассемблере InfoMaster 14.01.2025 Тетрис – одна из самых узнаваемых и популярных компьютерных игр, созданная в 1984 году советским программистом Алексеем Пажитновым. За прошедшие десятилетия она завоевала симпатии миллионы людей по. . .

@gunslinger случайный прохожий 3067 / 2098 / 629 Регистрация: 20.07.2013 Сообщений: 5,636
	30.03.2023, 13:16	2
	В функции powder тип переменной a замени на double (или float). Плюс также измени тип возвращаемого функцией значения. 1

	30.03.2023, 15:45

Опции темы

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

Решение