題目描述
實作pow(x, n)
,用來計算x
的n
次方,即xn
。
原題網址
輸入格式
-100.0 < x < 100.0
-231 <= n <= 231 - 1
-104 <= xn <= 104
範例輸入1
x = 2.00000
n = 10
n = 10
範例輸出1
1024.00000
範例輸入2
x = 2.10000
n = 3
n = 3
範例輸出2
9.26100
範例輸入3
x = 2.00000
n = -2
n = -2
範例輸出3
0.25000
額外解釋3
#{{{
2^{-2} = { 1 \over {2^2} } = { 1 \over 4 } = 0.25
}}}#
題解
這題雖然可以直接使用程式語言內建的pow
函數來完成,但不建議。
若要自己實作出powi
這種指數是整數的函數,直覺的方式就是,若指數是正整數,就用1
連續乘上底數,次數即為該正整數;若指數為負整數,就先把底數改成其自身的倒數,再把負整數乘上-1
變成正整數,接著指數為用正整數的處理方式來計算。
但是,這樣單純連乘的做法效能是很差的。比較好的做法是,先提取指數的2的因數,將底數進行平方處理,直到指數沒有2的倍數。例如,#{{2^{40} = 4^{20} = 8^{10} = 16^{5}}}#,如此一來,原本要進行的#{{24}}#次乘法,縮減為只要進行#{{3 + 5 = 8}}#次即可。
但是當指數為奇數的時候,就會需要先進行額外提取的動作。例如:
#{{{2^{43} = 2 \times 2^{42} = 2 \times 4^{21} = 2 \times 4 \times 4^{20} = 8 \times 8^{10} = 8 \times 16^{5}}}}#
在程式實作上,進行「指數除以2」的動作前,要先判斷此時的指數是否為奇數,如果是的話,就先將連乘結果先乘上此時的底數。之後才進行底數平方以及「指數除以2」的處理。