Сила целого числа в с ++
Мне нужно получить результат от pow(a,b) как целое число (и a, и b тоже целые числа). В настоящее время расчеты где (int) pow( (double)a, (double)b) включено неправильно. Может быть, кто-то может помочь с функцией, которая делает pow(a,b) с целыми числами и возвращает целое число тоже?
Но вот странная часть: я сделал свой скрипт в Linux с помощью Geany (и компилятора g++/gcc) и имел только pow(a,b) скрипт скомпилирован и работал нормально. Но в университете у меня есть Dev-C++ (и MS Windows). В Dev-C++ скрипт не компилировался с ошибкой [Warning] converting toint 'от double'
Мне нужно, чтобы этот scrpit работал под Windows (и компилятором Mingw).
Заранее спасибо,
-skazhy
11 ответов
Хороший рекурсивный подход, который вы можете продемонстрировать:
int myPow(int x, int p) {
if (p == 0) return 1;
if (p == 1) return x;
return x * myPow(x, p-1);
}
Лучший рекурсивный подход, чем у Зеда, не знаю, почему вы потерпели неудачу, так замкнулся Зед: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). Я должен добавить, что это действительно классика...
Или вы можете использовать небольшой шаблон метапрограммирования:)
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), потому что оценка будет происходить во время компиляции. Конечно, это будет работать только с целочисленными значениями. Однако эта функция предназначена только для полноты (и развлечения).
В основном в ответ на Zeds простая рекурсия...
Почему рекурсия считается лучше, чем итерация? Особенно в C++. Что случилось с...
int myPow (int x, int p) {
int i = 1;
for (int j = 1; j <= p; j++) i *= x;
return i;
}
Я не говорю, что ваш ответ неверен или, в любом случае, хуже - просто у меня сложилось впечатление, что вы думаете, что это хорошо, потому что это рекурсивно. IMO, особенно в C++, это смещение может привести к медленным и даже сломанным программам. Медленные программы, потому что вы наращиваете огромный стек, вызывая кеш и подкачку виртуальной памяти Сломанные программы, потому что вы получаете переполнение стека, где будет работать итеративное решение.
Некоторые смотрят на ваш ответ и думают, что он хвостовой рекурсивен и все равно будет оптимизирован для итерации. Конечно, это не так - после выхода из каждого рекурсивного вызова необходимо выполнить умножение, поэтому оно не является хвостовым рекурсивным. Дело в том, что в C++ есть много более тонких вещей, которые препятствуют оптимизации хвостовой рекурсии - даже если компилятор делает это вообще. Например...
void myrecurse (plan *p)
{
plan i;
i.prev = p;
// more plan setup, checks, and special case handling
myrecurse (&i);
}
В этом случае все "плановые" экземпляры должны оставаться в стеке. Следовательно, стековые кадры не могут быть отброшены. Следовательно, это невозможно оптимизировать в итерацию, даже если после рекурсивного вызова выполняется ровно ноль операций. Даже не скрытые операции, такие как очистка деструктора, так как план считается структурой POD.
Между прочим, это основано на том, что я сделал в реальном коде - операции со структурой данных, запланированной во время рекурсии, но ничего не изменилось в исходных узлах, пока рекурсия не достигнет корня / листа, все необходимые новые узлы были успешно завершены выделены, все замки приобретены, и нет никаких затруднений, чтобы сделать хуже. В этот момент выполняется итерация по этому связанному списку экземпляров плана для фиксации изменений - логика была более понятной как итерация, чем разбита на фрагменты, относящиеся к раскрутке рекурсивных вызовов.
Суть здесь, очевидно, не в том, чтобы утверждать, что рекурсия автоматически плоха. Я просто нервничаю, когда люди считают, что рекурсия лучше, чем итерация по умолчанию.
Двоичное питание, также известное как возведение в квадрат.
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).
Я предполагаю, что ваше домашнее задание состоит в том, чтобы написать интегральную функцию экспоненты. Сначала взглянем на показатель степени:
http://en.wikipedia.org/wiki/Exponent
Затем посмотрите в своем учебнике, как умножать числа в C. Вы захотите использовать for петля.
Разве хвостовая рекурсивная функция не будет лучшей? Что-то вроде:
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);
}
Стандарт 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++.
Вместо того, чтобы бросать двойку в int в (int) pow((double)a, (double)b) line, попробуйте округлить результаты pow, а затем приведите к int, если это необходимо.
Вероятно, это одна из тех проблем с плавающей запятой, когда вы усекаете, особенно если ваш результат выключен на единицу.
Почему линейно? Попробуйте это логарифмически!!
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;
}
Здесь есть две альтернативы: когда мы хотим подсчитать мощность (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;
}