使用递归的幂函数

Question

我必须用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);
        } 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ⁿ=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.在这里,有一个数学的事实,可以帮助我们:一个^{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⨯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中,我们在这种情况下抛出异常.最合适的现成例外是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;
    }
}