Рекурсивный метод для x^n, оптимизированный для, когда n равно

Question

Мне нужно написать рекурсивный метод с использованием Java, называемый степенью мощности, которая принимает двойной x и целое число n и возвращает x^n. Вот что я до сих пор.

public static double power(double x, int n) { 
    if (n == 0) 
     return 1; 
    if (n == 1) 
     return x; 
    else 
     return x * (power(x, n-1)); 

} 

Этот код работает должным образом. Тем не менее, я пытаюсь пройти лишнюю милю и выполнять следующие дополнительные упражнения:

«Необязательный вызов: вы можете сделать этот метод более эффективным, когда n четно, используя x^n = (x^(n/2)))^2 «.

Я не уверен, как реализовать эту последнюю формулу, когда n четно. Я не думаю, что могу использовать рекурсию для этого. Я попытался реализовать следующее, но он также не работает, потому что я не могу использовать двойную силу для int.

if (n%2 == 0) 
     return (x^(n/2))^2; 

Может кто-нибудь указать мне в правильном направлении? Я чувствую, что мне не хватает чего-то очевидного. Вся помощь была оценена.

Answer 1

Это точно такой же принцип, как и для x^n == x * (x^(n-1)): Вставьте свою рекурсивную функцию для x^(n/2) и (...)^2, но убедитесь, что вы не вводите бесконечную рекурсию для п == 2 (как 2 даже, тоже):

if (n % 2 == 0 && n > 2) 
    return power(power(x, n/2), 2); 
} 

в качестве альтернативы, вы можете просто использовать промежуточную переменную:

if (n % 2 == 0) { 
    double s = power(x, n/2); 
    return s * s; 
} 

Я возможно, просто обработайте 2 как особый случай - и избегайте «и» - условия и дополнительной переменной:

public static double power(double x, int n) { 
    if (n == 0) return 1; 
    if (n == 1) return x; 
    if (n == 2) return x * x; 
    if (n % 2 == 0) return power(power(x, n/2), 2); 
    return x * (power(x, n - 1)); 
} 

P.S. Я думаю, что это должно работать, тоже :)

public static double power(double x, int n) { 
    if (n == 0) return 1; 
    if (n == 1) return x; 
    if (n == 2) return x * x; 
    return power(x, n % 2) * power(power(x, n/2), 2); 
} 

Answer 2

Когда n даже формула именно то, что Вы писали: разделяй n на два, называют power рекурсивно, и квадрат результат.

Когда n нечетно, то формула является немного более сложным: вычесть 1 из n, сделать рекурсивный вызов для n/2, квадрат результат, и умножить на x.

if (n%2 == 0) 
    return (x^(n/2))^2; 
else 
    return x*(x^(n/2))^2; 

n/2 обрезает результат, поэтому вычитание 1 не делается явно. Вот реализация в Java:

public static double power(double x, int n) { 
    if (n == 0) return 1; 
    if (n == 1) return x; 
    double pHalf = power(x, n/2); 
    if (n%2 == 0) { 
     return pHalf*pHalf; 
    } else { 
     return x*pHalf*pHalf; 
    } 
} 

Demo.

Answer 3

Подсказка: Операция ^ не будет выполнять возведение в степень в Java, но функция, которую вы написали, power волю.

Кроме того, не забывайте, что возведение в квадрат числа является таким же, как просто его умножение. Никакой вызов функции не требуется.

Answer 4

Создания небольшого изменения в вашу функцию, это уменьшит число рекурсивных вызовов, совершаемое:

public static double power(double x, int n) { 
    if (n == 0) { 
     return 1; 
    } 
    if (n == 1) { 
     return x; 
    } 

    if (n % 2 == 0) { 
     double temp = power(x, n/2); 
     return temp * temp; 
    } else { 
     return x * (power(x, n - 1)); 
    } 
} 

Answer 5

Так как

x^(2n) = (x^n)^2 

Вы можете добавить это правило в ваш метод, либо с помощью силы которую вы написали, как предложил Стефан Хаустэйн, или используя обычный оператор умножения, поскольку, похоже, вам разрешено это делать.

Обратите внимание, что нет необходимости в базовых случаях n = 1 и n = 0, одно из них достаточно (желательно использовать базовый случай n = 0, так как иначе ваш метод не будет определен для n = 0) ,

public static double power(double x, int n) { 
    if (n == 0) 
     return 1; 
    else if (n % 2 == 0) 
     double val = power(x, n/2); 
     return val * val; 
    else 
     return x * (power(x, n-1)); 
} 

Нет необходимости проверять, что n> 2 в любом случае.

Answer 6

Это просто напоминает мне больше оптимизации может быть сделано и этот следующий код.

class Solution: 
# @param x, a float 
# @param n, a integer 
# @return a float 
def pow(self, x, n): 
    if n<0: 
     return 1.0/self.pow(x,-n) 
    elif n==0: 
     return 1.0 
    elif n==1: 
     return x 
    else: 
     m = n & (-n) 
     if(m==n): 
      r1 = self.pow(x,n>>1) 
      return r1*r1 
     else: 
      return self.pow(x,m)*self.pow(x,n-m) 

то, что более промежуточный результат может быть запомнен и избежать избыточных вычислений.