題目鏈接
實現(xiàn) pow(x, n)函數(shù)须误。即計算 x 的 n 次冪函數(shù)。
實現(xiàn)此算法前需要回顧下基本的數(shù)學(xué)知識仇轻。
當(dāng)n等于0時京痢，無論x為多少，均返回 1篷店。
當(dāng)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
}
}
接下來可以套用數(shù)學(xué)交換律
當(dāng)冪為偶數(shù)時
3^4 = 3^2 * 3^2
3^8 = 3^4 * 3^4
當(dāng)冪為奇數(shù)則在偶數(shù)的基礎(chǔ)上多乘一次自身
3^5 = 3^2 * 3^2 * 3
3^7 = 3^3 * 3^3 * 3
所以需要將冪/2計算后根據(jù)奇偶特性來寫就行了。
轉(zhuǎn)換成代碼后的邏輯就比較好寫了
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
}
}
