# 题目链接
# 题目描述
给定一个 double 类型的浮点数 x和 int 类型的整数 n,求 x 的 n 次方。
# 解题思路
本题是经典的分治法,用递归(recursion)和迭代(iteration)都可以完成。
# 递归 Recursion
func help(x float64, n int) float64 {
if n == 1 {
return x
} else if n&1 == 0 {
return help(x*x, n/2)
} else {
return x * help(x, n-1)
}
}
func myPow(x float64, n int) float64 {
if n < 0 {
return help(1.0/x, -n)
} else if n == 0 {
return 1
} else {
return help(x, n)
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 迭代 Iteration
func myPow(x float64, n int) float64 {
if n < 0 {
x = 1.0/x
n = -n
} else if n == 0 {
return 1
}
ans := 1.0
for n > 1 {
if n & 1 == 1 {
ans *= x
n--
} else {
x = x*x
n /= 2
}
}
ans *= x
return ans
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20