[Golang]力扣Leetcode—中级算法—数学—Pow(x, n)（分治算法） golangleetcode

题目：
实现 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 }

果不其然，超时了

[Golang]力扣Leetcode—中级算法—数学—Pow(x, n)（分治算法）

文章图片

我们可以用快速幕+递归的方法，「快速幕算法」的本质是分治算法。
如果我们要计算 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 mainimport "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)) }

【[Golang]力扣Leetcode—中级算法—数学—Pow(x, n)（分治算法）】提交截图：