题目链接
实现 pow(x, n)函数。即计算 x 的 n 次幂函数。
实现此算法前需要回顾下基本的数学知识。
当n等于0时，无论x为多少，均返回 1。
当n小于0时，则计算 x 的 |n| 次方分之1。
如2的-3次方等于8分之1 （0.125）。
如2的-4次方等于16分之1 （0.0625）。
则初步的边界情况就可以先写起来了
func myPow(_ x: Double, _ n: Int) -> Double {
var tempx = x
var tempn = n
if tempn < 0 {
tempn = tempn * -1
tempx = 1 / tempx
}
if tempn == 0 {
return 1.0
}
}
接下来可以套用数学交换律
当幂为偶数时
3^4 = 3^2 * 3^2
3^8 = 3^4 * 3^4
当幂为奇数则在偶数的基础上多乘一次自身
3^5 = 3^2 * 3^2 * 3
3^7 = 3^3 * 3^3 * 3
所以需要将幂/2计算后根据奇偶特性来写就行了。
转换成代码后的逻辑就比较好写了
func myPow(_ x: Double, _ n: Int) -> Double {
var tempx = x
var tempn = n
if tempn < 0 {
tempn = tempn * -1
tempx = 1 / tempx
}
if tempn == 0 {
return 1.0
}
return fastPow(tempx,tempn)
}
func fastPow(_ x:Double, _ n: Int) -> Double {
let half = myPow(x, n/2)
if n%2 == 0 {
return half * half
} else {
return half * half * x
}
}
