Python用辗转相除法,递归求最大公约数
时间: 2023-11-16 17:03:58 浏览: 122
可以使用以下代码实现:
```python
def gcd(a, b):
if b == 0:
return a
else:
return gcd(b, a % b)
```
这里的 `gcd` 函数使用了递归的方式实现了辗转相除法求两个数的最大公约数。首先判断 b 是否等于 0,如果是,则说明 a 就是最大公约数,直接返回 a;否则,递归调用 `gcd` 函数,将 b 和 a 对 b 取模的结果作为参数传入。每次递归都会将问题规模缩小,直到 b 等于 0,返回最终结果。
相关问题
Python递归辗转相除法求最大公约数
递归辗转相除法是一种求最大公约数的常用方法。它基于以下原理:两个数的最大公约数等于其中较小的数与两数相除余数的最大公约数。下面是使用Python递归辗转相除法求最大公约数的示例代码:
```python
def gcd(a, b):
if b == 0:
return a
else:
return gcd(b, a % b)
# 示例
num1 = 36
num2 = 48
result = gcd(num1, num2)
print("最大公约数为:", result)
```
在上述代码中,`gcd` 函数接受两个参数 `a` 和 `b`,并使用递归的方式求它们的最大公约数。当 `b` 为 0 时,递归结束,返回 `a` 作为最大公约数。否则,递归调用 `gcd(b, a % b)` 来求 `a` 和 `b` 的余数,并将其作为新的参数传入函数中。
以上代码输出的结果为:
```
最大公约数为: 12
```
这样,我们就使用递归辗转相除法成功求得了36和48的最大公约数12。
python编写辗转相除法求最大公约数的递归函数
下面是使用 Python 编写辗转相除法求最大公约数的递归函数:
```python
def gcd(a, b):
if b == 0:
return a
else:
return gcd(b, a % b)
```
其中,如果 b 等于 0,那么 a 就是最大公约数;否则,递归调用 gcd 函数,将 b 和 a 对 b 取模的结果作为参数传入。每次递归都会使得 b 变成更小的数,直到找到最大公约数。