java - Java中使用递归的幂函数

Question

我正在尝试完成我的 Java 类的作业，我们将在其中创建一种求解幂的有效方法(将底数转换为指数，由用户输入定义)。

我几乎已准备就绪，但有效的方法 pow2 无法正确处理奇数指数。它比预期的多乘以基数。我在这里缺少什么？

例如，如果我输入 4 作为基数，输入 5 作为 exp，程序将输出 4096 而不是 1024。

import java.util.Scanner;

public class MyPow {


    public static int countGbl = 0;


    public static double raise(double base, int exp) {

        double b = base;

        for (int i = 1; i < exp; i++){
            countGbl += 1;
            base = base * b;
        }

        return base;
    }


    public static double pow1(double base, int exp) {

        if (base == 0.0) return Double.POSITIVE_INFINITY;
        else if (base == 0.0 && exp >= 0) return 0.0;
        else if (exp == 1) return base;
        else if (base > 0 && exp == 0) return 1.0;
        else{
            if (exp < 0){
                base = 1.0/base;
                exp = -exp;
            }

            if (exp % 2 == 0){
                countGbl++;
                return pow1(base, exp/2) * pow1(base, exp/2);
            }
            else {
                countGbl += 2;
                return pow1(base, exp/2) * pow1(base, exp/2) * base;
            }
        }
    }


    public static double pow2(double base, int exp) {
        double temp = raise(base, exp/2);
        double retval = temp*temp;
        if (exp % 2 == 1){
            countGbl++;
            retval *= temp;
        }
        return retval;
        }





    public static void main(String[] args) {

        Scanner s = new Scanner(System.in);

        System.out.println("Enter base: ");
        double base = Integer.parseInt(s.nextLine());
        System.out.println("Enter exp: ");
        int exp = Integer.parseInt(s.nextLine());

        System.out.println(pow2(base, exp));
        System.out.println(countGbl);

    }
}

仅供引用，pow1 方法的原因是因为我们要编写一个不如 pow2 高效的示例方法。

此外，请忽略 countGbl。我们的教授希望我们计算在方法调用期间完成的乘法次数。

Answer 1

看起来您正在尝试进行优化:

基数^exp = 基数^exp/2 * 基数^exp/2 * 基数

其中exp是奇数，exp/2是Java的整数除法，其实也是数学中的floor函数。

但是，在奇怪的情况下，您所做的是乘以 temp 的另一个因子，它已经被计算为 base^exp/2。

将 retVal 乘以 base，而不是 temp。 pow2

的变化

retval *= temp;

到

retval *= base;

此外，另一个优化是在pow2中将exp除以2之后返回到raise方法，你可以继续使用递归，重复调用 pow2 直到达到指数为 1 或 0 的基本情况。