[关闭]
@Lin-- 2018-10-07T15:25:26.000000Z 字数 460 阅读 254

第二次作业

计算机数学


把Division Algorithm的证明补充完整。

证:


S非空,得有r∈S,且
设存在r1,q1使得

先证q的唯一性:

因为
由存在性得
所以有
=q1
故有

后证r的唯一性:


说明Simple Division算法的正确性及该算法对n比特输入需要使用的时间是O(n^2)。

  1. def divide(a,b):
  2. if a==0:
  3. return 0,0
  4. q,r=divide(a//2,b)
  5. q,r=2*q,2*r
  6. if a&1: #a是奇数
  7. r=r+1
  8. if r>=b:
  9. r,q=r-b,q+1
  10. return q,r

证:

(1)

q为商,r为余数。递归算法,最底层,之后向上返回。
若除数为奇数,则在递归计算a/2时是向下取整,故向上返回应是


所以得

(2)

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注