题目描述

实现一个函数 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 代码示例

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 代码示例

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 代码示例

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$ 的问题，同时处理大数和负数指数的情况。希望这些代码示例能帮助你更好地理解并实现这一算法。