By

前言

Github：https://github.com/HealerJean

博客：http://blog.healerjean.com

1、计算x的n次幂

实现 pow(x, n) ，即计算 x 的 n 次幂函数。

示例 1:

输入: 2.00000, 10
输出: 1024.00000

示例 2:

输入: 2.10000, 3
输出: 9.26100

示例 3:

输入: 2.00000, -2
输出: 0.25000
解释: 2-2 = 1/22 = 1/4 = 0.25

1.1、解题思路

假如我们现在知道了a^5的值，那么a的10次方只需要用 a的5次方乘以a的5次方即可。同样的，求a的5次方的过程 和 求a的10次方是同样的过程。

(a的5次方 = a的2次方 * a的2次方 * a) ，指数n是奇数的话，那么 （a^n = a^(n/2) * a^(n/2) * a ）。

1.2、算法

1.2.1、暴力法

  /**
     * 暴力法
     */
    public double myPow1(double x, int n) {

        if (n == 0 ){
            return 1 ;
        }

        double res = 1 ;
        if (n < 0 ){
           x = 1/x ;
            n = Math.abs(n);
        }

        while (n > 0) {
            res = res * x;
            n--;
        }
        return res;
    }

1.2.2、快速幂求解

public double myPow(double x, int n) {
    boolean flag = false;
    if (n >= 0) {
        flag = true;
    }
    double res = 1;
    //i!= 0  保证不论是正数还是负数 都到了0的位置截止
    for (int i = n; i != 0; i /= 2) {
        //如果是奇数的话，要和自己相乘
        if (i % 2 != 0) {
            res *= x;
        }
        x *= x;
    }
    return flag ? res : 1 / res;
}

1.3、测试

@Test
public void test(){
    System.out.println(myPow(2.0000, 6));
}

​

ContactAuthor