Функция мощности с использованием рекурсии

Question

Мне нужно написать метод мощности в Java. Он получает два ints и не имеет значения, являются ли они положительными или отрицательными числами. Он должен иметь сложность O(logN). Он также должен использовать рекурсию. Мой текущий код получает два числа, но результат, который я продолжаю выводить, равен нулю, и я не могу понять, почему.

import java.util.Scanner; 

public class Powers { 

    public static void main(String[] args) { 
     float a; 
     float n; 
     float res; 

     Scanner in = new Scanner(System.in); 
     System.out.print("Enter int a "); 
     a = in.nextFloat(); 

     System.out.print("Enter int n "); 
     n = in.nextFloat(); 

     res = powers.pow(a, n); 

     System.out.print(res); 
    } 

    public static float pow(float a, float n) { 
     float result = 0; 

     if (n == 0) { 
      return 1; 
     } else if (n < 0) { 
      result = result * pow(a, n + 1); 
     } else if (n > 0) { 
      result = result * pow(a, n - 1); 
     } 

     return result; 
    } 
} 

Answer 1

Давайте начнем с некоторыми математическими фактами:

• Для положительного п, aⁿ = a⨯a⨯ ... ⨯an раз
• Для отрицательного n, aⁿ = ⅟a⁻ⁿ = ⅟ (a⨯a⨯ ... ⨯a). Это означает, что a не может быть равен нулю.
• Для n = 0, aⁿ = 1, даже если a равен нулю или отрицателен.

Итак, давайте начнем с положительного n случая и работаем оттуда.

Поскольку мы хотим, чтобы наше решение было рекурсивным, мы должны найти способ определить aⁿ на основе меньшего n и работать оттуда. Обычно люди думают о рекурсии - попытаться найти решение для n-1 и работать оттуда.

И в самом деле, так как это математически верно, что aⁿ = a⨯ (aⁿ⁻¹), наивный подход был бы очень похож на то, что вы создали:

public static int pow(int a, int n) { 
    if (n == 0) { 
     return 1; 
    } 
    return (a * pow(a,n-1)); 
} 

Однако сложность этого является O (п). Зачем? Поскольку для n = 0 он не выполняет никаких умножений. При n = 1 оно одно умножение. При n = 2 он называет pow (a, 1), который, как мы знаем, является одним умножением и умножает его один раз, поэтому мы имеем два умножения. На каждом этапе рекурсии есть одно умножение, и есть n шагов. Так что это O (n).

Для того, чтобы сделать это O (log n), нам нужен каждый шаг, который необходимо применить к фракции n, а не только n-1. Здесь снова есть математический факт, который может нам помочь: a ^{n₁ + n₂} = a ^n₁ ⨯a ^n₂.

Это означает, что мы можем вычислить aⁿ как ^п/2 ⨯a ^п/2.

Но что произойдет, если n нечетно? что-то вроде a⁹ будет ^4.5 ⨯a ^4.5. Но здесь речь идет о целых силах. Обработка фракций - это совсем другое дело. К счастью, мы можем просто сформулировать это как a⨯a⁴⨯a⁴.

Таким образом, для четного числа используют ^п/2 ⨯a ^п/2, и для нечетного числа, использовать a⨯ в ⨯a ^п/2 (целочисленное деление ^п/2 , давая нам 9/2 = 4).

public static int pow(int a, int n) { 
    if (n == 0) { 
     return 1; 
    } 
    if (n % 2 == 1) { 
     // Odd n 
     return a * pow(a, n/2) * pow(a, n/2); 
    } else { 
     // Even n 
     return pow(a, n/2) * pow(a, n/2); 
    } 
} 

Это действительно дает нам правильные результаты (для положительного n, то есть). Но на самом деле сложность здесь, опять же, O (n), а не O (log n). Зачем? Потому что мы дважды вычисляем полномочия.Это означает, что мы на самом деле называем это 4 раза на следующем уровне, 8 раз на следующем уровне и т. Д. Количество шагов рекурсии экспоненциально, поэтому это отменяется с предполагаемой экономией, которую мы сделали, разделив n на два.

Но на самом деле, лишь небольшая коррекция необходима:

public static int pow(int a, int n) { 
    if (n == 0) { 
     return 1; 
    } 
    int powerOfHalfN = pow(a, n/2); 
    if (n % 2 == 1) { 
     // Odd n 
     return a * powerOfHalfN * powerOfHalfN; 
    } else { 
     // Even n 
     return powerOfHalfN * powerOfHalfN; 
    } 
} 

В этой версии мы называем рекурсию только один раз. Таким образом, мы получаем, скажем, мощность 64, очень быстро через 32, 16, 8, 4, 2, 1 и делаем. Только одно или два умножения на каждом шаге, и есть только шесть шагов. Это O (log n).

Вывод из всего этого:

