幂函数c语⾔递归算法，使⽤递归的幂函数
⼩编典典
让我们从⼀些数学事实开始：
对于正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)。
所有这些的结论是：
为了获得O(log n)，我们需要递归，该递归在每个步骤上只占n的⼀部分，⽽不只是n-1或n-任何东西。
但是，这只是故事的⼀部分。我们需要注意不要多次调⽤递归，因为在⼀个步骤中使⽤多个递归调⽤会创建指数复杂度，⽽使⽤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
递归函数c语言规则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; }
}
2020-11-13

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。