Lihb +

乘除法的递归运算

乘法公式

乘法

算法:

function multiply(x, y)
Input: Two n-bit integers x and y, where y >= 0
Output: Their product

if y = 0: return 0
z = multiply(x, math.floor(y / 2))
if y is even:
    return z
else:
    return x + 2z

除法

一个整数x除以另一个整数y(y!=0),意味需要找到一个商数q和一个余数r,使得 x = yq + r,同时r < y

function divide(x, y)
Input:  Two n-bit integers x and y, where y >= 1
Output: The quotient and remainder of x divided by y

if x = 0: return (q, r) = (0, 0)
(q, r) = divide(math.floor(x / 2), y)
q = 2 * q  r = 2 * r
if x is odd: r = r + 1
if x >= y: r = r -y, q = q + 1
return (q, r)

点击查看评论

Blog

Knowledge

Project