首页 > 试题广场 >

数值的整数次方

[编程题]数值的整数次方

热度指数：831150 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

实现函数 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

    /**
     * 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号

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)

简单快速幂

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

【分析】

第一种方法：使用递归，时间复杂度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给我，我要回家

两种解法：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

难道只有我一个是Math.pow()吗？

发表于 2018-03-19 08:57:33 回复(12)

lijian430421

0^0 和 0^(-4) 在到底是如何定义的？
wiki百科：0的0次幂和0的负次幂在数学是都是没有定义的。
已无力吐槽……

发表于 2015-04-14 21:22:23 回复(7)

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〗

用递归来处理很简单，主要注意的是分为两种情况来讨论，一种是指数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

不知道这样对不对？

public class Solution {
public double Power(double base, int exponent) {
return Math.pow(base,exponent);
}
}

发表于 2015-09-29 19:56:28 回复(26)

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

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菜鸡弟弟


	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

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条回答 2248收藏 168634浏览

通过挑战的用户

查看代码

Cpp_Noob

2022-09-16 11:03:28
杜小康康

2022-09-16 10:59:09
西门_无惧

2022-09-16 10:12:49
牛客66488...

2022-09-16 10:11:42
bhmzzz

2022-09-16 09:35:01

数值的整数次方

输入

输出

输入

输出

输入

输出

说明

问题信息

热门推荐

通过挑战的用户

相关试题