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

@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) не возвести в степень число.

Новые блоги и статьи Все статьи Все блоги /
Контроль заполнения и очистка дат в зависимости от значения перечислений Maks 12.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: реализовать контроль корректности заполнения дат назначения. . .	Архитектура слоя интернета для сервера-слоя. Hrethgir 11.04.2026 В продолжение https:/ / www. cyberforum. ru/ blogs/ 223907/ 10860. html Знаешь что я подумал? Раз мы все источники пишем в голове ветки, то ничего не мешает добавить в голову такой источник, который сам. . .	Подстановка значения реквизита справочника в табличную часть документа Maks 10.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: при выборе сотрудника (справочник Сотрудники) в ТЧ документа. . .	Очистка реквизитов документа при копировании Maks 09.04.2026 Алгоритм из решения ниже применим как для типовых, так и для нетиповых документов на самых различных конфигурациях. Задача: при копировании документа очищать определенные реквизиты и табличную. . .
модель ЗдравоСохранения 8. Подготовка к разному выполнению заданий anaschu 08.04.2026 https:/ / github. com/ shumilovas/ med2. git main ветка * содержимое блока дэлэй из старой модели теперь внутри зайца новой модели 8ATzM_2aurI	Блокировка документа от изменений, если он открыт у другого пользователя Maks 08.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа, разработанного в конфигурации КА2. Задача: запретить редактирование документа, если он открыт у другого пользователя. / / . . .	Система безопасности+живучести для сервера-слоя интернета (сети). Двойная привязка. Hrethgir 08.04.2026 Далее были размышления о системе безопасности. Сообщения с наклонным текстом - мои. А как нам будет можно проверить, что ссылка наша, а не подделана хулиганами, которая выбросит на другую ветку и. . .	Модель ЗдрввоСохранения 7: больше работников, больше ресурсов. anaschu 08.04.2026 работников и заданий может быть сколько угодно, но настроено всё так, что используется пока что только 20% kYBz3eJf3jQ

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

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

Решение