使用递归的幂函数

我必须用Java编写一个power方法。 它接收两个整数，如果它们是正数或负数则无关紧要。 它应该具有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); } return result; } } 

Answer 1

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

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

让我们从积极的n案例开始，并从那里开始工作。

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

事实上，由于a mat =a⨯（aⁿ-1）在数学上是正确的，所以天真的方法与你创造的方法非常相似：

 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。 在这里，有一个数学事实可以帮助我们：a ^{n 1 + n 2} = a ^{n 1} a a ^{n 2} 。

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

但如果n是奇数，会发生什么？ 像a⁹这样的东西将是4.5⨯a4.5。 但我们在这里讨论整数权力。 处理分数是完全不同的事情。 幸运的是，我们可以将其表述为a⨯a⁴⨯a⁴。

因此，对于偶数使用^{n /} 2⨯an ^{/ 2} ，对于奇数，使用a⨯an ^/ 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，16,8,4,2,1和非常快速地获得64的幂。 每一步只有一到两次乘法，而且只有六个步骤。 这是O（log n）。

所有这些的结论是：

1. 为了得到一个O（log n），我们需要递归，它在每一步上只有n的一小部分，而不仅仅是n – 1或n – 任何东西。
2. 但这一部分只是故事的一部分。 我们需要注意不要多次调用递归，因为在一个步骤中使用几个递归调用会产生指数复杂性，使用一小部分n取消。

最后，我们准备好照顾负数。 我们只需得到倒数⅟a – ⁿ。 有两件重要的事情需要注意：

• 不允许除以零。 也就是说，如果你得到a = 0，你不应该执行计算。 在Java中，我们在这种情况下抛出exception。 最合适的现成例外是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之前不会改变。

这应该是你锻炼的适当解决方案。 但是，我个人不喜欢最后的那个，所以这里是另一个版本。 你能说出为什么这样做吗？

 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

注意：

 float result = 0; 

和

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

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

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

Answer 3

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

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

Answer 4

一个好的规则是远离键盘，直到algorythm准备好。 你做了什么显然是O（n）。

正如Eran建议的那样，为了获得O（log（n））复杂度，你必须在每次迭代时将n除以2。

结束条件：

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

特殊情况 ：

• n <0 => 1. / pow（a，-n）//注意1.获得双倍…

正常情况：

• m = n / 2
• result = pow（a，n）
• result = resul * resul //避免计算两次
• 如果n是奇数（n％2！= 0）=>结果* = a

这个algorythm在O（log（n））中 – 由你自己编写正确的java代码

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

Answer 5

这是一个不那么容易混淆的方式，至少如果你不担心额外的乘法。 ：

 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

 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

试试这个：

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