首页 > 试题广场 >

数值的整数次方

[编程题]数值的整数次方
  • 热度指数:825479 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 64M,其他语言128M
  • 算法知识视频讲解
实现函数 double Power(double base, int exponent),求base的exponent次方。

注意:
1.保证base和exponent不同时为0。
2.不得使用库函数,同时不需要考虑大数问题
3.有特殊判题,不用考虑小数点后面0的位数。

数据范围: ,保证最终结果一定满足
进阶:空间复杂度 ,时间复杂度

示例1

输入

2.00000,3

输出

8.00000
示例2

输入

2.10000,3

输出

9.26100
示例3

输入

2.00000,-2

输出

0.25000

说明

2的-2次方等于1/4=0.25    
推荐
    /**
     * 1.全面考察指数的正负、底数是否为零等情况。
     * 2.写出指数的二进制表达,例如13表达为二进制1101。
     * 3.举例:10^1101 = 10^0001*10^0100*10^1000。
     * 4.通过&1和>>1来逐位读取1101,为1时将该位代表的乘数累乘到最终结果。
     */
    public double Power(double base, int n) {
    	double res = 1,curr = base;
    	int exponent;
    	if(n>0){
    		exponent = n;
    	}else if(n<0){
    		if(base==0)
    			throw new RuntimeException("分母不能为0");  
    		exponent = -n;
    	}else{// n==0
    		return 1;// 0的0次方
    	}
    	while(exponent!=0){
			if((exponent&1)==1)
				res*=curr;
			curr*=curr;// 翻倍
			exponent>>=1;// 右移一位
		}
		return n>=0?res:(1/res);        
  	}

编辑于 2015-09-20 14:56:57 回复(142)
python
# -*- coding:utf-8 -*-
class Solution:
    def Power(self, base, exponent):
        result = 1
        if base == 0:
            return 0
        if exponent == 0:
            return 1
        if exponent < 0:
            for i in range(-exponent):
                result = result * base
            return 1/result
        for i in range(exponent):
            result = result * base
        return result
 上面的很简单,没有使用快速幂算法,下面使用一下快速幂算法,快速幂算法参考下面的博客
https://blog.csdn.net/hkdgjqr/article/details/5381028
    def fast_power(self, base, exponent):
        if base == 0:
            return 0 
        if exponent == 0:
            return 1
        e = abs(exponent)
        tmp = base
        res = 1
        while(e > 0):
            #如果最后一位为1,那么给res乘上这一位的结果
            if (e & 1 == 1):
                res =res * tmp
            e = e >> 1
            tmp = tmp * tmp
        return res if exponent > 0 else 1/res
编辑于 2018-03-25 12:01:54 回复(15)
简单快速幂

class Solution {
public:
    double Power(double base, int exponent) {
        long long p = abs((long long)exponent);
    	double r = 1.0;
        while(p){
            if(p & 1) r *= base;
            base *= base;
            p >>= 1;
        }
        return exponent < 0 ? 1/ r : r;
    }
};

编辑于 2016-08-05 19:31:10 回复(51)
java 实现
传统公式求解时间复杂度O(n)
public class Solution {
    public double Power(double base, int exponent) {
        double  result=1;
        for(int i=0;i<Math.abs(exponent);i++){
            result*=base;
        }
        if(exponent<0){
            result=1/result;
        }
        return result;             
  }
} 
递归:n为偶数,a^n=a^n/2*a^n/2;n为奇数,a^n=(a^(n-1)/2)*(a^(n-1/2))*a
时间复杂度O(logn) public class Solution {
    public double Power(double base, int exponent) {
        int n=Math.abs(exponent);
        if(n==0)
            return 1;
        if(n==1)
            return base;
        double  result=Power(base,n>>1);
        result*=result;
        if((n&1)==1)
            result*=base; 
        if(exponent<0)
            result=1/result;
        return result;             
  }
}

结合各位道友的意见,二刷如下
public class Solution {
    public double Power(double base, int exponent) { 
        if(exponent==0 && base != 0)
            return 1;
        if(exponent==1)
            return base;
        if(base == 0 && exponent <= 0){
            throw new RuntimeException();
        }
        if(base ==0 && exponent>0){ 
            return 0;
        }
        int n= exponent;
        if(exponent<0){
            n = -exponent;
        }
        double  result=Power(base,n>>1);
        result*=result;
        if((n&1)==1)
            result*=base; 
        if(exponent<0)
            result=1/result;
        return result;     
  }
}

编辑于 2018-11-14 23:58:38 回复(25)
【分析】
第一种方法:使用递归,时间复杂度O(logn)
  • 当n为偶数,a^n =(a^n/2)*(a^n/2)
  • 当n为奇数,a^n = a^[(n-1)/2] * a^[(n-1)/2] * a
举例:
  • 2^11 = 2^1 * 2^2 * 2^8
  • 2^1011 = 2^0001 * 2^0010 * 2^1000

第二种方法:累乘,时间复杂度为O(n)

【参考代码】
package javaTest;


