Question

СРОЧНО!!! НА ПИТОНЕ!!! ДАЮ 100 БАЛЛОВ!!! Быстрое возведение в степень Возводить в степень можно гораздо быстрее, чем за n умножений! Для этого нужно воспользоваться следующими рекуррентными соотношениями: an=(a2)n/2 при чётном n, an=a∗an−1 при нечётном n. Реализуйте алгоритм быстрого возведения в степень. Если вы всё сделаете правильно, то количество умножений будет иметь порядок log2n. Нельзя использовать операцию возведения в степень. Входные данные Вводится действительное число a и целое неотрицательное число n. Выходные данные Выведите ответ на задачу. Примеры Ввод 2 7 Вывод 128 Ввод 1.00001 100000 Вывод 2.71827

Answer 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)

Answer 2

Конечно, я могу помочь вам с этой задачей. Вот реализация алгоритма быстрого возведения в степень на языке Python:

pythonCopy code
def fast_exponentiation(a, n):
    if n == 0:
        return 1
    elif n % 2 == 0:
        half_power = fast_exponentiation(a, n // 2)
        return half_power * half_power
    else:
        return a * fast_exponentiation(a, n - 1)

a, n = map(float, input().split())
result = fast_exponentiation(a, int(n))
print(result)

Этот код рекурсивно вычисляет a в степени n, используя описанные рекуррентные соотношения. Если n равно 0, функция возвращает 1 (любое число в степени 0 равно 1). Если n четное, то мы вызываем функцию рекурсивно для возведения a в степень n / 2, а затем возводим результат в квадрат. Если n нечетное, мы сначала вызываем функцию для возведения a в степень n - 1, а затем умножаем результат на a.

После вычисления результата алгоритма, мы выводим его на экран.

Обратите внимание, что я использовал функцию float для преобразования вещественного числа a, а функцию int для преобразования числа n в целое число.

Надеюсь, это поможет вам! Если у вас есть еще вопросы, не стесняйтесь задавать.