21

我需要从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'

我也需要让这个脚本在 Windows(和 Mingw 编译器)下工作。

4

11 回答 11

68

比 Zed 更好的递归方法。

int myPow(int x, unsigned 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) 的复杂度要好得多。

或者作为constexpr使用 c++17 的函数。

template <unsigned int p>
int constexpr IntPower(const int x)
{
  if constexpr (p == 0) return 1;
  if constexpr (p == 1) return x;

  int tmp = IntPower<p / 2>(x);
  if constexpr ((p % 2) == 0) { return tmp * tmp; }
  else { return x * tmp * tmp; }
}
于 2009-10-01T18:53:36.227 回答
21

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

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),因为评估将在编译时进行。当然,这只适用于整数值。然而,这个功能只是为了完整性(和乐趣)而提供的。

于 2009-10-01T22:30:47.037 回答
15

主要是为了回复 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);
}

在这种情况下,所有“计划”实例必须保留在堆栈中。因此,堆栈帧不能被丢弃。因此,这在迭代中是不可优化的,即使在递归调用之后执行的操作恰好为零。甚至没有像析构函数清理这样的隐藏操作,因为 plan 被假定为 POD 结构。

顺便说一句,这是基于我在真实代码中所做的事情 - 在递归期间计划的数据结构操作,但在递归到达根/叶之前,原始节点中没有任何变化,所有需要的新节点都已成功分配,获得所有锁,并且没有更糟的破坏。那时,通过计划实例的链接列表完成迭代以提交更改 - 作为迭代的逻辑比分解为与递归调用的展开相关的片段更清晰。

这里的重点显然不是声称递归是自动坏的。当人们似乎默认递归比迭代更好时,这让我感到紧张。

于 2009-10-02T01:27:39.830 回答
5

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

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

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

于 2009-10-01T18:37:14.153 回答
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。

于 2013-07-06T15:13:02.220 回答
3

尾递归函数不是最好的吗?就像是:

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);
}
于 2009-10-01T22:55:08.353 回答
2

与其将 double 类型转换为 int,(int) pow((double)a, (double)b)不如尝试将 pow 的结果四舍五入,然后在必要时将其转换为 int。

当您截断时,这可能是浮点问题之一,尤其是当您的结果相差 1 时。

于 2009-10-01T18:45:22.740 回答
2

C++ 标准没有int pow(int, int)(它有double pow(double, int), float ...)。微软的 cmath 使用没有 ipow 的 C math.h。一些 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

在 Google Code 上搜索function:ipow lang:c++ 。

这是第一个链接的示例:

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++ 代码中计算整数幂(平方、立方等)

于 2009-10-01T21:03:19.913 回答
0

为什么是线性的?试试对数!!

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;
}
于 2013-05-27T02:46:01.327 回答
0

这里有两种选择,当我们想要计算 power(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;
}
于 2015-03-22T21:00:58.043 回答
-10

一个不错的递归方法,你可以炫耀:

int myPow(int x, int p) {
  if (p == 0) return 1;
  if (p == 1) return x;
  return x * myPow(x, p-1);
}
于 2009-10-01T18:44:43.193 回答