数值的整数次方 - 快速幂

た入场券 2022-11-21 03:44 194阅读 0赞

## 数值的整数次方 ##

实现函数double Power(double base, int exponent)，求base的exponent次方。不得使用库函数，同时不需要考虑大数问题。

**示例 1:**

> 输入: 2.00000, 10  
> 输出: 1024.00000

**示例 2:**

> 输入: 2.10000, 3  
> 输出: 9.26100

**示例 3:**

> 输入: 2.00000, -2  
> 输出: 0.25000  
> 解释: 2-2 = 1/22 = 1/4 = 0.25

**说明:  
\-100.0 < x < 100.0  
n 是 32 位有符号整数，其数值范围是 \[−231, 231 − 1\] 。**

--------------------

## 解法 ##

> amazing：x = x \* x

double myPow(double x, int n){ 
        //快速幂
        long long b;
        if(n < 0){ 
            x = 1.0/x;
            //可能会超出int型
            b = n;
            b = -b;
        }else{ 
            b = n;
        }
        int i;
        double sum = 1.0;
        //快速幂
        while(b){ 
            if(b&1){ 
                sum *= x; // k是当前所在二进制位置(从0开始)，某个值 = x^2^k
            }
            x = x*x;
            b>>=1;
        }
        return sum;
    }

## 超时代码 ##

没有考虑到递归的深度  
有递归时，考虑：

*  是否会超时
 *  是否会陷入死循环
 *  从问题的角度考虑，是否可以再优化

#include<stdio.h>
    double pow_value(double x, int n){ 
        //求x的n次方
        if(n == 0){ 
            return 1;
        }
        if(n == 1){ 
            return x;
        }
        return pow_value(x, n/2) * pow_value(x, (n - n/2));
    }
    
    double myPow(double x, int n){ 
        //快速幂
        long b;
        if(n < 0){ 
            x = 1.0/x;
            //可能会超出int型
            b = n;
            b = -b;
        }else{ 
            b = n;
        }
        int i, k = 0;
        int sum = 1;
        //快速幂
        while(b){ 
            if(b&1){ 
                sum *= pow_value(x, (1<<k)); //k是当前所在二进制位置(从0开始)，某个值 = x^2^k
            }
            k++;
            b>>=1;
        }
        return sum;
    }
    int main(){ 
        double x = myPow(0.00001,2147483647);
        printf("%f", x);
    }