辗转相除法，python实现

### 辗转相除法的Python实现辗转相除法是一种用于计算两个正整数最大公约数的有效方法。以下是基于该算法的一个具体实现： #### 完整代码示例 ```python def gcd(a, b): while b != 0: a, b = b, a % b return a # 测试代码 num1 = 1071 num2 = 462 result = gcd(num1, num2) print(f"The GCD of {num1} and {num2} is {result}") ``` 此代码通过循环不断更新 `a` 和 `b` 的值，直到 `b` 变为零为止[^2]。此时，变量 `a` 中存储的就是两数的最大公约数。 #### 算法原理说明辗转相除法的核心在于利用欧几里得定理：对于任意两个正整数 \(a\) 和 \(b\) （\(a > b\)），它们的最大公约数等于 \(b\) 和 \(a \% b\) 的最大公约数。这一过程会持续迭代下去，直至其中一个数值变为零[^3]。 --- ### 更加优化的递归版本除了上述循环方式外，还可以采用递归来简化逻辑结构： ```python def gcd_recursive(a, b): if b == 0: return a else: return gcd_recursive(b, a % b) # 测试代码 num1 = 1071 num2 = 462 result = gcd_recursive(num1, num2) print(f"The GCD of {num1} and {num2} using recursion is {result}") ``` 这种写法更加简洁明了，在某些场景下也更易于理解。 --- ### 结合实际应用扩展功能如果希望进一步增强程序的功能性，则可加入输入验证以及支持多个数字间的最大公约数运算等功能模块。下面展示了一个简单的改进版例子： ```python from functools import reduce def gcd_multiple(*numbers): def _gcd(x, y): while y: x, y = y, x % y return abs(x) return reduce(_gcd, numbers) # 测试代码 nums = [48, 180, 640] result = gcd_multiple(*nums) print(f"The GCD of {nums} is {result}.") ``` 这里引入了标准库中的 `reduce()` 函数来处理不定数量参数情况下的连续求解操作[^1]。 ---

创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考

下一篇如果使用python呢？