питание целого числа в C++ [дубликат]

Рекурсивный подход лучше, чем у Зеда.

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).

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

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) , потому что оценка будет происходить при компиляции время. Конечно, это будет работать только с целыми числами. Однако эта функция предоставляется только для полноты (и развлечения).

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

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

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

Не лучше ли использовать хвостовую рекурсивную функцию? Примерно так:

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

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

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

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

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

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.

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

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

В стандарте C ++ нет int pow (int, int) (Он имеет double pow (double, int) , float ... ). Cmath Microsoft использует 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 ;( user@host:
$ gcc main.cpp -lm

Найдите функцию : ipow lang: c ++ в 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;
    }
}

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