c - 递归求幂

Question

所以我必须编写一个递归算法来求幂，我必须使用它来使算法更快:然后我必须弄清楚发生了多少次乘法。我写了它，但我不确定我是否正确 - 我还需要一些帮助来计算乘法部分。

#include <stdio.h>
#include <math.h>

double intpower(double x, int n)
{
    double result;
    if(n>1&&n%2!=0) {result=x*intpower(x,(n-1)/2)*intpower(x,(n-1)/2);}
    if(n>1&&n%2==0) {result=intpower(x,n/2)*intpower(x,n/2);}
    if(n==1) return x;
    else return result;
}


int main()
{
    int n;
    double x,result;
    printf("x\n");
    scanf("%lf", &x);
    printf("n\n");
    scanf("%d", &n);
    printf("result = %.2f\n", intpower(x,n));


    return 0;
}

Answer 1

归纳定义是说

1. 如果 k 是偶数，则 x^k = [ x^(k/2) ] ^ 2
2. 如果 k 是奇数，则 x^k = x * [ x^(floor(k)/2) ] ^ 2

通过这些可以更容易地了解如何安排递归:

#include <stdio.h>

double int_pwr(double x, unsigned k)
{
  if (k == 0) return 1;
  if (k == 1) return x;  // This line can be omitted.
  double y = int_pwr(x, k/2);
  return (k & 1) ? x * y * y : y * y;
}

int main(void)
{
  double x;
  unsigned k;
  scanf("%lf%u", &x, &k);
  printf("x^k=%lg\n", int_pwr(x, k));
  return 0;
}

我已将类型更改为更符合逻辑，并通过在每个级别进行两次递归调用来节省 OP 解决方案所完成的指数级(以 k 为单位)的工作量。

关于乘法的次数，很容易看出，如果k的最高位是2^p(即位置p)，那么你需要p次乘法重复平方。另一种说法是 p = floor(log_2(k))。例如，如果 k=4=2^2，您将平方平方得到答案:2 次乘法。此外，您还需要 q-1，其中 q 是 k 的二进制表示中 1 的数量。这是“奇数”检查为真的次数。 IE。如果 k = 5(有 2 位为 1)，您将对平方进行平方，然后再将结果乘以 x 一次。总而言之，乘法次数为 p + q - 1，其中 p 和 q 的定义如上。