題目描述

實作pow(x, n),用來計算xn次方,即xn



原題網址

https://leetcode.com/problems/powx-n/

輸入格式

  • -100.0 < x < 100.0
  • -231 <= n <= 231 - 1
  • -104 <= xn <= 104

範例輸入1

x = 2.00000
n = 10

範例輸出1

1024.00000

範例輸入2

x = 2.10000
n = 3

範例輸出2

9.26100

範例輸入3

x = 2.00000
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」的處理。

參考答案