python 使用递归函数计算两个正整数的最大公约数 方法:使用欧几里得算法进行计算,从值 m 和 n 开始,反复应用公式:m, n = n, m % n 直到 n 为 0 ,m即为所求的最大公约数
时间: 2024-03-07 18:50:22 浏览: 35
好的,这是一个很常见的问题,下面是使用递归函数计算两个正整数的最大公约数的 Python 代码:
```python
def gcd(m, n):
if n == 0:
return m
else:
return gcd(n, m % n)
```
这个函数接受两个参数 `m` 和 `n`,如果 `n` 等于 0,那么 `m` 就是最大公约数,否则就递归调用 `gcd(n, m % n)` 来计算最大公约数,直到 `n` 等于 0 为止。欧几里得算法的基本思想就是反复用较小数去除较大数,直到两数相等为止。
相关问题
递归函数求两个正整数m和n的最大公约数
好的,可以使用欧几里得算法求解最大公约数。具体来说,可以定义一个递归函数 gcd(m, n),其中 m, n 表示需要求最大公约数的两个正整数。如果其中一个数为 0,则另一个数即为它们的最大公约数;否则,将 n 对 m 取模得到余数 r,然后递归调用 gcd(n, r) 求解 n 和 r 的最大公约数即可。以下是对应的 Python 代码:
```python
def gcd(m, n):
if n == 0:
return m
else:
return gcd(n, m % n)
```
希望对您有帮助。
Python编写程序,输入正整数n,m,通过递归函数用辗转相除法(欧几里得算法)求n,m的最大公约数
可以使用如下代码实现:
```python
def gcd(n, m):
if m == 0:
return n
else:
return gcd(m, n % m)
n = int(input("请输入正整数n:"))
m = int(input("请输入正整数m:"))
print("最大公约数是:", gcd(n, m))
```
在这个代码中,`gcd` 函数使用递归方式实现了辗转相除法(欧几里得算法)。如果 `m` 等于 0,那么 `n` 就是最大公约数;否则,递归调用 `gcd(m, n % m)`,并返回结果。最后,我们使用 `input` 函数获取用户输入的 `n` 和 `m`,并输出计算结果。