Рекурсивный алгоритм для мощности питания

Question

Мне нужно вычислить мощность мощности. Например: 3^2^n. Вы можете считать n входным, но этот пример - это не то же самое, что и 9^n. Я пишу алгоритм с использованием циклов, но теперь мне нужно написать рекурсивный. Я не мог найти эффективный способ написать его.

Answer 1

Допустим, х^(у^п) = powpow(x, y, n) у и п> = 1

Если у> 1 и п> 1, powpow(x, y, n) = powpow(x, y, 1) * powpow(x, y, n-1) (ближе к результату)

Если у> 1 и п = 1, powpow(x, y, 1) = x * powpow(x, y-1, 1) (ближе)

Если у = 1 и п = 1, powpow(x, 1, 1) = x (решена)

это менее эффективно, чем в цикле, но это рекурсивно. Это то, к чему вы стремитесь ...?

EDIT, как @pjs указал, первый случай должен быть: powpow(x, y, 1) = powpow(x, powpow(y, n, 1), 1)

Answer 2

public class Power { 
    int ans = 1; 
    int z = 1; 
    int x = 1; 

    int pow1(int b, int c) { 
     if (c > 1) { 
      pow1(b, c - 1); 
     } 
     ans = ans * b; 
     return ans; 
    } 

    void pow(int a, int b, int c) { 
     x = pow1(b, c); 
     ans = a; 
     pow1(a, x - 1); 
    } 

    public static void main(String[] args) { 
     Power p = new Power(); 
     p.pow(3, 2, 3); 
     System.out.println(p.ans); 
    } 
} 

Answer 3

Reccursive подход

Мы можем вычислить мощность (х, у) эффективно в сложности O (log y), используя следующие данные:

power(x, y) : 
    if y is 0 : return 1 

    if y is even : 
     return square(power(x, y/2)) 
    else : 
     return square(power(x, (y - 1)/2) * x 

Используя master theorem, мы можем вычислить сложность описанной выше процедуры как O (log y) (аналогичный случай как двоичный поиск.)

Теперь, если мы используем описанную выше процедуру для вычисления 3^(2^n).

Мы можем видеть, что (2^n) будет вычислено в O (log n) и 3^k. Где k = 2^n, будет вычисляться в O (log k) = O (log (2^n)) = O (n).

Таким образом, используя двоичный метод экспоненции последовательно, мы можем решить это с использованием сложности O (n).

Итерационный подход

Идея: Предположим, что мы вычислили 3^(2^х). Тогда мы можем легко вычислить 3^(2^(х + 1)), просто квадратуры 3^(2^х):

(3^(2^x)) * (3^(2^x)) = 3^((2^x) + (2^x)) 
            = 3^(2 * (2^x)) 
            = 3^((2^(x + 1)) 

Таким образом, если мы начинаем с 3^(2^0), в п шагов мы можем дойти до 3^(2^п):

def solve(n): 
    ans = 3^(2^0) = 3 
    for i in range(0, n) : 
     ans = square(ans) 
    return ans 

Очевидно, что сложность вышеуказанного раствора также о (п).

Answer 4

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

Эта реализация основана на старом трюке возведения в квадрат базы и повышении его до половины указанной мощности, когда показатель степени четный, поэтому рекурсивный стек растет логарифмически, а не линейно по мощности.Это был вдохновлен ответ Ильи, но я обнаружил, что y > 1 and n > 1 случай не является правильным, что приводит меня использовать рекурсивный вызов в рекурсивном вызове, реализованного в elif n > 1 строке ниже:

def powpow(x, y, n) 
    if y == 0 
    return 1 
    elsif y == 1 || n == 0 
    return x 
    elsif n > 1 
    return powpow(x, powpow(y, n, 1), 1) 
    elsif y.even? 
    return powpow(x * x, y/2, 1) 
    else 
    return x * powpow(x * x, y/2, 1) 
    end 
end 

p powpow(3,2,5) # => 1853020188851841 

Я был в состоянии подтвердить, что результат непосредственно:

irb(main):001:0> 2**5 
=> 32 
irb(main):002:0> 3**32 
=> 1853020188851841