首页 > 试题广场 >

数值的整数次方

[编程题]数值的整数次方
  • 热度指数：828827 时间限制：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
算法知识视频讲解
添加回答
推荐
nailperry头像 nailperry 
    /**
     * 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
牛客104285号头像 牛客104285号
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)
马客(Mark)头像 马客(Mark)
简单快速幂 

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)
Java
FantasyLin头像 FantasyLin
【分析】
第一种方法：使用递归，时间复杂度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)
offer给我，我要回家头像 offer给我，我要回家
两种解法：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)
freeshi头像 freeshi
难道只有我一个是Math.pow()吗？
发表于 2018-03-19 08:57:33 回复(12)
lijian430421头像 lijian430421
0^0 和 0^(-4) 在到底是如何定义的？
wiki百科：0的0次幂和0的负次幂在数学是都是没有定义的。
已无力吐槽……
发表于 2015-04-14 21:22:23 回复(7)
datong头像 datong 
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
一只骑单车的猫头像 一只骑单车的猫

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)
『FinalFantasy〗头像 『FinalFantasy〗

用递归来处理很简单，主要注意的是分为两种情况来讨论，一种是指数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)
root0头像 root0
不知道这样对不对？
public class Solution {
    public double Power(double base, int exponent) {
        return Math.pow(base,exponent);
  }
}
发表于 2015-09-29 19:56:28 回复(26)
CF_浩哥头像 CF_浩哥 
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)
drdr头像 drdr 
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)
QT菜鸡弟弟头像 QT菜鸡弟弟 

	class Solution {





	public:





	    double Power(double base, int exponent) {





	     double res;





	 





	     res = pow(base,exponent);





	     return res;





	   好流氓啊
发表于 2019-07-31 18:43:03 回复(0)
牛客吴彦祖QAQ头像 牛客吴彦祖QAQ 
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条回答 164792浏览

热门推荐

通过挑战的用户

查看代码

相关试题

数值的整数次方

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号