public class JavaTest {
    public static void main(String[] args) {
    	System.out.println(power(3, 3));
    	System.out.println(powerAnother(3, 3));
    }
    // 使用递归
    public static double power(double base, int exponent) {
    	int n = Math.abs(exponent);
    	double result = 0.0;
    	if (n == 0)
    		return 1.0;
    	if (n == 1)
    		return base;
    	
    	result = power(base, n >> 1);
    	result *= result;
    	if ((n & 1) == 1) // 如果指数n为奇数,则要再乘一次底数base
    		result *= base;
    	if (exponent < 0) // 如果指数为负数,则应该求result的倒数
    		result = 1 / result;
    	
    	return result;
    }
    // 使用累乘
    public static double powerAnother(double base, int exponent) {
    	double result = 1.0;
    	for (int i = 0; i < Math.abs(exponent); i++) {
    		result *= base;
    	}
    	if (exponent >= 0)
    		return result;
    	else
    		return 1 / result;
    }
    
}

编辑于 2016-10-16 21:24:26 回复(9)
/*剑指书中细节:
*1.当底数为0且指数<0时
*会出现对0求倒数的情况,需进行错误处理,设置一个全局变量;
*2.判断底数是否等于0
*由于base为double型,不能直接用==判断
*3.优化求幂函数
*当n为偶数,a^n =(a^n/2)*(a^n/2) 
*当n为奇数,a^n = a^[(n-1)/2] * a^[(n-1)/2] * a 
*时间复杂度O(logn)
*/
public class Solution {  
      boolean invalidInput=false;     
      public double Power(double base, int exponent) {      
        if(equal(base,0.0)&&exponent<0){
            invalidInput=true;
            return 0.0;
        }
        int absexponent=exponent;
        if(exponent<0)
            absexponent=-exponent;
        double res=getPower(base,absexponent);
        if(exponent<0)
            res=1.0/res;
        return res;
  }
    boolean equal(double num1,double num2){
        if(num1-num2>-0.000001&&num1-num2<0.000001)
            return true;
        else
            return false;
    }
    double getPower(double b,int e){
        if(e==0)
            return 1.0;
        if(e==1)
            return b;
        double result=getPower(b,e>>1);
        result*=result;
        if((e&1)==1)
            result*=b;
        return result;
    }
}

编辑于 2017-08-27 09:43:23 回复(5)
两种解法:1.快速幂 2. 递归
//    1.快速幂
   public double Power(double base, int exponent) {
        if (exponent == 0) {
            return 1.0;
        }
        if (base - 0.0 == 0.00001 || base - 0.0 == -0.00001)  {
            if (exponent < 0) {
                throw new RuntimeException("除0异常"); 
            }else{
                return 0.0;
            }
        }
        int e = exponent > 0 ? exponent: -exponent;
        double res = 1;
        while (e != 0) {
            res = (e & 1) != 0 ? res * base : res;
            base *= base;
            e = e >> 1;
        }
        return exponent > 0 ? res : 1/res;
  }

//    2.递归
    public double Power(double base, int exponent) {
        if (exponent == 0) {
            return 1.0;
        }
        if (base - 0.0 == 0.00001 || base - 0.0 == -0.00001)  {
            if (exponent < 0) {
                throw new RuntimeException("除0异常"); 
            }else{
                return 0.0;
            }
        }
        return exponent > 0 ? getPower(base, exponent) : 1/getPower(base, -exponent);
    }
    
    public static double getPower(double base, int e) {
        if (e == 1) {
            return base;
        }
        double halfPower = getPower(base, e >> 1);
        return (e & 1) != 0 ? base * halfPower * halfPower : halfPower * halfPower;
    }


编辑于 2018-03-21 17:09:53 回复(7)
public class Solution {
    public double Power(double base, int exponent) {
        return Math.pow(base, exponent);
  } 
}
我是众大神中一颗随风飘扬的小草
编辑于 2018-04-25 20:56:32 回复(14)
难道只有我一个是Math.pow()吗?
发表于 2018-03-19 08:57:33 回复(12)
0^0 和 0^(-4) 在到底是如何定义的?
wiki百科:0的0次幂和0的负次幂在数学是都是没有定义的。
已无力吐槽……
发表于 2015-04-14 21:22:23 回复(7)
class Solution {
public:
    double Power(double base, int exponent) {
        
        if(exponent == 0) return 1;
        if(base == 0) return 0;
        if(exponent == 1) 
    		return base;
        else if(exponent == -1)
            return 1/base;
        return Power(base,exponent/2) * Power(base,exponent/2) * Power(base,exponent%2);
    }
};
exponent == 0 而 base 也 == 0 时竟然返回1,醉了
发表于 2015-09-04 14:40:07 回复(7)

JavaScript
方法一:调用系统函数

function Power(base, exponent) {
    return Math.pow(base, exponent);
}

方法二:暴力,速度慢;

function Power(base, exponent) {
    var result = 1;
    if (base == 0 && exponent < 0) {
        throw new Error('输入错误');
    }
    for (var i = 0; i < Math.abs(exponent); i++) {
        result *= base;
    }
    return exponent > 0 ? result : 1 / result;
}

