从原理到实践：详解辗转相除法（欧几里得算法）

从原理到实践：详解辗转相除法（欧几里得算法）

引用

CSDN

1.

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

辗转相除法，又称欧几里得算法，是一种用于计算两个正整数最大公约数的算法。本文将从原理到实践，深入探讨这一经典算法。

辗转相除法原理

计算步骤

辗转相除法的基本步骤如下：

1. 给定两个正整数a和b（a > b）
2. 计算a除以b的余数c
3. 将b赋值给a，将c赋值给b
4. 重复步骤2和3，直到余数为0。此时的b即为最大公约数

图形理解

通过树形图可以更直观地理解辗转相除法的计算过程：

在这个图中，蓝色部分表示初始数据。除根节点外，每层节点左边是除数，右边是余数，每层数值加起来等于父节点的值，每层的余数是下一层的除数。

公式推导

假设 a % b = R1，则 a = n1 * b + R1
假设 b % R1 = R2，则 b = n2 * R1 + R2
……
一直往下算可以发现，所有数值关系都可以由余数R1、R2 … Rn来表达。当Rn与Rn-1存在倍数关系后，Rn就可以通过倍数关系表达初始数据a和b。

代码实现

接下来，我们通过一个LeetCode题目来实践辗转相除法的应用：

题目：找出数组的最大公约数

给你一个整数数组 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);
    }
}

这段代码首先找到数组中的最大值和最小值，然后通过递归函数realFindGCD计算这两个数的最大公约数。递归函数的核心逻辑是：如果a能被b整除，则b就是最大公约数；否则，继续用b和a%b进行递归计算。

总结

辗转相除法是一个简单而优雅的算法，通过递归或循环都能很好地实现。它不仅在数学中有广泛应用，在计算机科学中也是基础算法之一。理解其原理和实现方法，对于提升算法思维大有裨益。