当n为偶数时针对x ^ n优化的递归方法

Question

我需要编写一个使用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是偶数时,我不确定如何实现最后一个公式.我不认为我可以使用递归.我试图实现以下内容,但它也不起作用,因为我不能把一个双倍的功能.

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

PS我认为这也应该有用:)

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是偶数,公式正是你所写的:除以n2,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;
    }
}

演示.

Answer 3

提示:该^操作不会在Java中执行求幂,但是您编写的函数power将会执行.

另外,不要忘记平方数字与单独乘以它相同.无需功能调用.

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

Answer 5

以来

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

您可以使用您编写的幂函数将此规则添加到您的方法中,如Stefan Haustein建议的那样,或使用常规乘法运算符,因为您似乎可以这样做.

注意,不需要基本情况​​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.