Java метод, такой как MathPow, с решением, повторяющимся и рекурсивным по эффективности - домашняя работа - PullRequest
Новая
       10

Java метод, такой как MathPow, с решением, повторяющимся и рекурсивным по эффективности - домашняя работа

0 голосов
/ 09 апреля 2020

У меня проблема с домашним заданием, и мне нужна помощь, пожалуйста!

Вопрос 1:

Выполните нижеприведенные методы Java, чтобы поднять ToTower (x, n) увеличит число x до целой степени n (то есть для вычисления значения xn). Помните, что xn = 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 шагов

Примечание: не должно быть используется в методе java .lang.MathPow

Вопрос 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, решаемой за 86 шагов , но это можно было сделать за 7 шагов 76.26 до степени 50, решенной за 50 шагов, но это можно было сделать за 6 шагов 63.53 до степени 93, решенной за 93 шага, но это можно было сделать за 7 шагов

Примечание: нельзя использовать в методе java .lang.MathPow

Спасибо всем за помощь и решение обеих проблем !!!

Ответы [ 2 ]

1 голос
/ 09 апреля 2020

Вы можете вычислить в O (logN) x ^ n, разбив n на 2 степени, например:

9 = 1 + 8

15 = 1 + 2 + 4 + 8

Следовательно, x ^ 9 = (x ^ 1) * (x ^ 8).

Чтобы разбить n на 2 степени, вы можете использовать побитовые операторы. Например, n & pow2 будет означать, что вы выполняете операцию «И» между N и pow2, что означает, что если n имеет бит 1, а pow2 также имеет этот бит 1, результат будет ненулевым. Учитывая, что pow2 должен иметь один бит 1 (это степень 2), вы можете в основном проверять каждый бит n. Таким образом, вы разбиваете n на степени 2, и вы можете просто держать приставку вокруг, что означает x ^ (pow2), когда вы проходите по степеням 2, а затем умножать ее на res, когда вы обнаружите, что n действительно состоит из эта степень 2.

Таким образом, мы можем сделать этот код для первого решения: 

  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;
  }

Вот еще статьи о побитовых операторах: https://www.tutorialspoint.com/java/java_basic_operators.htm

Аналогично, вы можете изменить рекурсивный код, чтобы получить его в O (logN).

Вот рекурсивный код: 


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

    if (n == 0) return 1;
    if (n % 2 == 0)
    {
      res= raiseToPower(x, n / 2);
      res=res*res;
    }
    else
    {
      res= x * raiseToPower(x, n - 1);
    }
    if(!neg)
      return res;
    return 1/res;
}
0 голосов
/ 09 апреля 2020 
public class ExponentialCalculator {

    public static void main(String[] args) {
        double x = 2;
        int n = -4;
        System.out.println(raiseToPower(x, n));
    }

    //Divide and Conquer method
    public static double raiseToPower (double x, int n) {
        if(n==0) {
            return 1;
        }
        double temp = raiseToPower(x, n/2) * raiseToPower(x, n/2);
        if(n%2==0) {
            return n > 0 ? temp: 1/temp;    
        }
        else {
            return n > 0 ? x * temp: 1/(x * temp);
        }
    }
}


результат 0,0625

Журнал сложности (n)

...