[类似MathPow的Java方法，在效率-家庭作业中具有迭代和递归的解决方案

Question

我的作业有问题，需要帮助！

问题1：

完成下面的Java方法，以便raiseToPower（x，n）将数字x提升为整数幂n（即，计算值xn）。请记住，x-n = 1 / xn，并且那个x0 = 1。

您应该以尽可能少的步骤（即以O（log n）时间）进行此操作。

提供非递归（迭代）的解决方案：

这是我的解决方案：

    public static double raiseToPower (double x, int n) {
double res=1;
     boolean neg=false;
     if(n<0)
     {
         neg=true;

     }
     if(n>0)

         for (int i=0;i<n;i++) {
             res = res * x;
         }
             if(neg==true) {
                 n=n*-1;
                 for (int i=0;i<n;i++) {


                     res = res * x;
                 }
                   res=1/res;
             }


             return res;
}

但是这不正确，因为效率不高

这是我的错误，例如：52.49的9的幂可以通过9个步骤解决，但可以通过4个步骤完成89.89至75的幂可以在75个步骤中解决，但可以在7个步骤中完成78.57至63的幂可以通过63个步骤解决，但可以通过6个步骤完成70.17至44的幂可以在44个步骤中解决，但可以在6个步骤中完成]

问题2：

我需要完全像问题1一样写代码，但要递归

这是我的问题：给出一个递归的解决方案：

这是我的代码：

     public static double raiseToPower (double x, int n) {
ouble dev=0.0;
        if (n == 0) {
            return 1;
        } else {
            if (n < 0) {
              double  count= raiseToPower (x, n+1);
                dev=count*x;
                return 1 / raiseToPower (x, -n);
            }
            if (n > 0) {
             double  count= raiseToPower (x, n-1);
             dev=count*x;



            }

        }
        return dev;
}

此代码正确，但效率不高。

例如，这是我的错误：

53.31至44的幂可以通过44个步骤解决，但可以通过6个步骤完成6.90达到74的幂，需要74个步骤，但是可以通过7个步骤完成80.76至76的幂可以通过76个步骤解决，但可以通过7个步骤完成51.44的幂可以通过86个步骤解决，但可以通过7个步骤完成76.26的50的幂可以通过50步解决，但可以通过6步完成63.53至93的幂可以通过93个步骤解决，但可以通过7个步骤完成]

感谢大家帮助和解决这两个问题！

Answer 1

您可以通过分解n的2的幂来计算O（logN）x ^ n，如下所示：

9 = 1 + 8

15 = 1 + 2 + 4 + 8

为了分解n的2的幂，可以使用按位运算符。像这样：n＆pow2表示您要在N和pow2之间进行“与”运算，这意味着如果n具有位1，而pow2也具有该位1，则结果将为非零。因此，我们可以为第一个解决方案编写此代码：

  public static double raiseToPower (double x, int n) {
    double res=1;
    double powx=x;
    int pow2=1;
    boolean neg=false;
    if(n<0)
    {
      neg=true;
      n=n*-1;
    }
    while(n!=0) {
      if((n&pow2)!=0)
      {
        res=res*powx;
        n=n-pow2;
      }
      powx=powx*powx;
      pow2=pow2*2;
    }
    if(neg==true)
      res=1/res;
    return res;
  }