JZ16 数值的整数次方

描述

实现函数 double Power(double base, int exponent)
  
  
  
  
  
  
  
  ，求base的exponent次方               。 注意： 1.保证base和exponent不同时为0  
 
  
 
  
 
  
 
  
 
  
 
  
 
  
 。 2.不得使用库函数 
  
  
  
  
  
  
  
，同时不需要考虑大数问题 3.有特殊判题 


 


 


 


 


 


 


 

，不用考虑小数点后面0的位数















。

方法1

思路

既然是求次方
 
 
 
 
 
 
 
 ，那我们做不断累乘就可以了  
   
   
   
   
   
   
   
，重点是处理负的次方数 具体做法： step 1：先处理次方数为负数的情况 

 

 

 

 

 

 

 
，将底数化为分数解决
  
  
  
  
  
  
  
 。 step 2：遍历次方数的次数

 

 

 

 

 

 

 

 ，不断累乘底数  
  
  
  
  
  
  
  。

代码

public double Power(double base, int exponent) { if (exponent < 0) { base = 1 / base; exponent = -exponent; } double res = 1.0; for (int i = 0; i < exponent; i++) { res *= base; } return res; }

方法2

思路

计算幂运算               ，我们还可以使用快速幂快速计算
 


 


 


 


 


 


 


 

。 如果我们要计算5^10 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 
，常规的算法是5∗5=25















，然后再25∗5=125                       ，如此往下 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
，一共是9次运算






















，即n−1次
 
 
 
 
 
 
 
。 但是我们可以考虑这样：5∗5=25(二次）               、25∗25=625（四次）  
 
  
 
  
 
  
 
  
 
  
 
  
 
  
 、625∗625=...（八次）                ，这是一个二分的思维 
 
  
 
  
 
  
 
  
 
  
 
  
 
  
 
，运算次数缩减到了log2n次 具体做法： step 1：先处理次方数为负数的情况














，将底数化为分数解决   
   
   
   
   
   
   
   。 step 2：使用快速幂计算次方：将已乘出来的部分求次方
  
  
  
  
  
  
  
  ，可以每次缩小一半要求的次方数
 

 

 

 

 

 

 

 
。

代码

package mid.JZ16数值的整数次方; public class Solution { /*public double Power(double base, int exponent) { if (exponent < 0) { base = 1 / base; exponent = -exponent; } double res = 1.0; for (int i = 0; i < exponent; i++) { res *= base; } return res; }*/ public double Power(double base, int exponent) { if (exponent < 0) { base = 1 / base; exponent = -exponent; } return Pow(base, exponent); } public double Pow(double base, int exponent) { double res = 1.0; while (exponent != 0) { if ((exponent & 1) != 0) { res *= base; } base *= base; exponent = exponent >> 1; } return res; } public static void main(String[] args) { new Solution().Power(5, 10); } }