用NS结构流程图表示:输入2个数,求它们的最大公约数
答案:2 悬赏:60 手机版
解决时间 2021-12-16 08:49
- 提问者网友：的空心小姐
- 2021-12-15 19:42
用NS结构流程图表示:输入2个数,求它们的最大公约数
最佳答案
- 五星知识达人网友：我叫哇咔咔
- 2021-12-15 21:00
不妨设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
令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
全部回答
- 1楼网友：爷是黑户
- 2021-12-15 22:14
你说呢...
我要举报
如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！
点此我要举报以上问答信息
大家都在看
推荐资讯