C++如何实现n次方？ |21xrx.com

C++如何实现n次方？

2023-06-28 20:19:56 深夜i -- --

C++ n次方实现

在C++编程语言中，求解一个数的n次方是一个非常基本的数学操作。在本篇文章中，我们将介绍C++中如何实现n次方。

一、普通算法

最基本的方法就是通过循环计算，每次乘上这个数本身，每次乘n-1次。


double power(double x, int n)
{
  double ans = 1.0;
  for (int i = 0; i < n; i++)
  {
    ans *= x;
  }
  return ans;
}

二、快速幂算法

普通算法的时间复杂度为O(n)。当n比较大时，这个算法会非常慢。因此，这里介绍一种时间复杂度为O(logn)的算法——快速幂算法。

快速幂算法是运用分治思想的算法。将底数不断地平方，将指数不断地除以2，直到指数为0时终止循环。在这个过程中，如果指数为奇数，就将结果乘上底数。

对于正整数指数，可以通过以下代码实现：


double power(double x, int n)
{
  if (n == 0) return 1;
  double t = power(x, n / 2);
  if (n % 2) return x * t * t;
  else return t * t;
}

这个算法的递归深度为O(logn)，因此时间复杂度为O(logn)。

三、快速幂算法的优化

在上面的快速幂算法实现中，每次递归都需要重新求底数的平方，这会造成一定的时间浪费。为了避免这种情况，可以通过循环来实现快速幂算法的优化。

普通版循环代码：


double pow(double x, int n) {
  double res = 1;
  while(n) {
    if(n & 1) {
      res *= x;
    }
    x *= x;
    n >>= 1;
  }
  return res;
}

位运算：

`n & 1` 等价于 `n % 2`，但是位运算比取模运算快得多。

`n >>= 1` 等价于 `n /= 2`。位运算的效率也要比除法高得多。

优化版循环代码：


double power(double x, int n) {
  if(n < 0) x = 1 / x, n = -n;
  double ans = 1;
  while(n) {
    if(n & 1) ans *= x;
    x *= x;
    n >>= 1;
  }
  return ans;
}

以上就是C++实现n次方的两种方法——普通算法和快速幂算法的讲解。对于不同的操作, 选择不同的C++实现方法,能够有效地提高程序的效率，提升编程体验。

上一篇: idea打包java可执行jar包

下一篇: 如何在c++中打出箭头符号

评论区

()

相似文章