编程算法C++实现之辗转相除法

辗转相除法用于求最大公倍数和最小公约数。首先我讲讲怎么算：现在有两个数，12和18，其中较大数是18，那么用18对12取余数，得到6，再用12对6取余数，发现可以整除，于是最大公约数就是6。这个过程对于人来说显得较为复杂，毕竟这明明是一个能一眼看出结果的问题，但是这个过程对于计算机来说，确实很容易的，并且此过程很显然适合用编程来实现。下面讲讲原理，假设12和18的最大公约数是x，那么可得12/x=a，18/x=b，a和b肯定都是整数，而且b＞a，两式想减6=(b-a)x，b-a肯定也是个整数，所以6也可以被x整除。此时需要注意，我们的目标就是求出x，由于6也可以被整x整除，所以这个问题转换为了求6、12的最大公约数，所以可以对这两个数再进行相同操作（注意，可重复操作，所以适合用循环语句来实现）。最后即可得到最大公约数。最大公倍数只需要用12*18/6即可得到，此处为小学或初中内容了，无需多言。