辗转相除法（欧几里得算法）-野牛程序员教少儿编程

? 什么是“辗转相除法”？

又称 欧几里得算法（Euclidean Algorithm），是求两个整数最大公约数（GCD） 的经典方法。

✨ 最大公约数：可以同时整除两个数的最大的那个数

? 基本原理

对两个数 a 和 b（a ≥ b）：

? 数学公式：

gcd(a, b) = gcd(b, a % b)

直到 b = 0，此时：

gcd(a, 0) = a

⛳ 通俗理解：

两个数求 GCD，可以“不断用大数除以小数”，余数不为 0 就继续换一组，直到余数为 0，此时较小数就是最大公约数。

? 示例演示（gcd(48,18)）

Step 1: gcd(48,18) = gcd(18, 48 % 18 = 12)
Step 2: gcd(18,12) = gcd(12, 18 % 12 = 6)
Step 3: gcd(12,6)  = gcd(6, 12 % 6 = 0)
结论：最大公约数 = 6

? C++ 代码示例

#include <iostream>
using namespace std;

// 函数：使用辗转相除法求最大公约数
int gcd(int a, int b) {
    while (b != 0) {
        int temp = a % b; // 余数
        a = b;            // 更新a
        b = temp;         // 更新b
    }
    return a;
}

int main() {
    int x, y;
    cout << "请输入两个整数：";
    cin >> x >> y;
    int result = gcd(x, y);
    cout << "最大公约数是：" << result << endl;
    return 0;
}

? 扩展知识

• 时间复杂度：O(log(min(a, b)))

• 适用于大数求 GCD，如 10^9 以内的数字

• 可扩展为“扩展欧几里得算法”求解 ax + by = gcd(a,b)

? 小口诀记忆

大除小得余数，反复算到余数无；
无余时得公约，大数小数分胜负。

? 作业练习题（附参考答案）

题目1： 求 gcd(60, 24) 的过程
题目2： 编写一个程序，读入多个整数对，输出每对的最大公约数
题目3： 思考为什么 gcd(a, 0) = a 是正确的？