未分類

Pow(x, n)

BinarySearch, Go, LeetCode, Math

Pow(x, n)

Implement pow(x, n).

提示 解題應用
BinarySearch 二分法
Math 規律觀查

Default:

1
2
3
func myPow(x float64, n int) float64 {
}

解答思路:

先考慮次方值n只有正數的情況下，如果n是偶數的話x^n就可以變成(x*x)^(n/2)，也就是說每次的次方數都可以對半，如此一來迴圈就不用做那麼多次，但如果n是奇數的話就要想辦法將其轉變為偶數，把x^n變為x*(x^(n-1))，將一個x值抽出存入暫存值待最後偶數部分的次方算完後才乘回去便能解決，至於如果n為負值的話則是將x轉為1/x再將n改回正值後才開始上述計算(數學次方計算的觀念)。

程式碼解說:

這邊一開始先初始化暫存值為1.0(float64)以利如果n值為奇數時暫存抽出的x值，接著便判斷n值是否為負數，如果是就將x轉為1/x再將n改回正值，而如果n一開便為0，此時便直接回傳1(或暫存值)，前置作業都判斷結束後才開始以迴圈計算x值n次方的值，如果n為奇數的話將當下x值乘至暫存值並將次方數-1變為偶數，當次方數為偶數時就可以將x與x相乘並將次方數對半直到n為0或1為止才結束迴圈，最後只要將先前的暫存值與偶數次方情況下運算完的總合相乘就是我們要的結果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
tmp := 1.0
if n < 0 {
	x = 1 / x
	n *= -1
} else if n == 0 {
	return tmp
}
for n > 1 {
	if n%2 == 1 {
		tmp *= x
		n--
	}
	x *= x
	n /= 2
}
return tmp * x

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func myPow(x float64, n int) float64 {
	tmp := 1.0
	if n < 0 {
		x = 1 / x
		n *= -1
	} else if n == 0 {
		return tmp
	}
	for n > 1 {
		if n%2 == 1 {
			tmp *= x
			n--
		}
		x *= x
		n /= 2
	}
	return tmp * x
}

總結:

某數與該數的次方值n要計算出結果，先考慮次方值n只有正數的情況下，如果n是偶數的話x^n就可以變成(x*x)^(n/2)，使每次的次方數都可以對半，但如果n是奇數的話就要把x^n變為x*(x^(n-1))，將一個x值抽出存入暫存值待最後偶數部分的次方算完後才乘回去，至於如果n為負值的話則是將x轉為1/x再將n改回正值後才開始上述計算。

分享到