Блог

Главная - Вопросы по программированию - как запомнить мой код для нахождения степени числа

как запомнить мой код для нахождения степени числа

#c #algorithm #recursion

#c #алгоритм #рекурсия

Вопрос:

Я пытаюсь найти мощность числа, используя рекурсию, но в моем дереве рекурсии много повторений. Пожалуйста, помогите мне, как я могу использовать запоминание в своем коде, чтобы повысить эффективность моего кода.

 double myPow(double x, int n) {
        if(n==0)
            return 1;
        if(n==-1)
            return 1/x;
        if(n==1)
            return x;
        if(n%2==0)
            return myPow(x,n/2)*myPow(x,n/2);
        else
            if(n>0)
                return myPow(x,n/2)*myPow(x,n/2 1);
            else
                return myPow(x,n/2)*myPow(x,n/2-1);
    }

**Constraints:**

-100.0 < x < 100.0
-2^31 <= n <= 2^31-1
-10^4 <= x^n <= 10^4

Комментарии:

1. в вашем коде есть два вида чрезмерных повторений. Один предназначен для одного вызова, например myPow(3.141,20) , другой для нескольких вызовов. Первое вы можете легко выполнить, в то время как второе у меня есть сомнения, стоит ли это усилий. Какой из них вас беспокоит?

2. Будет действительно полезно, если вы сообщите им обоим.

Ответ №1:

Я обычно использую один из двух подходов для решения подобной проблемы.

  1. Передайте по карте в параметр кэша-> пары результатов
  2. Рекурсия вверх, это обычно может привести к одной «строке» рекурсивных вызовов, а не к ветвлению.

Для 1 вы можете изменить свой код следующим образом:

 double myPow(double x, int n, map<int, double> amp;cache) {
    if(n==0)
        return 1;
    if(n==-1)
        return 1/x;
    if(n==1)
        return x;
    auto it = cache.find(n);
    if(it != cache.end()){
        return it->second;
    }
    double result = 0;
    if(n%2==0)
        result = myPow(x,n/2)*myPow(x,n/2);
    else
        if(n>0)
            result = myPow(x,n/2)*myPow(x,n/2 1);
        else
            result = myPow(x,n/2)*myPow(x,n/2-1);

    cache.emplace(n,result);
    return resu<
}

Для подхода 2 вы можете начать вычисления при n = 1 и выполнить рекурсию вверх до переданного параметра.

Комментарии:

1. Я что-то здесь упускаю или кэш не должен быть больше похож map<pair<int, double>, double> , потому что кэшированное значение зависит как от экспоненты n , так и от основания x ? Кажется, что ваш кеш учитывает только показатель степени.

2. действительно, ваш кеш предназначен только для экспоненты. И это не нужно, если вы измените result = myPow(x,n/2)*myPow(x,n/2) значение на temp = myPow(x,n/2); result = temp*temp; (плюс позаботитесь о четных нечетных случаях)

3. @Striezel, да, я бы создал оболочку, в которой я объявил карту, а затем передал ее для этой конкретной базы. Конечно, можно кэшировать пару, но вероятность попадания в кэш при удвоении очень низкая.