图解 欧几里德算法

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

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

 

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

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

 

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

 

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

 

posted on 2018-05-27 09:48 秦梦超 阅读(…) 评论(…) 编辑 收藏

版权声明：本文为qmcj原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/qmcj/p/9095223.html