中等C++6 分钟2,037 字

辗转相除法(欧几里得算法)——用减法求最大公约数的智慧

在古代,数学家欧几里得想出了一个聪明的办法求两个数的最大公约数,不需要列举所有因数,只需要重复做一件事:用大数除以小数,取余数;然后让原来的小数变成被除数,余数变成除数,继续除,直到余数为0。这时除数就是最大公约数。这个方法叫辗转相除法​​,也叫欧几里得算法。它是数学史上最古老的算法之一,至今仍被广泛使用,效率极高。

一、辗转相除法的原理

我们先用一个生活例子理解:假设你有48块糖和18块巧克力,想分成几份,每份糖和巧克力数量相同,而且正好分完,最多能分几份?这其实就是在求48和18的最大公约数。

操作步骤​​(以48和18为例):

  1. 48 ÷ 18 = 2 余 12(48 = 18 × 2 + 12)
  2. 18 ÷ 12 = 1 余 6(18 = 12 × 1 + 6)
  3. 12 ÷ 6 = 2 余 0 → 余数为0,最大公约数是6

所以最多能分6份,每份有8块糖和3块巧克力。

核心公式​​:gcd(a, b) = gcd(b, a % b),其中a > b(如果a < b,第一次除法会自动交换,因为a % b = a)。

为什么这样连续做下去能得到最大公约数?因为两个数的最大公约数,同时也是它们差的最大公约数。而取余运算本质上就是重复减法。例如,48和18的最大公约数,等于18和12(48-2×18)的最大公约数,依次类推,直到余数为0,除数就是答案。

二、代码实现:循环与递归

C++实现有两种常见风格:递归版和循环版。递归版代码简洁,循环版避免了函数调用开销,适合大数。

cpp
#include <iostream>
using namespace std;

// 递归版:一直调用自己,直到 b 为 0
int gcd(int a, int b) {
    if (b == 0) return a;          // 如果除数为0,返回被除数
    return gcd(b, a % b);          // 否则递归:新被除数=原除数,新除数=余数
}

// 循环版:用 while 循环代替递归
int gcd_loop(int a, int b) {
    while (b != 0) {               // 只要除数不是0就继续
        int r = a % b;             // 计算余数
        a = b;                     // 更新被除数
        b = r;                     // 更新除数
    }
    return a;                      // 循环结束,a 就是最大公约数
}

int main() {
    int x, y;
    cout << "请输入两个整数: ";
    cin >> x >> y;
    cout << "最大公约数(递归): " << gcd(x, y) << endl;
    cout << "最大公约数(循环): " << gcd_loop(x, y) << endl;
    return 0;
}

输入48 18,输出6。辗转相除法非常快,即使是很大的数也能瞬间算出来。

三、生活中的更多例子

例子1:分考卷 老师有240张数学卷子和90张语文卷子,要平均分给几个班级,每个班级得到的两种卷子数量相同,且不浪费。最多能分给几个班级?

  • 240 ÷ 90 = 2 余 60
  • 90 ÷ 60 = 1 余 30
  • 60 ÷ 30 = 2 余 0 → 最大公约数是30,最多分给30个班。

例子2:切蛋糕 一个长方形蛋糕长36厘米,宽24厘米,要切成若干个正方形小块(边长相等,且没有剩余),正方形边长最大是多少?

  • 36 ÷ 24 = 1 余 12
  • 24 ÷ 12 = 2 余 0 → 边长最大12厘米。这样能切出最少的块数,既整齐又漂亮。

例子3:零花钱平分 小明攒了108元,小红攒了72元,他们想合起来买相同的文具套装,每套价格相同,正好把钱花完。每套最多多少钱?

  • 108 ÷ 72 = 1 余 36
  • 72 ÷ 36 = 2 余 0 → 每套最多36元。小明买3套,小红买2套。

四、新手容易犯的错误

  1. 忘记处理b为0的情况​​:递归版必须有if (b == 0) return a;,否则会无限递归导致栈溢出。循环版条件是while (b != 0),写反了也会出错。
  2. 交换a和b的顺序​​:如果输入a < b,比如 gcd(18, 48),第一次计算 18 % 48 = 18,然后 gcd(48, 18) 实际上是交换了位置,结果正确。但初学者可能误以为必须确保a ≥ b,其实算法本身会自动处理,不需要额外判断。
  3. 对负数处理​​:C++中取余运算的结果符号与被除数相同(比如 -7 % 3 = -1),所以如果输入负数,辗转相除法仍然能得到绝对值意义上的最大公约数,但结果可能为负。通常我们只在自然数范围内使用,所以最好先取绝对值。
  4. 混淆循环与递归​​:递归版每次调用都会创建新的函数栈,如果数字特别大(比如几百万位),可能栈溢出。实际竞赛中更推荐循环版,因为它只使用常数空间。

五、完整可运行代码(带输入检查)

下面是一个更完善的演示程序,包含了负数取绝对值和输入检查:

cpp
#include <iostream>
#include <cstdlib>  // 用于 abs 函数
using namespace std;

// 递归版:只处理非负整数
int gcd_recursive(int a, int b) {
    if (b == 0) return a;
    return gcd_recursive(b, a % b);
}

// 循环版
int gcd_iterative(int a, int b) {
    while (b != 0) {
        int r = a % b;   // 计算余数
        a = b;           // 更新被除数
        b = r;           // 更新除数
    }
    return a;
}

int main() {
    int x, y;
    cout << "请输入两个整数(空格隔开): ";
    cin >> x >> y;

    // 避免负数:取绝对值
    x = abs(x);
    y = abs(y);

    // 如果其中一个为0,最大公约数是另一个数
    if (x == 0 && y == 0) {
        cout << "两个数都是0,没有定义最大公约数。" << endl;
        return 0;
    }
    if (x == 0) {
        cout << "最大公约数: " << y << endl;
        return 0;
    }
    if (y == 0) {
        cout << "最大公约数: " << x << endl;
        return 0;
    }

    // 正常计算
    int result1 = gcd_recursive(x, y);
    int result2 = gcd_iterative(x, y);
    cout << "递归版结果: " << result1 << endl;
    cout << "循环版结果: " << result2 << endl;
    return 0;
}

运行示例:

请输入两个整数(空格隔开): 48 18
递归版结果: 6
循环版结果: 6

六、相关知识点指引

  1. 更相减损术​​:中国古代《九章算术》中也有类似方法,用反复相减代替取余,速度较慢但原理相通。 int gcd_by_sub(int a, int b) { while (a != b) { if (a > b) a -= b; else b -= a; } return a; }
  2. 最小公倍数(LCM)​​​:利用公式 lcm(a, b) = a * b / gcd(a, b)。注意先除后乘防止溢出。
  3. 扩展欧几里得算法​​:不仅能求最大公约数,还能找到一组整数解使得 ax + by = gcd(a, b),常用于解不定方程和模逆元计算。
  4. C++标准库函数​​:C++17 提供了 std::gcd(<numeric> 头文件),可以直接使用: #include <numeric> int result = gcd(48, 18); // 返回6

辗转相除法是数论的基础算法,掌握它不仅能快速解决竞赛中的求最大公约数问题,还能为学习更高级的算法(如 RSA 加密、裴蜀定理)打下基础。

同类知识点