方法三:简单快速幂
思路:https://blog.csdn.net/hkdgjqr/article/details/5381028

function Power(base, exponent) {
    var result = 1;
    if (base == 0 && exponent < 0) {
        throw new Error('输入错误');
    }
    var exp = Math.abs(exponent);
    while (exp != 0) {
        if ((exp & 1) == 1) {
            result *= base;
        }
        base *= base; // 翻倍
        exp >>= 1; // 右移 
    }
    return exponent > 0 ? result : 1 / result;
}
发表于 2019-05-12 16:05:51 回复(2)

用递归来处理很简单,主要注意的是分为两种情况来讨论,一种是指数exponent>=0的情况,一种是exponent<0的情况,后者只需要简单的处理下,让其变为倒数就可以了,代码如下:

class Solution{
    public double Power(double base, int exponent) {
        double res=0;
        if (exponent>=0)
        res=way(base,exponent);
        else {
            res=way(base,-exponent);
            res=1/res;
        }
        return res;
    }
    private double way(double base,int n){
        if (n==0)
            return 1;
        else
            return base*way(base,n-1);
    }
}
发表于 2018-09-11 16:57:37 回复(1)
不知道这样对不对?
public class Solution {
    public double Power(double base, int exponent) {
        return Math.pow(base,exponent);
  }
}
发表于 2015-09-29 19:56:28 回复(26)
return Math.pow(base,exponent);
编辑于 2015-10-02 22:37:05 回复(14)
# -*- coding:utf-8 -*-
class Solution:
    def Power(self, base, exponent):
        # write code here
        return base ** exponent

发表于 2016-04-05 12:34:29 回复(6)
class Solution {
public:
    double Power(double base, int exponent) {
        if(exponent == 0) return 1;
        double ret = pow(Power(base, abs(exponent)/2), 2);
    	if(abs(exponent)%2 == 1) 
            ret *= base;
        return exponent < 0 ? 1/ret : ret;
    }
};

发表于 2017-07-16 15:14:19 回复(0)
public class Solution {
    public double Power(double base, int exponent) {
        
       //  return Math.pow(base,exponent);
        
      double result=0.0; 
    	
        if(base==0&&exponent<0){
            return 0.0;
        }
        if(exponent>=0){
           result = zhengshu(base,exponent);
        }else{
        	result = 1.0/zhengshu(base,-exponent);
        }     
         return result;  
  }
    
    
       public static double zhengshu(double base, int exponent){
    	
        if(exponent==0){
            return 1;
        }
        if(exponent==1){
            return base;
        }
        
        double r=zhengshu(base,exponent>>1);
        r*=r;
        if((exponent&1)==1){
            r*=base;
        } 
        
    	return r;
    }
}

发表于 2016-03-04 15:21:45 回复(1)
最佳答案,没有之一。java代码,已经运行通过所有测试用例。思路如下:还是那句老话,算法的本质就是模拟数学规律,我们可以先模拟一下幂运算就是乘法的连乘,那么用算法写出来,然后再考虑几个测试用例的极端情况,如exponent==0或者exponent<0的情况,然后按逻辑写出你的代码就好了,不要把他想的有多难,羞愧是负能量最高的能量场。
public class Solution {
    public double Power(double base, int exponent) {
        if(exponent == 0){
            return 1;
        }else if(exponent > 0){
            double num = base;
            for(int i = 1; i < exponent; i++){
                num = num * base;
            }
            return num;
        }else {
            double nums = base;
            int flag = -exponent;
            for(int i = 1; i < flag; i++){
                nums = nums * base;
            }
            return 1/nums;
        }
  }
}
编辑于 2015-08-27 20:33:45 回复(23)

class Solution {

public:

    double Power(double base, int exponent) {

     double res;

 

     res = pow(base,exponent);

     return res;

   好流氓啊

发表于 2019-07-31 18:43:03 回复(0)
class Solution {
public:
    //主要考察点:
    //1指数为负责的情况;
    //2递归实现快速乘方;
    double Power(double base, int exponent)
    {
        if(abs(base) < 0.00000000001)//base为0的情况考虑
            return 0;
        bool neg = false;
        if(exponent < 0)
        {
            exponent = -exponent;
            neg = true;
        }
        double ret = Power_Help(base, exponent);
        if(neg)
            ret = 1.0 / ret;
        return ret;
    }
    double Power_Help(double base, unsigned exponent)
    {
        if(exponent == 0)
            return 1;
        if(exponent == 1)
            return base;
        double ret = Power_Help(base, exponent >> 1);
        ret = ret * ret;
        //if(exponent & 1 == 1) 判断奇偶数更高效
        if(exponent % 2 == 1)//容易遗漏:指数为奇数,少乘一次base,补上
            ret = ret * base;
        return ret;
    }
};

发表于 2017-10-09 19:53:03 回复(1)

问题信息

难度:
1577条回答 163433浏览

热门推荐

通过挑战的用户

查看代码