1. Чтобы получить O (журнал N), нам нужно рекурсию, которая работает на фракции п на каждом шаге, а не только п - 1 или п - ничего.
2. Но фракция является лишь частью истории. Нам нужно быть осторожным, чтобы не вызывать рекурсию более одного раза, поскольку использование нескольких рекурсивных вызовов за один шаг создает экспоненциальную сложность, которая отменяется с использованием доли n.

Наконец, мы готовы позаботиться об отрицательных числах. Нам просто нужно получить ответный ⅟a⁻ⁿ. Следует отметить две важные вещи:

• Не допускайте деления на ноль. То есть, если вы получили a = 0, вы не должны выполнять расчет. В Java мы выставляем исключение в таком случае. Наиболее подходящим готовым исключением является IllegalArgumentException. Это исключение RuntimeException, поэтому вам не нужно добавлять в свой метод предложение throws. Было бы хорошо, если бы вы либо поймали его, либо не допустили такой ситуации в вашем методе main, когда читаете в аргументах.
• Вы больше не можете вернуть целое число (на самом деле мы должны использовать long, потому что мы запускаем целочисленное переполнение для довольно низких мощностей с int) - потому что результат может быть дробным.

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

public static double pow(int a, int n) { 
    if (n == 0) { 
     return 1.0; 
    } 
    if (n < 0) { 
     // Negative power. 
     if (a == 0) { 
      throw new IllegalArgumentException(
        "It's impossible to raise 0 to the power of a negative number"); 
     } 
     return 1/pow(a, -n); 
    } else { 
     // Positive power 

     double powerOfHalfN = pow(a, n/2); 
     if (n % 2 == 1) { 
      // Odd n 
      return a * powerOfHalfN * powerOfHalfN; 
     } else { 
      // Even n 
      return powerOfHalfN * powerOfHalfN; 
     } 
    } 
} 

Обратите внимание, что та часть, которая обрабатывает отрицательный п используется только на верхнем уровне рекурсии. Как только мы вызываем pow() рекурсивно, он всегда с положительными числами, и знак не изменяется до тех пор, пока он не достигнет 0.

Это должно быть адекватным решением для вашего упражнения. Однако лично мне не нравится if там в конце, так что вот еще одна версия. Можете ли вы сказать, почему это делается так же?

public static double pow(int a, int n) { 
    if (n == 0) { 
     return 1.0; 
    } 
    if (n < 0) { 
     // Negative power. 
     if (a == 0) { 
      throw new IllegalArgumentException(
        "It's impossible to raise 0 to the power of a negative number"); 
     } 
     return 1/pow(a, -n); 
    } else { 
     // Positive power 
     double powerOfHalfN = pow(a, n/2); 
     double[] factor = { 1, a }; 
     return factor[n % 2] * powerOfHalfN * powerOfHalfN; 
    } 
} 

Answer 2

обратить внимание на:

float result = 0; 

и

result = result * pow(a, n+1); 

Вот почему вы получили нулевой результат. И вместо этого он предложил работать так:

result = a * pow(a, n+1); 

Answer 3

Кроме ошибки инициализации result до 0, есть некоторые другие вопросы:

1. Ваш расчет для отрицательного n является неправильным. Помните, что a^n == 1/(a^(-n)).
2. Если n не является целым числом, расчет намного сложнее, и вы его не поддерживаете. Я не удивлюсь, если вы не обязаны его поддерживать.
3. Для того, чтобы достичь производительности O(log n), вы должны использовать стратегию разделения и завоевания. т.е. a^n == a^(n/2)*a^(n/2).

Answer 4

Хорошее правило - уйти с клавиатуры, пока не будет готов алгоритм. То, что вы сделали, очевидно, O (n).

Как предложил Эран, чтобы получить сложность O (log (n)), вы должны разделить n на 2 на каждой итерации.

Конечные условия:

• п == 0 => 1
• п == 1 => а

Особый случай:

• п < 0 => 1./pow (a, -n) // обратите внимание на 1. получить двойной ...

Нормальный случай:

• т = п/2
• результат = пау (а, п)
• результат = Ресул * Ресул // избежать вычисления дважды
• , если п нечетно (n% 2!= 0) => Ресул * = а

Этот алгоритм в O (журнал (п)) - Это до вас, чтобы написать правильный код Java из него

Но, как было сказано: п должны быть целое (отрицательное положительное нормально, но число)

Answer 5

Здесь гораздо менее запутанный способ сделать это, по крайней мере, если вы не беспокоитесь о дополнительных умножениях. :

public static double pow(int base,int exponent) { 
     if (exponent == 0) { 
      return 1; 
     } 
     if (exponent < 0) { 
      return 1/pow(base, -exponent); 
     } 
     else { 
      double results = base * pow(base, exponent - 1); 
      return results; 
     } 
    }