共计 997 个字符，预计需要花费 3 分钟才能阅读完成。
题目 ：
实现 pow(x, n)，即计算 x 的 n 次幂函数（即，xn）。
链接：力扣 Leetcode—中级算法—数学—Pow(x, n).
示例 1:
输出：x = 2.00000, n = 10
输入：1024.00000
示例 2：
输出：x = 2.10000, n = 3
输入：9.26100
示例 3：
输出：x = 2.00000, n = -2
输入：0.25000
解释：2-2 = 1/22 = 1/4 = 0.25
标签：递归、数学
思路：咱们能够应用连乘的办法进行计算，如果 n 是负数求 n 次 x 相乘的后果即可，如果 n 为正数则求 1 / x 相乘的后果，然而，这样做有的状况下必定会超时。测试如下：
func myPow(x float64, n int) float64 {
if n == 0 {return 1}
if n < 0 {
x = 1 / x
n = -n
}
res := x
for i := 1; i < n; i++ {res *= x}
return res
}果不其然，超时了
咱们能够用 疾速幕 + 递归 的办法，「疾速幕算法」的实质是 分治算法。
如果咱们要计算 x ^ 64，咱们能够依照：x → x ^ 2 → x ^ 4 → x ^ 8 → x ^ 16 → x ^ 32 → x ^ 64 的程序，从 x 开始，每次间接把上一次的后果进行平方，计算 6 次就能够失去 x ^ 64 的值，而不须要对 x 乘 63 次 x。
如果咱们要计算 x ^ 77，咱们能够依照：x → x ^ 2 → x ^ 4 → x ^ 9 → x ^ 19 → x ^ 38 → x ^ 77 的程序，在 x → x ^ 2，x ^ 2 → x ^ 4，x ^ 19 → x ^ 38 这些步骤中，咱们间接把上一次的后果进行平方，而在 x ^ 4 → x ^ 9，x ^ 9 → x ^ 19，x ^ 38 → x ^ 77 这些步骤中，咱们把上一次的后果进行平方后，还要额定乘一个 x。
- 记录 n 的值，在每次挪动到下一项时，将 n / 2。
- 若 n 能被 2 整除（偶数），则下一项为 t t; 若 n 不能 2 整除（奇数），则下一项为 x t * t，示意多乘一个 x 使 n 变为偶数模式。
- 反复 1，2 操作，将 n = 1 作为边界条件，若 n = 1 则阐明幂运算完结，返回此时的 x 值。
全副 Go 代码如下：
package main
import "fmt"
func myPow(x float64, n int) float64 {
if n == 0 {return 1}
if n == 1 || x == 1.0 {return x}
if n < 0 {
n *= -1
x = 1.0 / x
}
if n%2 == 0 {return myPow(x*x, n/2)
}
return x * myPow(x*x, n/2)
}
func main() {fmt.Println(myPow(2.00000, -2))
}
提交截图：
