python用辗转相除法
时间: 2023-11-19 17:46:10 浏览: 51
辗转相除法(又称欧几里得算法)是一种求两个正整数最大公约数的算法。在Python中,可以使用递归实现辗转相除法。下面是一个示例代码:
```python
def gcd(a, b):
if b == 0:
return a
else:
return gcd(b, a % b)
a = 36
b = 48
result = gcd(a, b)
print("最大公约数为:", result)
```
这段代码中,`gcd`函数接收两个参数a和b,通过递归调用实现辗转相除法。当b等于0时,即找到了最大公约数,将其返回。运行以上代码,输出结果为`最大公约数为: 12`。
相关问题
Python用辗转相除法求最大公约数
可以使用如下代码来实现Python的辗转相除法求最大公约数:
```python
def gcd(a, b):
if b == 0:
return a
return gcd(b, a % b)
# 示例
print(gcd(24, 36)) # 输出:12
```
在这个函数中,我们使用递归的方式不断地进行辗转相除,直到余数为0,此时的被除数就是最大公约数。
Python用辗转相除法,递归求最大公约数
可以使用以下代码实现:
```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,返回最终结果。