黑马程序员技术交流社区

标题: 【上海校区】利用欧几里德算法求解最大公约数 [打印本页]

---

作者: 为热爱挥汗    时间: 2018-8-16 22:23
标题: 【上海校区】利用欧几里德算法求解最大公约数

利用欧几里德算法求解最大公约数

                                            上海传智播客  崔长春老师

利用欧几里德算法求两个正整数的最小公倍数又叫辗转相除法，他是基于如下定理：

两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数。

   例如：两个数15和12，两数相除得余数为3，12和余数3这两个数的公约数为3，则15和12这两个数的最大公约数就等于3.

很显然，根据上述定理，程序设计可以考虑两种实现方式，就是递归和循环。递归实现：

function gcd($max,$min){

                if($min==0){ return $max; }

                return gcd($min,$max % $min);

        }

        $num=gcd(40,12);

        echo $num;//结果：4

循环实现：

function gcd($max,$min){

                do{

                        $mod = $max % $min;

                        $max = $min;

                        $min = $mod;

                }while($mod != 0);

                return $max;

        }

        $num=gcd(55,35);

        echo $num;//结果：5  

---

作者: 不二晨    时间: 2018-9-13 16:47

很不错，受教了

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2