Python 使用分治法求幂
本帖最后由 zltzlt 于 2020-3-29 17:12 编辑Python 使用分治法求幂
分治法求 xy：若 y 为偶数，xy = (x2)y // 2；若 y 为奇数，xy = x * (x2)y // 2。
代码：
def power(x, y):
res = 1 # 因为后续是做乘法，所以初始化 res 为 1
while y: # 当 y 为 0 时停止循环
if y % 2: # 如果 y 是奇数
res *= x # res 的值为 res * x
y //= 2 # y = y // 2，将 y 分成两段
x *= x # 分了就得合，这里将 x 合并，即 x = x * x
return res # 返回结果 res 不应该是 xy=(x2)y//2 和 xy=x*(x2)y//2 吗 p是。。。。。{:10_245:}
页:
[1]