16:数值的整数次方

发表于 | 分类于

题目16：数值的整数次方

给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。不得使用库函数，同时不需要考虑大数问题。

思路

要注意计算机关于double相等的判定

判断两个double型数据，计算机有误差

1
2
3
4
5
6
7
private static boolean equal(double num1,double num2){
	if((num1-num2>-0.0000001) && (num1-num2<0.0000001)){
		return true;
	}else{
		return false;
	}
}

一. 常规方法

$O(N)$

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
public class _16 {
	public static double power(double base, int exponent) {
		if (equal(base, 0.0) && equal(exponent, 0.0)) {//指数和底数不能同时为0
			throw new RuntimeException("invalid input. base and exponent both are zero");
		}
		if (equal(exponent, 0.0)) {// 指数为0就返回1
			return 1.0;
		}
		int exp = exponent;
		if (exponent < 0) {// 求指数的绝对值
			exp = -exp;
		}
		//调用核心函数。传入的exp是取过绝对值的
		double result = powerWithUnsignedExponent(base, exp); 

		if (exponent < 0) {// 指数是负数，要进行求倒数
			result = 1 / result;
		}
		return result;
	}

	// 求一个数的正整数次幂
	private static double powerWithUnsignedExponent(double base, int exponent) {
    // 指数为1，返回底数（指数为0的在主调函数已经考虑过了）
		if (equal(exponent, 1.0)) {
			return base;
		}
		double result = 1.0;
		for (int i = 1; i <= exponent; i++) {
			result = result * base;
		}
		return result;
	}

	private static boolean equal(double num1, double num2) {
		if ((num1 - num2 > -0.0000001) && (num1 - num2 < 0.0000001)) {
			return true;
		} else {
			return false;
		}
	}

	public static void main(String[] args) {
		System.out.println(power(2, -4));
		System.out.println(power(2, 4));
		System.out.println(power(2, 3));//测试奇数幂的递归情况
		System.out.println(power(2, 0));
		System.out.println(power(0, 0));
	}
}

输出：

1
2
3
4
5
0.0625
16.0
8.0
1.0
Exception in thread "main" java.lang.RuntimeException: invalid input. base and exponent both are zero

二. 对核心方法优化

$O(logN)$

下面的讨论中 x 代表 base，n 代表 exponent。

image

因为 (x*x)n/2 可以通过递归求解，并且每递归一次，n 都减小一半，因此整个算法的时间复杂度为 O(logn)。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
private static double powerWithUnsignedExponent(double base, int exponent) { 
    if (equal(exponent,1.0)) {// 指数为1，返回底数（指数为0的在主调函数已经考虑过了）
        return base;
    } 
    // 递归求一半的值。用位运算代替除法。
    double result = powerWithUnsignedExponent(base, exponent >> 1);
 
    // 求最终的值，如果是奇数就还要剩以一次底数
    result *= result;
    if ((exponent & 0x1) ==1) {//用与运算代替取模
        result *= base;
    }
    return result;
}

输出：

1
2
3
4
5
0.0625
16.0
8.0
1.0
Exception in thread "main" java.lang.RuntimeException: invalid input. base and exponent both are zero
> >