主要内容

计算数字的幂

虽然JavaScript有一个内置的pow函数来计算一个数字的幂，你可以递归地编写一个类似的函数，它可以非常有效。唯一的问题是指数必须是整数。

假设你想要计算

x^{n}

，其中

x

是任何实数，

n

是任何整数。如果

n

为0，那很容易，因为

x^{0} = 1

，无论

x

是多少。这是一个很好的例子。

所以现在让我们看看当

n

为正时会发生什么。让我们首先回想一下，当你乘以

x

的幂时，你添加指数：

x^{a} \cdot x^{b} = x^{a + b}

对于任何基数

x

和任何指数

a

和

b

都应该成立。因此，如果

n

为正数且为偶数，那么

x^{n} = x^{n / 2} \cdot x^{n / 2}

。如果你以递归方式计算

y = x^{n / 2}

，那么你可以将

x^{n}

计算为

y \cdot y

。如果

n

是正数和奇数怎么办？那么

x^{n} = x^{n - 1} \cdot x

，

n - 1

或者是0或者是正数和偶数。我们刚刚看到当指数为0或者是正数和偶数时如何计算

x

的幂。因此，您可以递归计算

x^{n - 1}

，然后使用此结果计算

x^{n} = x^{n - 1} \cdot x

。

当

n

为负时怎么办？那么

x^{n} = 1 / x^{- n}

，指数

- n

为正，因为它是负数的否定。所以你可以递归计算

x^{- n}

并取其倒数。

将这些观察结果放在一起, 我们得到了以下计算

x^{n}

的递归算法:

基本情况是 $n = 0$ ‍， $x^{0} = 1$ ‍。
如果 $n$ ‍为正数且为偶数，则递归计算 $y = x^{n / 2}$ ‍，那么 $x^{n} = y \cdot y$ ‍。请注意，在这种情况下，您只需要进行一次递归调用，只计算一次 $x^{n / 2}$ ‍，然后将此递归调用的结果乘以它。
如果 $n$ ‍是正数且为奇数，递归计算 $x^{n - 1}$ ‍，使指数为0或为正偶数。那么， $x^{n} = x^{n - 1} \cdot x$ ‍。
如果 $n$ ‍为负数，则递归计算 $x^{- n}$ ‍，以使指数变为正数。然后， $x^{n} = 1 / x^{- n}$ ‍。

本内容是达特茅斯计算机科学教授 Thomas Cormen 和 Devin Balkcom，与可汗学院的计算课程团队合作完成。内容获得许可 CC-BY-NC-SA。

想加入讨论吗？

排序方式:

尚无帖子。