剑指offer编程题Java实现——面试题11数值的整数次方

题目:

实现函数double power(double base,int exponent),求base的exponent次方。不得使用库函数,同时不需要考虑大数问题。

解题思路:最一般的方法实现数值的n次方就是将一个数自身连乘n次
底数要考虑到正数、负数和零的情况
指数要考虑到正整数,负整数和零的情况。可能的情况有九种,其中尤其要注意底数为0,指数为负数的情况下是无意义的,因此要做特殊处理
指数为负数的乘方运算,可先按照指数为正求得,然后求倒数得到真正结果
解法一:全面不高效,考虑到所有边界条件和负面测试使用循环计算乘方
解法二:全面高效完美的算法,使用公式,利用递归实现,减少计算次数

a^n=a^(n/2)*a^(n/2)    n是偶數

a^n=a^(n/2)*a^(n/2)&a   n是奇数

 package Solution;
/**
* 剑指offer面试题11:数值的整数次方
* 题目:实现函数double power(double base,int exponent),求base的exponent次方。
* 不得使用库函数,同时不需要考虑大数问题。
* 解题思路:实现数值的n次方就是将一个数自身连乘n次
* 底数要考虑到正数、负数和零的情况
* 指数要考虑到正整数,负整数和零的情况。因此可能的情况有九种,其中尤其要注意底数为0,指数为负数的情况下是无意义的,因此要做特殊处理
* 指数为负数的乘方运算,可先按照指数为正求得,然后求倒数得到真正结果
* 解法一:全面不高效,考虑到所有边界条件和负面测试
* 解法二:全面高效完美的算法,使用公式a^n=a^(n/2)*a^(n/2) n是偶數
* a^(n/2)*a^(n/2)&a n是奇数
* @author GL
*
*/
public class No11Power { public static void main(String[] args) {
System.out.println("底数为2,指数为2运算结果为:"+power(2,2));
System.out.println("底数为2,指数为-2运算结果为:"+power(2,-2));
System.out.println("底数为2,指数为0运算结果为:"+power(2,0));
System.out.println("底数为-2,指数为2运算结果为:"+power(-2,2));
System.out.println("底数为-2,指数为-2运算结果为:"+power(-2,-2));
System.out.println("底数为-2,指数为0运算结果为:"+power(-2,0));
System.out.println("底数为0,指数为2运算结果为:"+power(0,2));
System.out.println("底数为0,指数为0运算结果为:"+power(0,0));
System.out.println("底数为2,指数为1运算结果为:"+power(2,1));
System.out.println("底数为0,指数为-2运算结果为:"+power(0,-2));
} public static double power(double base,int exponent){
if(equal(base,0.0)&&exponent<0)
throw new RuntimeException("while exponent is minus,the base can't be zero");
int absExponent=exponent;
if(exponent<0)
absExponent=~exponent+1;//整数按位取反+1得到他的相反数
//double result=powerWithUnsignedExponent(base,absExponent);
double result= powerWithUnsignedExponentByRecursion( base, absExponent);
if(exponent<0)
result=1.0/result;
return result;
}
//解法一:求指数为非负数时候的乘方运算,连乘
private static double powerWithUnsignedExponent(double base, int absExponent) {
double result=1.0;
for(int i=1;i<=absExponent;i++){
result=result*base;
}
return result;
} //解法二:计算一个数的乘方的时候,通过计算指数的一半次,得到的结果相乘即可得到,这样计算量会大大减少
private static double powerWithUnsignedExponentByRecursion(double base,int exponent){
if(exponent==0)
return 1.0;
if(exponent==1)
return base;
double result= powerWithUnsignedExponentByRecursion(base,exponent>>1);
result=result*result;
if((exponent&0x1)==1)
result=result*base;
return result;
} //浮点数由于精度问题不能用==判断是否想等,如果两数满足一定条件精度,可以看做相等
private static boolean equal(double number1,double number2){
if(number1-number2>-0.0000001&&(number1-number2)<0.0000001)
return true;
return false;
}
}
上一篇:UITableViewCell单元格的删除、插入、移动


下一篇:[置顶网]POWER 9为云与智能打造强大引擎