用流程图表示:求两个数的最大公约数
题目
用流程图表示:求两个数的最大公约数
答案
不妨设a≥b,记(a,b)为a与b的最大公约数
令c=(a,b),d=(b,a mod b)=(d, a-qb),其中q=floor(a/b)为不大于a/b的最大整数
1) c|a且c|b故c|(a-qb), 则有c|(b,a-qb)=d
2) d|b且d|(a-qb),设ud=b, vd=a-qb, 则有a=vd+qb=(v+qu)d,即d|a, 故d|(a,b)=c
综上,c=d,即(a,b)=(b,a mod b)
由于a mod b是严格递减的,所以辗转相除最终可以收敛
(a,b)=(b,a mod b)=...=(c,0)=c
举一反三
我想写一篇关于奥巴马的演讲的文章,写哪一篇好呢?为什么好
最新试题
热门考点
- 星垂平野阔,月涌大江流好在哪
- 关于嫦娥二号
- The young man often practices __(speak)Enlish with her.
- 两数相除,商4,余15,被除数、除数、商及余数和为129,求除数及被除数!
- 高中英语关于动词不定式与动词ing,现在分词,have done的用法,具体到在单项选择如何判断,
- 若a ≠0.5,试确定关于x的不等式2ax+3>x的解集
- 25比40少百分之几?40比25多百分之几?
- 微风吹拂着千万条才展开带黄色的嫩叶的柳丝写出了柔柳的什么特点
- 如图,正方体ABCD-A1B1C1D1中,E,F分别是AB,AA1的中点.求证: (1)E,C,D1,F四点共面; (2)CE,D1F,DA三线共点.
- 有两捆电线,一捆长120米,比另一捆长1/3,另一捆电线长多少米?(用方程法解}