剑指offer 13：数值的整数次方

题目描述

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

保证base和exponent不同时为0

问题分析

计算一个浮点数的整数次方，主要考察的是对输入数据的完整性的预估能力。针对此问题，输入数据可能存在以下情况：

1.底数不为0，指数都为整数

2.底数不为0，指数都为负数

3.底数为0，指数为负数（出现零除情况）

4.底数为0，指数为正数（给定特殊值0或1）

代码实现的逻辑并不复杂，主要是需要考虑到所有可能存在的输入情况，同时需要注意，对于浮点数，是不可以直接使用“==”直接对两数进行比较的。

下面给出C++代码实现：

class Solution {

public:

    double Power(double base, int exponent) {//排除零除的情况出现

        if(std::abs(base-0.0)<(1e-) && exponent<){return 0.0;

        }

        bool isnegative=(exponent<)? true:false;

        if(isnegative){

          return 1.0/calc_power(base,-exponent);

        }

        else{

            return calc_power(base,exponent);

        }

    }

    double calc_power(double base,int unsignedexp){

        double res=1.0;

        for (int i=;i<unsignedexp;i++){

            res*=base;

        }

        return res;

    }
　　　　

};

如果希望提高 calc_power函数的计算效率，可以使用如下递归的实现方法，时间复杂度从O(n)降到O(logn),但栈递归的空间复杂度也变为O(logn)

double calc_power(double base,int unsignedexp){

        //log(n)时间复杂度，同样递归深度也为log(n)

        if (unsignedexp==){

            return 1.0;

        }

        if (unsignedexp==){

            return base;

        }

        double result = calc_power(base, unsignedexp>>);

        result*=result;

        if((unsignedexp & 0x1)==){

            result*=base;

        }

        return result;

    }

巴特西

剑指offer 13：数值的整数次方

题目描述

问题分析

最新文章

热门文章