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

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

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

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

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

🧩 基本原理

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

数学公式：

直到 b = 0，此时：

通俗理解：

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

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

C++ 代码示例

扩展知识

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

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

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

🧠 小口诀记忆

大除小得余数，反复算到余数无； 无余时得公约，大数小数分胜负。🧪 作业练习题（附参考答案）

题目1：求 gcd(60, 24) 的过程

题目2：编写一个程序，读入多个整数对，输出每对的最大公约数

题目3：思考为什么gcd(a, 0) = a是正确的？

野牛程序员教少儿编程与信息学奥赛

宜宾市野牛网络科技有限公司专业微信小程序开发、网站建设、软件开发等