当前位置： 面试刷题>> Pow(x, n)(经典算法150题)
### 题目描述
实现一个函数 `Pow(x, n)`，该函数计算并返回 $x$ 的 $n$ 次幂（即 $x^n$）。该函数需要处理大数的情况，并且 $n$ 可能是负数。
**注意**：
- 你不能使用库函数，如 `Math.pow()`（JavaScript）、`pow()`（PHP）或 `**` 运算符（Python）来直接计算幂。
- 负数指数幂的定义是 $x^{-n} = 1 / x^n$，其中 $x \neq 0$。
### 示例
**输入**：
- $x = 2.00000$
- $n = 10$
**输出**：
- $1024.00000$
**输入**：
- $x = 2.10000$
- $n = 3$
**输出**：
- $9.26100$
**输入**：
- $x = 2.00000$
- $n = -2$
**输出**：
- $0.25000$
### 解题思路
为了有效计算 $x^n$，特别是当 $n$ 很大或 $n$ 为负数时，我们可以使用递归和快速幂算法来优化计算过程。快速幂算法通过将指数 $n$ 分解为二进制形式，并利用乘法的结合律来减少乘法操作的次数。
### PHP 代码示例
```php
function Pow($x, $n) {
if ($n == 0) return 1;
if ($n < 0) {
$x = 1 / $x;
$n = -$n;
}
$half = Pow($x, intval($n / 2));
if ($n % 2 == 0) {
return $half * $half;
} else {
return $half * $half * $x;
}
}
// 示例测试
echo Pow(2.00000, 10); // 输出 1024
echo "\n";
echo Pow(2.10000, 3); // 输出 9.261
echo "\n";
echo Pow(2.00000, -2); // 输出 0.25
```
### Python 代码示例
```python
def Pow(x, n):
if n == 0:
return 1
if n < 0:
x = 1 / x
n = -n
half = Pow(x, n // 2)
if n % 2 == 0:
return half * half
else:
return half * half * x
# 示例测试
print(Pow(2.00000, 10)) # 输出 1024.0
print(Pow(2.10000, 3)) # 输出 9.261
print(Pow(2.00000, -2)) # 输出 0.25
```
### JavaScript 代码示例
```javascript
function Pow(x, n) {
if (n === 0) return 1;
if (n < 0) {
x = 1 / x;
n = -n;
}
let half = Pow(x, Math.floor(n / 2));
if (n % 2 === 0) {
return half * half;
} else {
return half * half * x;
}
}
// 示例测试
console.log(Pow(2.00000, 10)); // 输出 1024
console.log(Pow(2.10000, 3)); // 输出 9.261
console.log(Pow(2.00000, -2)); // 输出 0.25
```
通过这些示例，你可以看到如何使用递归和快速幂算法来解决 $x^n$ 的问题，同时处理大数和负数指数的情况。希望这些代码示例能帮助你更好地理解并实现这一算法。