Мощность числа

Постановка задачи

Для двойного «x» и целого числа «n» напишите функцию для вычисления «x» в степени «n». Например:

power (2, 5) = 32

power (3, 4) = 81

power (1.5, 3) = 3,375

power (2, -2) = 0. 25

Подсказка

  • Разделяй и властвуй

Попробуйте сами

  • C ++
  • C++
  • C ++
  • Java
  • Java
  • Python
  • Python
  • JavaScript
  • JavaScript
  • Ruby
  • Ruby
 double power (double x, int n) {//TODO: Write - Your - Code return x;} 

Решение

  • C ++
  • C ++
  • C ++
  • путь> Java
  • путь> Java
  • Python
  • Python
  • JavaScript
  • JavaScript
  • Ruby
  • Ruby
 double power_rec (double x, int  n) {if (n == 0) return 1;  если (n == 1) вернуть x;  двойной темп = power_rec (x, n/2);  если (п% 2 == 0) {вернуть темп * темп;  } else {return x * temp * temp;  }} удвоенная степень (двойной x, int n) {bool is_negative = false;  если (n  0.00000000001) {cout  

Объяснение решения

Сложность времени выполнения

Логарифмическая, O (logn).

Сложность памяти

Логарифмическая, O (log n ).

Рекурсивное решение имеет сложность памяти O (logn), так как оно потребляет память в стеке.

Анализ решения

Простой алгоритм решения этой проблемы — умножить «x» на «n» раз. Временная сложность этого алгоритма будет O (n). Мы можем использовать подход «разделяй и властвуй» для более эффективного решения этой проблемы.

  • На этапе деления мы продолжаем делить n на 2 рекурсивно, пока мы не достигнем базового случая, то есть n == 1
  • На этапе объединения мы получаем результат ‘r’ подзадачи и вычисляем результат текущего проблема с использованием двух правил ниже:
    • если n четно, результат будет r * r (где r — результат подзадачи)
    • если n нечетно, результат будет x * r * r (где r — результат подзадачи)
Оцените статью
nanomode.ru
Добавить комментарий