每日算法之数值的整数次方

每日算法之数值的整数次方

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);
    }
}

hmoban主题是根据ripro二开的主题,极致后台体验,无插件,集成会员系统
自学咖网 » 每日算法之数值的整数次方