C++ 最大公约数 Greatest Common Divisor GCD

2023-02-15 15:10:58 浏览数 (3)

数据结构、算法与应用第一张练习 23

当两个非负整数x和y都是0的时候，他们的最大公约数是0. 当两者至少有一个不是0的时候，他们的最大公约数是可以除尽二者的最大整数。因此gcd(0,0)=0, gcd(10,0)=gcd(0,10)=10,而gcd(20,30)=10.

求最大公约数的欧几里得算法（Euclid's Algorithm）是一个递归算法：

代码语言：javascript复制

    x                       (y=0)
    gcd(y,x mode y)         (y>0)

其中mod是模数运算子（modulo operator），相当于C 取余操作符%.

以下为算法

代码语言：javascript复制

int GCD( int x, int y ){

    if( y==0 ){
        return x;
    }
    return GCD( y, x%y );
}

0 人点赞