@Author：Runsen

编程的本质来源于算法，而算法的本质来源于数学，编程只不过将数学题代码化。 ---- Runsen

先问你们一个小学问题：如何求两个整数的最大公约数？

曾经见过不少的算法题，发现有的并不在数据结构和算法大纲中，而是来源于高中数学。

高中数学在必修三中，有一个非常重要的知识点，叫做碾转相除法、更相减损术。

辗转相除法， 又名欧几里德算法（Euclidean algorithm）乃求两个正整数之最大公因子的算法。它是已知最古老的算法， 其可追溯至公元前300年前。

在古代，有一个比较出名的数学家，叫做刘徽。而更相减损术是我国数学家刘徽的专著《九章算术》中记载的．

碾转相除法

辗转相除是求最大公约数的一种算法。给两个数,我们可以把它组成数对(a,b)

辗转相除法基于如下原理：两个整数的最大公约数等于其中较小的数和两数的相除余数的最大公约数。

求a和b的最大公约数，就用ab中较小的数去除另一

文章来源: maoli.blog.csdn.net，作者：刘润森！，版权归原作者所有，如需转载，请联系作者。

原文链接：maoli.blog.csdn.net/article/details/110920088