【剑指Offer】T16 数值的整数次方

给定一个 double 类型的浮点数 base 和 int 类型的整数 exponent。求 base 的 exponent 次方。

  1. 直接想到的方法:

    double Power(double base, int exponent) {
        double result = 1.0;
        for(int i = 1; i <= exponent; i++){
            result*=base;
        }
        return result;
    }

    缺陷:没考虑指数正负、底数为 0 的情况

  2. 考虑边界值

    double Power(double base, int exponent) {
        if(equal(base, 0.0)){
            return 0.0;
        }
        
        unsigned int unsignedExponent = (unsigned int)(exponent);
        if(exponent < 0){
            unsignedExponent = (unsigned int)(-exponent);
        }
        
        double result = 1.0;
        for(int i = 1; i <= unsignedExponent; i++){
            result*=base;
        }
        
        if(exponent < 0){
            return 1.0/result;
        }
        
        return result;
    }
  3. 优解:如果求 32 次方,知道 16 次方的基础上,可以直接对 16 次方进行平方,减少计算次数。类似递归中的斐波那契数列,有如下公式:

$$ a^n =\begin{cases} a^{n/2} \times a^{n/2},n 为偶数 \\ a^{(n-1)/2} \times a^{(n-1)/2},n 为奇数 \end{cases} $$

double PowerWithUnsignedExponent(double base, unsigned int exponent);

double Power(double base, int exponent)
{
    g_InvalidInput = false;

    if (equal(base, 0.0) && exponent < 0)
    {
        g_InvalidInput = true;
        return 0.0;
    }

    unsigned int absExponent = (unsigned int) (exponent);
    if (exponent < 0)
        absExponent = (unsigned int) (-exponent);

    double result = PowerWithUnsignedExponent(base, absExponent);
    if (exponent < 0)
        result = 1.0 / result;

    return result;
}

double PowerWithUnsignedExponent(double base, unsigned int exponent)
{
    if (exponent == 0)
        return 1;
    if (exponent == 1)
        return base;

    double result = PowerWithUnsignedExponent(base, exponent >> 1);
    result *= result;
    if ((exponent & 0x1) == 1)
        result *= base;

    return result;
}

本文链接:https://ariser.cn/index.php/archives/157/
本站文章采用 知识共享署名4.0 国际许可协议进行许可,请在转载时注明出处及本声明!