算法设计与分析基础习题参考答案

4星 · 超过85%的资源
所需积分/C币: 33
浏览量·38
DOC
1.06MB
2010-09-07 16:25:59 上传
無_1024
  • 粉丝: 669
  • 资源: 14
前往需求广场,查看用户热搜
上传资源 快速赚钱
精品专辑
内容简介:习题 1.1 5..证明等式 gcd(m,n)=gcd(n,m mod n)对每一对正整数 m,n 都成立.Hint:根据除法的定义不难证明:  如果 d 整除 u 和 v, 那么 d 一定能整除 u±v;  如果 d 整除 u,那么 d 也能够整除 u 的任何整数倍 ku.对于任意一对正整数 m,n,若 d 能整除 m 和 n,那么 d 一定能整除 n 和 r=mmod n=m-qn;显然,若 d 能整除 n 和 r,也一定能整除 m=r+qn 和 n。数对(m,n)和(n,r)具有相同的公约数的有限非空集,其中也包括了最大公约数。故 gcd(m,n)=gcd(n,r)6.对于第一个数小...