7月13日,晴。曲水流觞叹如何,人生如梦易蹉跎。源码百万尽在握,写罢回首谁知我。 例5 求最大公约数 如果有一个自然数A能被自然数B整除,则称A为B的倍数,B为A的约数。几个自然数公有的约数,叫做这几个自然数的公约数。这些公约数中最大的一个公约数,称为这几个自然数的最大公约数,简称为GCD。
例如,在2、4、6这3个数中,2就是2、4、6的最大公约数。 怎么求最大公约数呢?早在公元前300年左右,欧几里得就在他的著作《几何原本》中给出了高效的解法——辗转相除法。 例如,求153和123的最大公约数,操作过程如下: 所以,153和123的最大公约数就是3。 可以看出,在用辗转相除法求最大公约数时,每次相除后的除数N和余数R都将原来的问题规模缩小,而且有一个边界条件(两数能够整除,即余数为0)。俺老猪看出了,在用辗转相除法求最大公约数时,每次相除后的除数N和余数R都将原来的问题规模缩小,而且有一个边界条件(两数能够整除,即余数为0)。有这两条,就可使用递归算法来解这个问题,处理流程如下: 俺沙悟净用代码实现试上一试:
在以上程序中,定义了一个gcd()函数,在这个函数中调用gcd()函数,这样就形成了递归调用。在这个函数内部通过辗转相除,然后判断余数是否为0,若为0就返回n值,否则递归调用gcd()函数进行辗转相除。 |
|