【算法科普】辗转相除法（欧几里得算法）原理及应用

创作时间:

作者:

@小白创作中心

【算法科普】辗转相除法（欧几里得算法）原理及应用

引用

CSDN

https://blog.csdn.net/case_break/article/details/142426462

辗转相除法，又称欧几里得算法，是求两个正整数最大公约数的算法。其基本原理是：两个整数的最大公约数等于其中较小数和两数相除余数的最大公约数。本文将从算法原理、图解说明到实际代码应用，全面解析辗转相除法。

辗转相除法原理

计算步骤

求a和b的最大公约数（a > b）：
用辗转相除法来做，粗暴点说就一句话：余数c = a%b，此后一直用除数对余数取余，直到结果为0

图解说明

《我的第一本算法书》以1112和695为例，计算了这个过程。

整个取余的过程有点像强迫症削甘蔗，要把两根不同长度的甘蔗均分。于是互相适配，拿互不相同的部分（余数）试探长度，直至达成同一长度。

通过类似树的图形去分解数据，看起来更为直观。

整个计算过程的数据拆分如图所示，蓝色部分为初始数据。除根节点外，每层节点左边是除数，右边是余数，每层数值加起来等于父节点的值，每层的余数是下一层的除数。

从上往下计算到终点后，从这个图就很直观地能观察出，每个节点都能由叶子节点构成。1112和695的例子凑巧整除结果为1，但即使是多倍，也无非同一层中多几个和除数的值相同的节点而已。

公式推导

若 a % b = R1
则 a = n1 * b + R1

假设 b % R1= R2
则 b = n2* R1 + R2

…… 一直往下算可以发现都是由余数R1、R2 … Rn 在表达这些数值关系，所以当Rn 与 Rn-1 存在倍数关系后，Rn就可以通过倍数关系表达初始数据a和b。

代码实现：LeetCode1979 找出数组的最大公约数

给你一个整数数组 nums ，返回数组中最大数和最小数的最大公约数。

两个数的最大公约数是能够被两个数整除的最大正整数。

class Solution {
    public int findGCD(int[] nums) {
        int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
        for(int i = 0 ; i < nums.length; i++){
            if(nums[i] > max){
                max = nums[i];
            }
            if(nums[i] < min){
                min = nums[i];
            }
        }
        return realFindGCD(max, min);
    }
    //通过递归计算a、b的最大公约数
    public int realFindGCD(int a, int b){
        if(a % b == 0){
            return b;
        }
        return realFindGCD(b, a%b);
    }
}

对比通过循环来写可以发现，递归就是通过交换参数、在入参中计算完成了这个“持续用除数对余数取余”这个操作，不断更新数据。这也是递归很妙的地方，在一些回溯的场景、树的遍历中有大用。