【剑指offer】JZ16:数值的整数次方
- 题目描述
- 解题思路
题目描述
描述:实现函数 double Power(double base, int exponent),求base的exponent次方。
注意:
1.保证base和exponent不同时为0。
2.不得使用库函数,同时不需要考虑大数问题。
3.有特殊判题,不用考虑小数点后面0的位数。
数据范围: ∣base∣≤100 , ∣exponent∣≤100 ,保证最终结果一定满足 ∣val∣≤104。
进阶:空间复杂度 O(1) ,时间复杂度 O(n) 。
输入:2.00000,3
返回值:8.00000
输入:2.10000,3
返回值:9.26100
输入:2.00000,-2
返回值:0.25000
说明:2的-2次方等于1/4=0.25
解题思路
数值的整数次方:最直观的想法是,求a的b次方,使用for循环直接循环b次。更快求数值的整数次方的方法是快速幂,其基本思想是:如果b是偶数,那么ab就分为ab/2×ab/2;如果b是奇数,那么ab就分为ab-1×a。举一个通俗易懂的例子,比如求55,则55=54×5,54=52×52,52=51×51。如果使用计算机来实现的话,可以使用二进制来判断,当指数大于0时进入循环,首先判断指数的最后一位是否为1,如果是则将其乘入结果,同时每次循环中还需要对底数进行自乘并将指数右移一位,为下次循环做准备。
double Power(double base, int exponent)
{double result=1;bool flag=exponent>0?true:false;exponent=abs(exponent);while(exponent>0){if(exponent&1) //二进制最后一位是1result*=base;base*=base;exponent>>=1;}return flag==true?result:1.0/result;;
}