Мощность целого числа в С++

Ответ 1

Хороший рекурсивный подход, который вы можете показать:

int myPow(int x, int p) {
  if (p == 0) return 1;
  if (p == 1) return x;
  return x * myPow(x, p-1);
}

Ответ 2

Лучше рекурсивный подход, чем Zed's, не знаю, почему вы так закрылись Zed: x

int myPow(int x, int p)
{
  if (p == 0) return 1;
  if (p == 1) return x;

  int tmp = myPow(x, p/2);
  if (p%2 == 0) return tmp * tmp;
  else return x * tmp * tmp;
}

Намного сложнее там O (log² (p)) вместо O (p). Я должен добавить, что это действительно классика...

Ответ 3

Или вы могли бы использовать небольшой метапрограммирование шаблона:)

template<int X, int P>
struct Pow
{
    enum { result = X*Pow<X,P-1>::result };
};
template<int X>
struct Pow<X,0>
{
    enum { result = 1 };
};
template<int X>
struct Pow<X,1>
{
    enum { result = X };
};

int main()
{
    std::cout << "pow(3,7) is " << Pow<3,7>::result << std::endl;
    return 0;   
}

Этот код имеет лучшую сложность, O (1), потому что оценка будет выполняться во время компиляции. Конечно, это будет работать только с целыми значениями. Однако эта функция предоставляется только для полноты (и забавы).

Ответ 4

В основном в ответ на простую рекурсию Zeds...

Почему рекурсия считается лучше, чем итерация? Особенно в С++. Что случилось с...

int myPow (int x, int p) {
  int i = 1;
  for (int j = 1; j <= p; j++)  i *= x;
  return i;
}

Я не говорю, что ваш ответ неправильный или каким-то образом хуже - это просто, что у меня сложилось впечатление, что вы считаете это хорошим, потому что оно рекурсивно. ИМО, особенно на C++, что смещение может привести к медленным и даже сломанным программам. Медленные программы, потому что вы выращиваете огромный стек, вызывая кэш и виртуальную память. Сломанные программы, потому что вы получаете переполнение стека, где будет работать итерационное решение.

Некоторые будут смотреть на ваш ответ и считать хвост рекурсивным и в любом случае будут оптимизированы на итерации. Конечно, это не так - после выхода каждого рекурсивного вызова есть еще много раз, чтобы сделать, поэтому он не является хвостом рекурсивным. Дело в том, что на С++ существует много более тонких вещей, которые предотвращают оптимизацию хвостовых рекурсий - даже если компилятор их вообще делает. Например...

void myrecurse (plan *p)
{
  plan i;
  i.prev = p;
  //  more plan setup, checks, and special case handling

  myrecurse (&i);
}

В этом случае все экземпляры "плана" должны оставаться в стеке. Поэтому фреймы стека нельзя отбрасывать. Поэтому это не оптимизируется в итерации, хотя после рекурсивного вызова выполняются точно нулевые операции. Даже не скрытые операции, такие как очистка деструкторов, поскольку предполагается, что план является структурой POD.

Кстати, это основано на том, что я сделал в реальном коде - операции структуры данных, которая запланирована во время рекурсии, но в исходных узлах ничего не меняется до тех пор, пока рекурсия не достигнет корня/листа, все необходимые новые узлы были успешно распределены, все блокировки были приобретены, и нет никаких изменений, чтобы ухудшиться. В этот момент итерация выполняется через связанный список экземпляров плана для фиксации изменений - логика была более ясной как итерация, чем разбита на фрагменты, относящиеся к разворачиванию рекурсивных вызовов.

Здесь, очевидно, не следует утверждать, что рекурсия автоматически плоха. Это просто заставляет меня нервничать, когда люди, похоже, считают, что рекурсия лучше, чем итерация по умолчанию.

Ответ 5

Я предполагаю, что ваше домашнее задание - написать интегральную функцию экспоненты. Во-первых, посмотрите, что такое показатель:

http://en.wikipedia.org/wiki/Exponent

Затем загляните в учебник, чтобы умножить числа на C. Вы хотите использовать цикл for.

Ответ 6

Не лучше ли была бы функция хвостохранилища? Что-то вроде:

int myPow_helper(int x, int p, int result) {
   if (p == 0) {
      return result;
   } else {
      return myPow_helper(x, p-1, result*x);
   }
}

int myPow(int x, int p) {
   return myPow_helper(x, p, 1);
}

Ответ 7

Вместо того, чтобы вставлять double в int в строке (int) pow((double)a, (double)b), попробуйте округлить результаты pow, а затем при необходимости переведите в int.

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

Ответ 8

Стандарт С++ не имеет int pow(int, int) (он имеет double pow(double, int), float ...). Microsoft cmath использует C math.h, который не имеет ipow. Некоторые заголовки cmath определяют версию шаблона pow.

$ cat main.cpp
#include <cmath>

int main() {
  std::pow(2,2);
}

$ gcc main.cpp # this cmath has template pow
...snip... std::pow<int, int>(int, int)]+0x16): undefined reference to `pow'
collect2: ld returned 1 exit status
1 ;( [email protected]:
$ gcc main.cpp -lm

Найдите : ipow lang: С++ в Google Code.

Здесь пример из первой ссылки:

template <typename Type1, typename Type2>
Type1 ipow(Type1 a, Type2 ex)
// Return a**ex
{
    if ( 0==ex )  return 1;
    else
    {
        Type1 z = a;
        Type1 y = 1;
        while ( 1 )
        {
            if ( ex & 1 )  y *= z;
            ex /= 2;
            if ( 0==ex )  break;
            z *= z;
        }
        return y;
    }
}

См. вычисление целых степеней (квадратов, кубов и т.д.) в коде С++.

Ответ 9

Двоичное питание, aka возведения в степень возведения в квадрат.

int powi (int base, unsigned int exp)
{
    int res = 1;
    while (exp) {
        if (exp & 1)
            res *= base;
        exp >>= 1;
        base *= base;
    }
    return res;
}

Обратите внимание, что это возвращает 1 для powi (0,0).

Ответ 10

Почему линейно? Попробуйте это логарифмически!!

long long powx( int val, int exp )
{
    long long actual = val;
    long long prod = 1;
    int i;

    for ( i = 0; i < 32; i++ )
    { 
        if ( exp & 0x1 )
        {
            prod *= actual;
        }

        exp >>= 1;

        actual *= actual;
    }

    return prod;
}

Ответ 11

Здесь есть две альтернативы: когда мы хотим подсчитать мощность (a, n), мы можем написать код, который очень короткий и работает в O (logn), но рекурсивно и поэтому требует создания нового стекового кадра для каждого вызова и требуется немного больше времени, чем повторение цикла. Таким образом, короткий код:

int power(int a, int n){
    if(n == 0) return 1;
    int keep = power(a,n/2);
    if(n & 1) return keep*keep*a;   // (n & 1) is and operation of 1 and the 
    return keep*keep;               // last bit of n
}

а для более быстрого кода здесь используется цикл while:

int power(int a, int n) {
    int res = 1;
    while (n) {
        if (n & 1)
            res *= a;
        a *= a;
        n >>= 1;
    }
    return res;
}