【文件属性】:
文件名称:算法设计与分析基础 习题参考答案
文件大小:1.06MB
文件格式:DOC
更新时间:2011-11-21 04:17:18
算法设计与分析基础 习题参考答案
习题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=m mod n=m-qn;显然,若d能整除n和r,也一定能整除m=r+qn和n。
数对(m,n)和(n,r)具有相同的公约数的有限非空集,其中也包括了最大公约数。故gcd(m,n)=gcd(n,r)
网友评论
- 很好的资源,用来学习
- 挺好的资源,正好是我的教程配套的,很感谢资源上传者,很有用
- 很好的资源啊
- 很好的资料 着了很久 但是 只有部分答案
- 可惜只有部分题的答案.
- 答案很好 就是只有部分题的答案
- 解答详细,有代码,有图解,很好