Рекурсивное возведение в степень

@Glbvnts · Регистрация: 10.03.2020

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

Добрый день!

Написать функцию BinPow(), которая принимает три параметра: python3-объект a, натуральное число 0<N<1000000, и некоторую ассоциативную бинарную функцию f(). Функция BinPow() реализует алгоритм бинарного возведения в степень (кроме нулевой степени). Результатом BinPow(a, n, f) будет применение f(x) к a n-1 раз.

Рекурсивный способ:

Python
1
2
def BinPow(a, n, f):
    return 1 if n == 0 else a * BinPow(a, n - 1, f)

Итерационный способ:

Python
1
2
3
4
5
6
def BinPow(a, n, f):
    res = a
    while n - 1 > 0:
        res = f(res, a)
        n -= 1
    return res

Тесты:

Python
1
2
3
print(BinPow(2, 33, int.__mul__), 2 ** 33)
print(BinPow("Se", 7, str.__add__))
print(BinPow((1, 2, 56, 23, 56, 7), 99999, tuple.__add__))

Runtime error из-за того что превышаю глубину рекурсии, а итерационный тоже считает медленно. А еще я не выполняю условие задачи в рекурсии: "Результатом BinPow(a, n, f) будет применение f(x) к a n-1 раз."

Как уменьшить вложенность рекурсии или ускорить итерационный способ?

@Catstail · 09.10.2021, 14:58

В рекурсивном способе f вообще не используется...

На всякий случай - быстрое возведение в степень (с фиксацией к-ва умножений):

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def fast_pow(x,n):
    global c
    if (n<=1):
        return (1,x)[n]
    p=x
    a=x
    k=1
    while True:
        k2=k+k
        if k2<n:
            p=p*a
            c+=1
            a=p
            k=k2
        else:
            return p*fast_pow(x,n-k)
 
c=0
print(fast_pow(2,100))
print(c)

Результат:

для n=100

1267650600228229401496703205376
12

Для n=1000

1071508607186267320948425049060001810561 4048117055336074437503883703510511249361 2249319837881569585812759467291755314682 5187145285692314043598457757469857480393 4567774824230985421074605062371141877954 1821530464749835819412673987675591655439 4607706291457119647768654216766042983165 2624386837205668069376
38

@Glbvnts · 09.10.2021, 15:35 **[ТС]**

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

return (1,x)[n]

Если я правильно понял, то этот return вернет x если n <= 1, а единицу он в каком случае вернет(если вообще вернет). Для меня эта конструкция не выглядит знакомой, что она делает? Уточните пожалуйста.

@Catstail · 09.10.2021, 15:50

Glbvnts, кортеж (1,x) состоит из двух элементов - нулевой элемент = 1, первый = x. Если n==0, то вернется 1, если n==1, то вернется x

@Glbvnts · 09.10.2021, 16:11 **[ТС]**

Catstail, это элегантно(без сарказма). Спасибо.

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .	SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11680&d=1772460536 Одним из. . .	Реалии Hrethgir 01.03.2026 Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .	Ритм жизни kumehtar 27.02.2026 Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .
SDL3 для Web (WebAssembly): Сборка библиотек: SDL3, Box2D, FreeType, SDL3_ttf, SDL3_mixer и SDL3_image из исходников с помощью CMake и Emscripten 8Observer8 27.02.2026 Недавно вышла версия 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual Studio. . . .	SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .

@Catstail Супер-модератор 38177 / 21112 / 4307 Регистрация: 12.02.2012 Сообщений: 34,716 Записей в блоге: 14
	09.10.2021, 15:50
	Glbvnts, кортеж (1,x) состоит из двух элементов - нулевой элемент = 1, первый = x. Если n==0, то вернется 1, если n==1, то вернется x 1

@Glbvnts Я не улыбаюсь. -8 / 1 / 0 Регистрация: 10.03.2020 Сообщений: 102
	09.10.2021, 16:11 [ТС]
	Catstail, это элегантно(без сарказма). Спасибо. 1

Рекурсивное возведение в степень

Решение