(原) 剑指offer--之数值的整数次方

题目描述

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

初次看题觉得这题好简单，直接用库函数power（）不就行了，仔细想了想，万一不让用库函数呢于是就自己实现了一个power()函数，

愚笨的脑子只考虑了一下几点

1：base == 0,直接return 0

2：base ！=0，但exponent == 0时，return 1

3：base != 0,exponent < 0时，求exponent绝对值，再求base 的exponent次方，然后返回其倒数

4：base != 0,exponent > 0时，求base的exponent次方，

c++代码

#include <iostream>
using namespace std;
class Solution {
public:
    double Power(double base, int exponent) {
        double result = 1.0;
        if (base == 0) return 0.0;
        else if (base != 0 && exponent == 0){
            return 1.0;
        }
        
        else if (exponent < 0){
            exponent = -exponent;
            for (int i = 0; i < exponent; ++i)
                result  *= base;
            return 1.0 / result;        }
        else{
            for (int i = 0; i < exponent; ++i)
                result *= base;
            return (double)result;
        }
    }
};

int main(){
    Solution su;
    double base;
    int exponent;
    while (true){
        scanf("%lf%d", &base, &exponent);
        printf ("%lf",su.Power(base, exponent));
    }
}

找来原书看了之后，好吧我承认我智商太低。

关于代码的完整性：

1：满足基本需求。

2：对一些极端值要考虑到，比如一些边界值。

3：对一些错误输入，有相应的处理方法。

4：最好考虑到算法的效率。

下面是按着原书方法又实现了一次

全面低效的方法：

#include <iostream>
using namespace std;

bool InvalidInput = false;

bool equal(double val1, double val2)
{
    if((val1 - val2 < 0.0000001) && (val1 - val2 > -0.0000001))
        return true;
    else
        return false;
}

double Power(double val, int exponent)
{
    InvalidInput = false;
    if(equal(val, 0.0) && exponent < 0)
    {
        InvalidInput = true;
        return 0.0;
    }
    int absExponent = (unsigned int)(exponent);
    double rev = 1.0;
    if(exponent < 0)
        absExponent = (unsigned int)(-exponent);
    for(int i = 0; i < absExponent; ++i)
        rev *= val;
    if(exponent < 0)
        return 1.0 / rev;
    else
        return rev;
}

高效的方法：原书是这样描述的：

如果exponent = 32,按照上述方法我们要循环31次乘法，

而如果我们知道了base 的16次方可以直接平方就得到了base的32次方

同理在8次方的基础上求16次方很容易用递归实现。

double powerwithunsign(double base, int exponent){
    if (exponent == 0) return 1;
    if (exponent == 1) return base;
    double result = powerwithunsign(base, exponent>>2);
    result *= result;
    if ((exponent & 0x1) == 1)
        result *= base;
    return result;
}

(原) 剑指offer--之数值的整数次方

题目描述

推荐阅读