Java 使用递归的幂函数

Question

提问by dEv93

I have to write a power method in Java. It receives two ints and it doesn't matter if they are positive or negative numbers. It should have complexity of O(logN). It also must use recursion. My current code gets two numbers but the result I keep outputting is zero, and I can't figure out why.

我必须用 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

采纳答案by RealSkeptic

Let's start with some math facts:

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

For a positive n, a? = a?a?…?a n times
For a negative n, a? = ?a?? = ?(a?a?…?a). This means acannot be zero.
For n = 0, a? = 1, even if ais zero or negative.

对于正 n，a? = a?a?…?an 次
对于负 n，a? =？一个？？= ?(a?a?…?a)。这意味着a不能为零。
对于 n = 0，a? = 1，即使a为零或负数。

So let's start from the positive n case, and work from there.

所以让我们从正 n 的情况开始，然后从那里开始工作。

Since we want our solution to be recursive, we have to find a way to define a? based on a smaller n, and work from there. The usual way people think of recursion is to try to find a solution for n-1, and work from there.

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

And indeed, since it's mathematically true that a? = a?(a??1), the naive approach would be very similar to what you created:

事实上，因为在数学上是正确的 a? = a?(a??1)，简单的方法与您创建的方法非常相似：

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

However, the complexity of this is O(n). Why? Because For n=0 it doesn't do any multiplications. For n=1, it does one multiplication. For n=2, it calls pow(a,1) which we know is one multiplication, and multiplies it once, so we have two multiplications. There is one multiplication in every recursion step, and there are n steps. So It's O(n).

然而，这的复杂度是 O(n)。为什么？因为对于 n=0 它不做任何乘法运算。对于 n=1，它进行一次乘法运算。对于 n=2，它调用 pow(a,1)，我们知道它是一次乘法，然后乘以一次，所以我们有两次乘法。每个递归步骤有一个乘法，有n个步骤。所以是 O(n)。

In order to make this O(log n), we need every step to be applied to a fractionof n rather than just n-1. Here again, there is a math fact that can help us: a^n?+n?= a^n??a^n?.

为了使这个 O(log n)，我们需要将每一步都应用于n 的一小部分，而不仅仅是 n-1。再一次，有一个数学事实可以帮助我们：a ^n?+n?= ^n?? ^n?.

This means that we can calculate a? as a^n/2?a^n/2.

这意味着我们可以计算 a? 作为^n/2?a ^n/2。

But what happens if n is odd? something like a? will be a^4.5?a^4.5. But we are talking about integer powers here. Handling fractions is a whole different thing. Luckily, we can just formulate that as a?a??a?.

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

So, for an even number use a^n/2?a^n/2, and for an odd number, use a? a^n/2?a^n/2(integer division, giving us 9/2 = 4).

因此，对于偶数，使用^n/2?a ^n/2，对于奇数，使用 a? a ^n/2?a ^n/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 );
    }
}

This actually gives us the right results (for a positive n, that is). But in fact, the complexity here is, again, O(n) rather than O(log n). Why? Because we're calculating the powers twice. Meaning that we actually call it 4 times at the next level, 8 times at the next level, and so on. The number of recursion steps is exponential, so this cancels out with the supposed saving that we did by dividing n by two.

这实际上为我们提供了正确的结果（即对于正 n）。但实际上，这里的复杂性再次是 O(n) 而不是 O(log n)。为什么？因为我们要计算两次幂。这意味着我们实际上在下一级别调用它 4 次，在下一级别调用 8 次，依此类推。递归步骤的数量是指数级的，因此这与我们通过将 n 除以 2 所做的假设节省相抵消。

But in fact, only a small correction is needed:

但实际上，只需要一个小小的修正：

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

In this version, we are calling the recursion only once. So we get from, say, a power of 64, very quickly through 32, 16, 8, 4, 2, 1 and done. Only one or two multiplications at each step, and there are only six steps. This is O(log n).

在这个版本中，我们只调用一次递归。所以我们从 64 的幂中得到，非常快地通过 32、16、8、4、2、1 并完成。每一步只有一两次乘法，而且只有六步。这是 O(log n)。

The conclusion from all this is:

这一切的结论是：

To get an O(log n), we need recursion that works on a fraction of n at each step rather than just n - 1 or n - anything.
But the fraction is only part of the story. We need to be careful not to call the recursion more than once, because using several recursive calls in one step creates exponential complexity that cancels out with using a fraction of n.

为了获得 O(log n)，我们需要在每一步处理 n 的一小部分的递归，而不仅仅是 n - 1 或 n - 任何东西。
但分数只是故事的一部分。我们需要注意不要多次调用递归，因为在一个步骤中使用多个递归调用会产生指数复杂性，而使用 n 的一小部分会抵消这种复杂性。

Finally, we are ready to take care of the negative numbers. We simply have to get the reciprocal ?a??. There are two important things to notice:

最后，我们准备好处理负数。我们只需要得到倒数?a??。有两个重要的事情需要注意：

Don't allow division by zero. That is, if you got a=0, you should not perform the calculation. In Java, we throw an exception in such a case. The most appropriate ready-made exception is IllegalArgumentException. It's a RuntimeException, so you don't need to add a throwsclause to your method. It would be good if you either caught it or prevented such a situation from happening, in your mainmethod when you read in the arguments.
You can't return an integer anymore (in fact, we should have used long, because we run into integer overflow for pretty low powers with int) - because the result may be fractional.

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

So we define the method so that it returns double. Which means we also have to fix the type of powerOfHalfN. And here is the result:

