辗转相除法 订阅
欧几里德算法又称辗转相除法,是指用于计算两个非负整数a,b的最大公约数。应用领域有数学和计算机两个方面。计算公式gcd(a,b) = gcd(b,a mod b)。欧几里德算法和扩展欧几里德算法可使用多种编程语言实现。 展开全文
欧几里德算法又称辗转相除法,是指用于计算两个非负整数a,b的最大公约数。应用领域有数学和计算机两个方面。计算公式gcd(a,b) = gcd(b,a mod b)。欧几里德算法和扩展欧几里德算法可使用多种编程语言实现。
信息
领    域
数学,计算机
别    名
辗转相除法
原    理
gcd(a,b) = gcd(b,a mod b)
中文名
欧几里德算法
应    用
计算两个正整数a,b的最大公约数
外文名
Euclidean Algorithm 或者 Euclid's algorithm
欧几里得算法算法简介
欧几里德算法是用来求两个正整数最大公约数的算法。古希腊数学家欧几里德在其著作《The Elements》中最早描述了这种算法,所以被命名为欧几里德算法。扩展欧几里德算法可用于RSA加密等领域。假如需要求 1997 和 615 两个正整数的最大公约数,用欧几里德算法,是这样进行的:1997 / 615 = 3 (余 152)615 / 152 = 4(余7)152 / 7 = 21(余5)7 / 5 = 1 (余2)5 / 2 = 2 (余1)2 / 1 = 2 (余0)至此,最大公约数为1以除数和余数反复做除法运算,当余数为 0 时,取当前算式除数为最大公约数,所以就得出了 1997 和 615 的最大公约数 1。
收起全文
精华内容
下载资源
问答
  • 辗转相除法

    2020-02-06 14:17:49
    辗转相除法 辗转相除法相信大家大学经常接触,但初次接触到可能不是那么容易理解,那么话不多说,我跟大家分享一下我的理解。 关于辗转相除法的专业解释有很多,我在这就不再赘述,大家可以自己搜搜看,我这直接上...

    辗转相除法

    关于辗转相除法的专业解释有很多,我在这就不再赘述,大家可以自己搜搜看,我这直接上图。
    辗转相除法

    辗转相除法计算的是 a 和 b 的 最大公约数 g

    这里先将 a 分成两份 分别由 b 和 c 组成

    a % b = c
    

    再求 b 和 c 的最大公约数 g

     g = gcd(b,c)
    

    这时b / g = 0 , c / g = 0

    由于a可以由 b 和 c 组成,
    所以 a / g = 0;
    可得 a 和 b 的最大公约数为 g

    这里举两个简单的例子:
    a = 10, b = 8;
    a % b = 2;
    c = 2;
    a 被分为了 8 和 2 两部分;
    因为 8 和 2 的最大公约数为 2
    而 a 由 b 和 c 组成
    10 = 8 + 2 = 4 * 2 + 2 = 5 * 2
    所以10和8的最大公约数为2;

    再例如:
    a = 18, b = 8
    c = a % b = 2
    8 % 2 = 0
    18 = 8 * 2 + 2 = 9 * 2
    所以 18 和 8 最大公约数为2

    具体实现是一个简单的递归调用:

    int gcd(int a, int b)
    {
        if(b == 0) return a;
        return gcd(b, a%b);
    }
    

    还有一点值得说的是, 一般情况下调用 gcd(a,b) 都是默认 a > b;
    不过如果a < b也不用但心,因为当 a < b 时,gcd(a,b) = gcd(b,a%b) = gcd(b,a)

    展开全文
  • 辗转相除法证明辗转相除法证明辗转相除法证明辗转相除法证明

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 6,556
精华内容 2,622
关键字:

辗转相除法