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

@Crazynigga1917 · Регистрация: 26.10.2017

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

Задание простое, но никак от runtime error уйти не могу в 20 тесте... А так все же работает. Подскажите в чем проблема?

Возводить в степень можно гораздо быстрее, чем за n умножений! Для этого нужно воспользоваться следующими рекуррентными соотношениями: aⁿ = (a²)ⁿ/² при четном n, aⁿ=a⋅aⁿ⁻¹ при нечетном n. Реализуйте алгоритм быстрого возведения в степень. Если вы все сделаете правильно,то сложность вашего алгоритма будет O(logn).

Python
1
2
3
4
5
6
7
8
9
10
def power(a, n):
    if n == 0:
        return 1
    if n % 2 == 0:
        return power(a, n/2)**2
    else:
        return a*power(a, n-1)
a = int(input())
n = int(input())
print(power(a, n))

@beregok77 · 10.03.2019, 19:51

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
def power(a, n):
    if n == 0:
        return 1
    elif n == 1:
        return a
    elif n % 2 != 0:
        return a * power(a, n-1)
    elif n % 2 == 0:
        return power(a*a, n/2)
 
 
a = float(input())
n = int(input())
print(power(a, n))

Jabbson · 10.03.2019, 21:43

beregok77, теперь ТС может наконец-то сдать задание, о котором спросил год назад

@mRaKoBeSi4 · 09.01.2021, 20:03

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def inf(a, n):
    if n == 0:
        return 1
    elif n == 1:
        return a
    elif n % 2 != 0:
        return a * inf(a, n - 1)
    elif n % 2 == 0:
        return inf(a * a, n / 2)
a = float(input())
n = int(input())
x = inf(a, n)
if x == int(x):
    x = int(x)
print(x)

так правильнее т.к. при введении целых чисел он выдает ответ в виде 4.0(с отображением десятых)

@TAVulator · 09.01.2021, 22:16

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

Реализуйте алгоритм быстрого возведения в степень.

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import timeit
 
def power(a, n):
    if n == 0:
        return 1
    elif n == 1:
        return a
    elif n % 2 != 0:
        return a * power(a, n-1)
    elif n % 2 == 0:
        return power(a*a, n/2)
 
 
a = float(99999999.9999)
n = int(33)
print("Total time : %.3f ms" % (1000*timeit.timeit('print(power(a, n), end=" ")', globals=globals(), number=1)))
print("Total time : %.3f ms" % (1000*timeit.timeit('print(a**n, end=" ")', globals=globals(), number=1)))

Результат:

9.999999999669995e+263 Total time : 0.122 ms

9.999999999669994e+263 Total time : 0.047 ms

ну такое...

@Arsegg · 09.01.2021, 22:42

TAVulator, тогда уже:

Python
1
2
3
4
5
6
7
In [1]: from math import pow
 
In [2]: %timeit 3 ** 400
1.85 µs ± 19.6 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
 
In [3]: %timeit pow(3, 400)
340 ns ± 28.4 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

P. S. Быстрее чем за O(1) не возвести в степень число.

Новые блоги и статьи Все статьи Все блоги /
Воспроизведение звукового файла с помощью SDL3_mixer при касании экрана Android 8Observer8 26.01.2026 Содержание блога SDL3_mixer - это библиотека я для воспроизведения аудио. В отличие от инструкции по добавлению текста код по проигрыванию звука уже содержится в шаблоне примера. Нужно только. . .	Установка Android SDK, NDK, JDK, CMake и т.д. 8Observer8 25.01.2026 Содержание блога Перейдите по ссылке: https:/ / developer. android. com/ studio и в самом низу страницы кликните по архиву "commandlinetools-win-xxxxxx_latest. zip" Извлеките архив и вы увидите. . .	Вывод текста со шрифтом TTF на Android с помощью библиотеки SDL3_ttf 8Observer8 25.01.2026 Содержание блога Если у вас не установлены Android SDK, NDK, JDK, и т. д. то сделайте это по следующей инструкции: Установка Android SDK, NDK, JDK, CMake и т. д. Сборка примера Скачайте. . .	Использование SDL3-callbacks вместо функции main() на Android, Desktop и WebAssembly 8Observer8 24.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
моя боль iceja 24.01.2026 Выложила интерполяцию кубическими сплайнами www. iceja. net REST сервисы временно не работают, только через Web. Написала за 56 рабочих часов этот сайт с нуля. При помощи perplexity. ai PRO , при. . .	Модель сукцессии микоризы anaschu 24.01.2026 Решили писать научную статью с неким РОманом	http://iceja.net/ математические сервисы iceja 20.01.2026 Обновила свой сайт http:/ / iceja. net/ , приделала Fast Fourier Transform экстраполяцию сигналов. Однако предсказывает далеко не каждый сигнал (см ограничения http:/ / iceja. net/ fourier/ docs ). Также. . .	http://iceja.net/ сервер решения полиномов iceja 18.01.2026 Выкатила http:/ / iceja. net/ сервер решения полиномов (находит действительные корни полиномов методом Штурма). На сайте документация по API, но скажу прямо VPS слабенький и 200 000 полиномов. . .

Jabbson 5907 / 3359 / 1036 Регистрация: 03.11.2009 Сообщений: 10,008
	10.03.2019, 21:43
	beregok77, теперь ТС может наконец-то сдать задание, о котором спросил год назад 1

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

Решение