首页 > 编程语言 > 详细

图解 欧几里德算法

时间:2018-05-27 11:27:34      阅读:215      评论:0      收藏:0      [点我收藏+]

把整数看成保持面积不变,可以重排为长宽为整数的矩阵

取两个整数的最大公因子,可以看作把两个整数重排后保持一端对齐,求对齐端的最大长度

 

当两个整数一端对齐时,他们的差也保持对其。所以原问题问题gcd(m,n)能归结为gcd(m-n,n)

最终其中的一者成为长=1,宽=gcd(m,n)的矩形,算法终结

 

而不断的减这一过程就是除法的直观描述,算法中循环减的过程可优化为除法取余的过程

 

以上,得到了基于减法与基于除法的两种欧几里德算法图像上的直观解释

 

技术分享图片

图解 欧几里德算法

原文:https://www.cnblogs.com/qmcj/p/9095223.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!