@Lin--
2018-10-07T15:25:26.000000Z
字数 460
阅读 254
计算机数学
令
S非空,得有r∈S,且
设存在r1,q1使得
因为
由存在性得
所以有
即=q1
故有
def divide(a,b):
if a==0:
return 0,0
q,r=divide(a//2,b)
q,r=2*q,2*r
if a&1: #a是奇数
r=r+1
if r>=b:
r,q=r-b,q+1
return q,r
q为商,r为余数。递归算法,最底层,之后向上返回。
若除数为奇数,则在递归计算a/2时是向下取整,故向上返回应是
若;
由得
所以得