Metodo ricorsivo per x^n ottimizzato per quando n è pari

Question

Ho bisogno di scrivere un metodo ricorsivo usando Java chiamato power che prende un doppio x e un intero n e che restituisce x^n. Ecco cosa ho finora.

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)); 

} 

Questo codice funziona come previsto. Tuttavia, sto cercando di fare il miglio supplementare ed eseguire il seguente esercizio opzionale:

"Sfida opzionale: è possibile rendere questo metodo più efficiente, quando n è pari, utilizzando x^n = (x^(n/2))^2."

Non sono sicuro di come implementare quell'ultima formula quando n è pari. Non penso di poter usare la ricorsione per quello. Ho cercato di implementare quanto segue, ma non funziona anche perché non riesco a raddoppiare la potenza di un int.

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

Qualcuno può indicarmi la giusta direzione? Mi sento come se mi mancasse qualcosa di ovvio. Tutto l'aiuto è apprezzato.

Answer 1

È esattamente lo stesso principio di x^n == x * (x^(n-1)): inserisci la tua funzione ricorsiva per x^(n/2) e (...)^2, ma assicurarsi che non si inserisce una ricorsione infinita per n == 2 (come 2 è ancora, troppo):

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

in alternativa, si potrebbe utilizzare una variabile intermedia:

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

I' Probabilmente gestisco anche 2 come caso speciale, ed evito le condizioni "e" e la variabile extra:

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. Penso che questo dovrebbe funzionare, troppo :)

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

Quando n è ancora, la formula è esattamente quello che hai scritto: dividere n a due, chiamare power modo ricorsivo, e piazza il risultato.

Quando n è dispari, la formula è un po 'più complessa: sottrarre 1 da n, effettuare una chiamata ricorsiva per n/2, quadrato il risultato, e moltiplicare per x.

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

n/2 tronca il risultato, quindi la sottrazione di 1 non è fatto in modo esplicito. Ecco un'implementazione in 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

Suggerimento: L'operazione ^ non eseguirà l'elevamento a potenza in Java, ma la funzione che ha scritto, power volontà.

Inoltre, non dimenticare che la quadratura di un numero equivale a moltiplicarla da sola. Non è necessaria alcuna chiamata di funzione.

Answer 4

Fare una piccola modifica alla funzione, si riduce il numero di chiamate ricorsive fatto:

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

Dal

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

è possibile aggiungere questa regola al metodo, sia usando il potere funzione che hai scritto, come suggerito da Stefan Haustein, o usando l'operatore di moltiplicazione regolare, poiché sembra che tu sia autorizzato a farlo.

Si noti che non è necessario per entrambi i casi di base n = 1 e n = 0, uno di essi è sufficiente (utilizzare preferibilmente il caso base n = 0, altrimenti il ​​metodo non sarebbe definito per 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)); 
} 

Non è necessario verificare che n> 2 in nessuno dei casi.

Answer 6

Questo mi ricorda che è possibile ottimizzare di più e questo codice seguente.

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) 

quello che è più il risultato intermedio potrebbe essere memorizzato ed evitare il calcolo ridondante.