我从 leetcode 得到这个代码.
I get this code from leetcode.
class Solution(object): def myPow(self, x, n): if n == 0: return 1 if n == -1: return 1 / x return self.myPow(x * x, n / 2) * ([1, x][n % 2])此代码用于实现poe(x, n),即Python中的x**n.
This code is used to implement poe(x, n), which means x**n in Python.
我想知道为什么它可以实现pow(x, n).
I want to know why it can implement pow(x, n).
看起来没有意义...
我明白
if n == 0: and if n == -1:但核心代码:
self.myPow(x * x, n / 2) * ([1, x][n % 2])真的很难理解.
顺便说一句,此代码仅适用于 Python 2.7.如果你想在 Python 3 上测试,你应该改变
BTW, this code only works on Python 2.7. If you want to test on Python 3, you should change
myPow(x*x, n / 2) * ([1, x][n % 2])到
myPow(x*x, n // 2) * ([1, x][n % 2]) 推荐答案递归函数是计算幂(最有可能是整数,非负数或-1,幂) 的数字,如您所料(类似于 x = 2.2 和 n = 9).
The recursive function is to compute power (most probably integer, non negative or -1, power) of a number, as you might have expected (something like x = 2.2 and n = 9).
(这似乎是为 Python 2.x 编写的(由于 n/2 的预期结果为 integer> 而不是 n//2))
(And this seems to be written for Python 2.x (due to the n/2 having expected result of integer instead of n//2))
最初的 returns 是非常简单的数学运算.
The initial returns are very straight-forward math.
if n == 0: return 1 if n == -1: return 1 / x当幂为0,则返回1,然后幂为-1,则返回1/x.
When the power is 0, then you return 1 and then the power is -1, you return 1/x.
现在下一行由两个元素组成:
Now the next line consists of two elements:
self.myPow(x * x, n/2) and [1, x][n%2]第一个 self.myPow(x * x, n/2) 仅仅意味着你想要获得更高的功率(不是 0 或 -1) 通过平方乘方数 x
The first one self.myPow(x * x, n/2) simply means you want to make higher power (not 0 or -1) into half of it by squaring the powered number x
(很可能是通过减少所需的乘法次数来加快计算速度 - 想象一下,如果您有计算 2^58 的情况.通过乘法,您必须乘以数字 58 次.但如果每次都将其分成两部分并递归求解,则最终操作次数会减少).
(most probably to speed up the calculation by reducing the number of multiplication needed - imagine if you have case to compute 2^58. By multiplication, you have to multiply the number 58 times. But if you divide it into two every time and solve it recursively, you end up will smaller number of operations).
示例:
x^8 = (x^2)^4 = y^4 #thus you reduce the number of operation you need to perform在这里,您将 x^2 作为递归中的下一个参数(即 y)并递归执行,直到幂为 0 或 -1.
Here, you pass x^2 as your next argument in the recursive (that is y) and do it recursively till the power is 0 or -1.
下一个是你得到两个除法幂的模.这是为了弥补奇情况下的情况(即,当幂n为奇数时).
And the next one is you get the modulo of two of the divided power. This is to make up the case for odd case (that is, when the power n is odd).
[1,x][n%2] #is 1 when n is even, is x when n is odd如果n是odd,那么通过做n/2,你会在这个过程中丢失一个x.因此,您必须通过将 self.myPow(x * x, n/2) 与该 x 相乘来弥补.但是如果你的 n 不是奇数(偶数),你不会失去一个 x,因此你不需要将结果乘以 x但是通过 1.
If n is odd, then by doing n/2, you lose one x in the process. Thus you have to make up by multiplying the self.myPow(x * x, n / 2) with that x. But if your n is not odd (even), you do not lose one x, thus you do not need to multiply the result by x but by 1.
举例说明:
x^9 = (x^2)^4 * x #take a look the x here但是
x^8 = (x^2)^4 * 1 #take a look the 1 here因此:
[1, x][n % 2]是将前面的递归乘以 1(对于偶数 n 情况)或 x(对于奇数 n case) 等价于三元表达式:
is to multiply the previous recursion by either 1 (for even n case) or x (for odd n case) and is equivalent to ternary expression:
1 if n % 2 == 0 else x更多推荐
有人可以为我解释这个递归吗?
发布评论