Быстрое возведение в степень Возводить в степень можно гораздо быстрее, чем за n умножений! Для этого нужно воспользоваться следующими рекуррентными соотношениями: an=(a2)n/2 при чётном n, an=a∗an−1 при нечётном n. Реализуйте алгоритм быстрого возведения в степень. Если вы всё сделаете правильно, то количество умножений будет иметь порядок log2n. Нельзя использовать операцию возведения в степень. Входные данные: Вводится действительное число a и целое неотрицательное число n. Выходные данные: Выведите ответ на задачу.
Примеры: Ввод 2 7 Вывод 128 Ввод 1.00001 100000 Вывод 2.71827
ппппппппппппппиииииииииитттттттттттоооооооооооооооннннннннн
Примеры: Ввод 2 7 Вывод 128 Ввод 1.00001 100000 Вывод 2.71827
ппппппппппппппиииииииииитттттттттттоооооооооооооооннннннннн
Ответ
1
(1 оценка)
0
etojan
4 года назад
Светило науки - 106 ответов - 1186 раз оказано помощи
Вот вариант без использования встроенных кэшей, только рекурсивная функция и словарь, всё как положено:
def pow(number, power):
powers = {0: 1, 1: number}
def rec(p):
if p in powers:
# уже вычисляли эту степень
return powers[p]
elif p % 2 == 0:
# чётный случай
result = rec(p//2) * rec(p//2)
powers[p] = result
return result
else:
# нечётный случай
result = rec(p-1) * number
powers[p] = result
return result
return rec(power)
print(pow(1.253, 25))
Нельзя использовать операцию возведения в степень.<br /><br />Входные данные<br /><br />Вводится действительное число a и целое неотрицательное число n.<br /><br />Выходные данные<br /><br />Выведите ответ на задачу.<br /><br />Примеры<br />Ввод<br />Вывод<br />2<br />7<br />128<br />1.00001<br />100000<br />2.71827