Лучшие помощники
- Megamozg 2170 б
- Matalya1 1800 б
- DevAdmin 1685 б
- arkasha_bortnikov 740 б
- kirill_shatsov 715 б
3 апреля 2023 11:38
832
СРОЧНО!!! НА ПИТОНЕ!!! ДАЮ 100 БАЛЛОВ!!! Быстрое возведение в степень Возводить в степень можно гораздо быстрее, чем за n умножений! Для этого нужно воспользоваться следующими рекуррентными соотношениями: an=(a2)n/2 при чётном n, an=a∗an−1 при нечётном n. Реализуйте алгоритм быстрого возведения в степень. Если вы всё сделаете правильно, то количество умножений будет иметь порядок log2n. Нельзя использовать операцию возведения в степень.Входные данные
Вводится действительное число a и целое неотрицательное число n.
Выходные данные
Выведите ответ на задачу.
Примеры
Ввод
2
7
Вывод
128
Ввод
1.00001
100000
Вывод
2.71827
1
ответ
Ответ:
=== Python 3.8.3 ===
def fastExp(b, n):
def even(n):
if n % 2 == 0:
return True
return False
if n == 0:
return 1
if even(n):
#Можно было написать return fastExp(b, b/2) ** 2, но операцию возведения в степень использовать нам запретили.
res = fastExp(b, n/2)
return res*res
return b*fastExp(b, n-1)
def main():
base = float(input())
exp = int(input())
print(fastExp(base, exp))
if __name__ == "__main__":
main()
Предложенные тесты проходит. Сам алгоритм быстрого возведения в степень реализован в виде функции fastExp(b, n)
=== Python 3.8.3 ===
def fastExp(b, n):
def even(n):
if n % 2 == 0:
return True
return False
if n == 0:
return 1
if even(n):
#Можно было написать return fastExp(b, b/2) ** 2, но операцию возведения в степень использовать нам запретили.
res = fastExp(b, n/2)
return res*res
return b*fastExp(b, n-1)
def main():
base = float(input())
exp = int(input())
print(fastExp(base, exp))
if __name__ == "__main__":
main()
Предложенные тесты проходит. Сам алгоритм быстрого возведения в степень реализован в виде функции fastExp(b, n)
0
·
Хороший ответ
5 апреля 2023 11:38
Остались вопросы?
Еще вопросы по категории Информатика
Кто является первым программистом мира?...
Для какого из приведённых чисел ложно высказывание: НЕ (число > 50) ИЛИ (число чётное)? 1) 123 2) 56 3) 9 4) 8...
Как называется устройство для объединения сетей, использующих разные протоколы ?...
Информационное сообщение объемом 1,5 Кб содержит 3072символа.Сколько симфолов содержит алфавит,при помощи которого было записано это сообщение?...
Напишите алгоритм, под управлением которого Робот обойдёт прямоугольную область, обнесённую стеной, по периметру и закрасит угловые клетки. Размеры об...
Все предметы