c ++中整数的幂

Question

我需要从pow(a,b)整数中得到结果(a和b都是整数).目前(int) pow( (double)a, (double)b)包含的计算是错误的.也许有人可以帮助一个函数,用整数执行pow(a,b)并返回一个整数？

但这里有一个奇怪的部分:我使用Geany(和g ++/gcc编译器)在Linux中创建了我的脚本,并且只pow(a,b)编译了脚本并且工作正常.但在大学里我有Dev-C++(和MS Windows).在Dev-C++中,脚本没有使用错误[Warning] converting toint' 编译double'

我需要在Windows(和Mingw编译器)下使这个scrpit工作.

提前致谢,

-skazhy

Answer 1

比Zed更好的递归方法,不知道为什么你失败如此封闭的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).我应该补充一点,这真是一个经典......

Answer 2

或者你可以使用一点点的模板元编程:)

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),因为评估将在编译时进行.当然,这只适用于整数值.但是,此功能仅用于完整性(和乐趣).

Answer 3

主要是回复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结构.

顺便提一下,这是基于我在实际代码中所做的事情 - 在递归期间计划的数据结构操作,但在递归到达根/叶之前,原始节点中没有任何改变,所需的所有新节点都已成功分配,获得所有锁,并且没有任何改变可以使情况恶化.此时,通过该链接的计划实例列表进行迭代以提交更改 - 逻辑作为迭代更清晰,而不是分解为与递归调用的展开相关的片段.

这里的要点显然不是声称递归是自动坏的.当人们似乎假设递归优于默认的迭代时,它只会让我感到紧张.

Answer 4

二进制幂，又名平方取幂。

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

请注意，这对于 powi(0,0) 返回 1。

Answer 5

我假设你的家庭作业是写一个积分指数函数。首先，看看什么是指数：

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

然后，查看您的教科书，了解如何在 C 中将数字相乘。您将需要使用for循环。

Answer 6

您可以展示一个很好的递归方法：

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