使用递归的幂函数

Question

我必须用Java编写幂方法。它接收两个整数，无论​​它们是正数还是负数都没有关系。它应该具有的复杂度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

让我们从一些数学事实开始：

• 对于正n，aⁿ=a⨯a⨯…⨯an次
• 对于负数n，aⁿ=⅟a⁻ⁿ=⅟（a⨯a⨯…⨯a）。这意味着 a 不能为零。
• 对于n = 0，即使 a 为零或负，aⁿ= 1 。

因此，让我们从n个正数开始，然后从那里开始。

因为我们希望我们的解决方案是递归的，所以我们必须找到一种方法来基于较小的n定义aⁿ，然后从那里开始。人们通常认为递归的方法是尝试找到n-1的解，然后从那里开始工作。

实际上，由于a since =a⨯（aⁿ⁻¹）在数学上是正确的，因此幼稚的方法将与您创建的方法非常相似：

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

但是，其复杂度为O（n）。为什么？因为对于n = 0，它不做任何乘法。对于n = 1，它执行一次乘法。对于n =
2，它调用pow（a，1），我们知道它是一个乘法，并将其相乘一次，所以我们有两个乘法。在每个递归步骤中都有一个乘法，有n个步骤。所以是O（n）。

为了使这个O（log n），我们需要将每个步骤应用于n 的 一部分 ，而不仅仅是n-1。在这里，有一个数学的事实，可以帮助我们：一个N 1 + N
2 = A 区N1 ⨯a 氮气。

这意味着我们可以将aⁿ计算为n / 2⨯an / 2。

但是，如果n为奇数会怎样？像a⁹将是一个4.5 ⨯a
4.5。但是我们在这里谈论整数幂。处理分数是完全不同的事情。幸运的是，我们可以将其表述为a⨯a⁴⨯a⁴。

因此，对于偶数，使用n / 2⨯an / 2；对于奇数，使用a⨯a n / 2⨯an / 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除以2来实现的节省被抵消。

但实际上，只需要进行一些小的更正：

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（log n），我们需要递归，该递归在每个步骤上只占n的一部分，而不只是n-1或n-任何东西。
2. 但是，这只是故事的一部分。我们需要注意不要多次调用递归，因为在一个步骤中使用多个递归调用会创建指数复杂度，而使用n的分数会抵消该复杂度。

最后，我们准备好处理负数。我们只需要得到倒数⅟a⁻ⁿ。有两件事要注意：

• 不允许被零除。也就是说，如果a == 0，则不应执行计算。在Java中，在这种情况下会引发异常。最合适的现成异常是IllegalArgumentException。这是RuntimeException，因此您无需在方法中添加throws子句。main读参数时，如果在方法中捕获了它或阻止了这种情况的发生，那将是很好的。
• 您无法再返回整数（实际上，我们应该使用long，因为使用会以很低的幂遇到整数溢出int）-因为结果可能是分数。

因此，我们定义该方法，使其返回double。这意味着我们还必须修复的类型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;
        }
    }
}

请注意，处理负数n的部分仅在递归的顶层使用。一旦我们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;
    }
}