所以我们定义了这个方法，让它返回双精度值。这意味着我们还必须修复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;
        }
    }
}

Note that the part that handles a negative n is only used in the top level of the recursion. Once we call pow()recursively, it's always with positive numbers and the sign doesn't change until it reaches 0.

请注意，处理负 n 的部分仅用于递归的顶层。一旦我们pow()递归调用，它总是带有正数，并且符号在达到 0 之前不会改变。

That should be an adequate solution to your exercise. However, personally I don't like the ifthere at the end, so here is another version. Can you tell why this is doing the same?

这应该是您锻炼的适当解决方案。但是，我个人不喜欢最后的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;
    }
}

Answer 2

回答by Chiron

pay attention to :

注意：

float result = 0;

and

和

result = result * pow( a, n+1);

That's why you got a zero result. And instead it's suggested to work like this:

这就是你得到零结果的原因。相反，建议这样工作：

result = a * pow( a, n+1);

Answer 3

回答by Eran

Beside the error of initializing resultto 0, there are some other issues :

除了初始化result为 0的错误之外，还有一些其他问题：

Your calculation for negative nis wrong. Remember that a^n == 1/(a^(-n)).
If n is not integer, the calculation is much more complicated and you don't support it. I won't be surprised if you are not required to support it.
In order to achieve O(log n)performance, you should use a divide and conquer strategy. i.e. a^n == a^(n/2)*a^(n/2).

你对负数的计算n是错误的。请记住a^n == 1/(a^(-n))。
如果 n 不是整数，则计算复杂得多，您不支持它。如果您不需要支持它，我不会感到惊讶。
为了实现O(log n)性能，您应该使用分而治之的策略。即a^n == a^(n/2)*a^(n/2)。

Answer 4

回答by Serge Ballesta

A good rule is to get away from the keyboard until the algorythm is ready. What you did is obviously O(n).

一个好的规则是在算法准备好之前远离键盘。你所做的显然是 O(n)。

As Eran suggested, to get a O(log(n)) complexity, you have to divide n by 2 at each iteration.

正如 Eran 所建议的，要获得 O(log(n)) 复杂度，您必须在每次迭代时将 n 除以 2。

End conditions :

结束条件：

n == 0 => 1
n == 1 => a

n == 0 => 1
n == 1 => 一个

Special case :

特例：

n < 0 => 1. / pow(a, -n) // note the 1. to get a double ...

n < 0 => 1. / pow(a, -n) // 注意 1. 得到一个 double ...

Normal case :

正常情况：

m = n /2
result = pow(a, n)
result = resul * resul // avoid to compute twice
if n is odd (n % 2 != 0) => resul *= a

m = n /2
结果 = pow(a, n)
result = resul * resul // 避免计算两次
如果 n 是奇数 (n % 2 != 0) => 结果 *= a

This algorythm is in O(log(n)) - It's up to you to write correct java code from it

该算法在 O(log(n)) 中 - 由您来编写正确的 Java 代码

But as you were told : n mustbe integer (negative of positive ok, but integer)

但正如你被告知的： n必须是整数（正数的负数，但整数）

Answer 5

回答by Jameson

Here is a much less confusing way of doing it, at least if your not worred about the extra multiplications. :

这是一种不那么令人困惑的方法，至少如果您不担心额外的乘法。：

public static double pow(int base,int exponent) {
        if (exponent == 0) {
            return 1;
        }
        if (exponent < 0) {
            return 1 / pow(base, -exponent);
        }
        else {
            double results = base * pow(base, exponent - 1);
            return results;
        }
    }

Answer 6

回答by malik arman

import java.io.*;
import java.util.*;
public class CandidateCode {
    public static void main(String args[] ) throws Exception {

    Scanner sc = new Scanner(System.in);
    int m = sc.nextInt();
    int n = sc. nextInt();
     int result = power(m,n);
     System.out.println(result);
    }
     public static int power(int m, int n){
         if(n!=0)
            return (m*power(m,n-1));
        else 
            return 1;
     }

}

Answer 7

回答by Milze

try this:

尝试这个：

    public int powerN(int base, int n) {return n == 0 ? 1 : (n == 1 ? base : base*(powerN(base,n-1)));

Answer 8

回答by Debaditya M

# a pow n = a pow n%2 * square(a) pow(n//2)
# a pow -n = (1/a) pow n
from math import inf
def powofn(a, n):
    if n == 0:
        return 1
    elif n == 1:
        return a
    elif n < 0:
        if a == 0 : return inf
        return powofn(1/a, -n)
    else:
        return powofn(a, n%2) * powofn(a*a, n//2)

Java 使用递归的幂函数

提问by dEv93

采纳答案by RealSkeptic

回答by Chiron

回答by Eran

回答by Serge Ballesta

回答by Jameson

回答by malik arman

回答by Milze

回答by Debaditya M

相关推荐

最近更新

标签

Java 使用递归的幂函数

提问by dEv93

采纳答案by RealSkeptic

回答by Chiron

回答by Eran

回答by Serge Ballesta

回答by Jameson

回答by malik arman

回答by Milze

回答by Debaditya M

相关推荐

Java 无法设置访客内存“android_arm”：参数无效

Java 在 Fragment 中显示 RecyclerView

Java 如何获取 Spring Boot 和 OAuth2 示例以使用默认密码以外的密码授予凭据

Java 在并发线程中操作`values()`和`put()`时如何避免HashMap“ConcurrentModificationException”？

相关推荐

最近更新

标签