在下面的除法算法中,我不理解为什么将q和r乘以二会起作用,以及如果x是奇数为什么要增加r。
请给出这个递归除法算法的理论证明。
提前感谢您的回答。
请给出这个递归除法算法的理论证明。
提前感谢您的回答。
function divide(x, y)
if x = 0:
return (q, r) = (0, 0)
(q, r) = divide(floor(x/2), y)
q = 2q, r = 2r
if x is odd:
r = r + 1
if r ≥ y:
r = r − y, q = q + 1
return (q, r)