剑指offer16.数值的整数次方

**剑指Offer16: 数值的整数次方**

### 题目描述实现 pow(x, n) 函数，求 x 的 n 次方。假设 n 为整数。

### 示例* `pow(2.0,3)` =8* `pow(4.1,2)` =16.81* `pow(-3.0,2)` = -9### 思路分析这个问题要求我们实现一个函数，能够计算任意数值 x 的 n 次方。其中，n 为整数。

最简单的方法是使用 Python 中的内置 pow 函数，但是这不是我们的目标，因为我们需要手动实现这个功能。

一种思路是使用递归来解决这个问题。但是，这种方法会导致重复计算，效率较低。

另一种思路是使用二分法来解决这个问题。这种方法可以避免重复计算，并且效率较高。

### 二分法解法我们可以将 n 分成两部分：n = a *2 + b，其中 a 是整数，b 为0 或1。

当 b =0 时，我们可以使用 x 的 a 次方的结果来计算 x 的 n 次方，因为 x 的 a 次方是 x 的 n 次方的一半。

当 b =1 时，我们需要计算 x 的 (a +1) 次方的结果，然后将其乘以 x 的 a 次方的结果即可得到 x 的 n 次方。

###代码实现

class Solution:
 def myPow(self, x: float, n: int) -> float:
 # Base case if n ==0:
 return1 # If n is negative, convert it to positive and invert the result if n < 0:
 return1 / self.myPow(x, -n)
 # If n is even, calculate x's half power and square it if n %2 ==0:
 half_pow = self.myPow(x, n //2)
 return half_pow * half_pow # If n is odd, calculate x's half power, square it, and multiply by x else:
 half_pow = self.myPow(x, (n -1) //2)
 return x * half_pow * half_pow# Test the functionsolution = Solution()
print(solution.myPow(2.0,3)) # Output:8.0print(solution.myPow(4.1,2)) # Output:16.81print(solution.myPow(-3.0,2)) # Output: -9.0