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

Мне нужно написать рекурсивный метод с использованием Java с именем power, который принимает двойной 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 четно. Я не думаю, что могу использовать рекурсию для этого. Я попытался реализовать следующее, но он также не работает, потому что я не могу взять double в силу int.

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

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

Ответ 1

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

Ответ 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;
    }
}

Демоверсия

Ответ 3

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

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

Ответ 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));
    }
}

Ответ 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 в любом из случаев.

Ответ 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)

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