nが偶数の場合に最適化されたx^nの再帰メソッド

Question

double xと整数nをとり、x^nを返すpowerというJavaを使用して再帰的メソッドを書く必要があります。ここまで私がこれまで持っていたことがあります。

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

} 

このコードは期待どおりに機能します。しかし、私は余分な距離を移動し、次の練習を実行しようとしています。

"任意の課題：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の再帰関数を挿入します。あなたは、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を特殊なケースとして扱い、 "and"条件と余分な変数を避けてください：

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が偶数の場合、式はあなたが書いた正確に何である：、2によってnを分割再帰的powerを呼び出し、その結果を二乗します。

nが奇数である場合、式はもう少し複雑である：nから1を減算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

、それが作られた再帰呼び出しの回数削減します：

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

ので

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

を、あなたの方法には、このルールを追加することができ、いずれかの電源を使用してあなたが書いた関数、Stefan Hausteinが示唆したように、または正規乗算演算子を使用しています。

ベースケースn = 1とn = 0の両方の必要はありません。そのうちの1つで十分です（ベースケース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) 

さらに中間結果を記憶でき、冗長な計算を避けることができます。