题解 | #数值的整数次方#

数值的整数次方

http://www.nowcoder.com/practice/1a834e5e3e1a4b7ba251417554e07c00

描述

这是一篇面对初级coder的题解。
知识点：数学常识快速幂递归
难度：一星

题解

题目：

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

保证base和exponent不同时为0。不得使用库函数，同时不需要考虑大数问题，也不用考虑小数点后面0的位数。

即求：浮点数的整数次方

首先补充一些数学上的基础知识：

a0=1 任何数的0次方得1

m-n=(1/m)一个数的负数次方就是一个数的正数次方的倒数

故有下面的预处理函数：

    if(exponent==0)
        return 1;
    if(exponent<0)
    {
        base=1/base;
        exponent=-exponent;
    }

方法一：暴力求解

按照乘方的定义就是连续n个数相乘

class Solution {
public:
    double Power(double base, int exponent) {
    if(exponent==0)
        return 1;
    if(exponent<0)
    {
        base=1/base;
        exponent=-exponent;
    }
     double answer=1 ;//连乘 故初始化为1
     for(int i=0; i<exponent;i++)
         answer*=base;
    return answer;
    }
};

运行时间： 8 ms 占用内存：520K

显然，这样执行效率不高其他语言也类似需要更好的方法

时间复杂度O(n)

方法二：递归分治的思想

基于的原理如下若n为偶数 a^n=a^(n/2)*a^(n/2) 若n为奇数 a^n=a^(n/2)*a^(n/2)*a 注意此处的除法为整除之所以不用除法是为了提高效率

class Solution {
public:
    double Power(double base, int exponent) {
    if(exponent==0)
        return 1;
    if(exponent<0)
    {
        base=1/base;
        exponent=-exponent;
    }
    return Dpower(base,exponent);
    }
    double Dpower(double b, int n) {
        if (n == 1) 
            return b;
        double ret = Dpower(b, n/2);
        if (n&1)  // 奇数
            return ret * ret * b;
        else 
            return ret * ret;
    }
};

递归受递归深度限制，同时大家知道，递归虽然简洁，但会产生额外的空间开销。我们可以把递归改写为循环，来避免对栈空间的大量占用

运行时间： 4 ms 占用内存：524K

时间复杂度：O(logn)，每次规模减少一半

空间复杂度：O(logn)，递归栈，因为要记住logn个变量

方法三：快速幂

本质上采用了数的二进制表示方法如求7的10次方，但这次，我们把10写成二进制的形式，也就是 1010 即10=0*2^0+1*2^1+0*2^2+1*2^3 考虑a(m+n)=am*an 7^10=7^2^1+7^2^3

class Solution {
public:
    double Power(double base, int exponent) {
    if(exponent==0)
        return 1;
    if(exponent<0)
    {
        base=1/base;
        exponent=-exponent;
    }
    double answer = 1;
    while(exponent){
        if(exponent&1)        //如果n的当前末位为1
            answer *= base;  //ans乘上当前的a
        base *= base;        //a自乘
        exponent >>= 1;       //n往右移一位
    }
    return answer;
    }
};

运行时间： 4 ms 占用内存：512K

时间复杂度：O(logn)，因为n的二进制位个数为logn

空间复杂度：O(1)

参考《STL源码剖析》中 Pow函数在STL中的实现——方法是类似的

templateinline T identity_element(plus){
	return T(0);
}
 
templateinline T identity_element(multiplies){
	return T(1);
}
 
templateinline T power_this(T x, Integer n){
	return power_this(x, n, multiplies());
}
 
templateT power_this(T x, Integer n, MonoidOperation op){
	if (n == 0)
		return identity_element(op);
	else{
		while ((n & 1) == 0){
			n >>= 1;
			x = op(x, x);
		}
		T result = x;
		n >>= 1;
		while (n != 0){
			x = op(x, x);
			if ((n & 1) != 0)
				result = op(result, x);
			n >>= 1;
		}
		return result;
	}
}

identity_element(op)为取“证同元素”。所谓“运算op的证同元素”，意思是数值A若与该元素做op运算，会得到A自己。加法的证同元素为0，因为任何元素加上0仍为自己。乘法的证同元素为1，因为任何元素乘以1仍为自己。