Python 官方文档：入门教程 => 点击学习
目录辗转相除法求最大公约数和最小公倍数辗转相除法数学原理python代码实现用递归的方式实现python3 20.辗转相除法算法分析源代码结果截图辗转相除法求最大公约数和最小公倍数
辗转相除法也称欧几里得算法，是用来求两个正整数的最大公约数的算法。接下来我们用实例来解释一下。假如我们需要求12和21的最大公约数，用辗转相除法是这样实现的：
21 / 12 = 1 （余 9）
12 / 9 = 1（余 3）
9 / 3 = 3 （余 0）至此，得到21与12的最大公约数为3（注意：这里的3是第二个式子取余得到的3，而非最后一个式子相除得到的），然后把两个数相乘再除以最大公约数就可以得到最小公倍数：（21*12）/ 3 = 84
接下来我们用python代码来实现这样一道题目：
题目：输入两个正整数，求其最大公约数和最小公倍数。
def func(m,n):
a = m
b = n
# 默认m>n，若不是，则交换
if m < n:
m,n = n,m
while n != 0:
# 对m除n取余
r = m % n
m = n
n = r
return m,(a*b)/mprint("正整数m与n的最大公约数与最小公倍数分别为：",func(12,21))
正整数m与n的最大公约数与最小公倍数分别为： (3, 84.0)
def rec(m,n):
# 默认m>n，若不是，则交换
if m < n:
m,n = n,m
# 终止条件
if n == 0:
return m,(a*b)/m
# 递归部分
return rec(n,m%n)
a = 12
b = 21print("正整数m与n的最大公约数与最小公倍数分别为：",rec(12,21))
正整数m与n的最大公约数与最小公倍数分别为： (3, 84.0)
1.算法定义为：在有限的步骤内解决数学问题的程序，即为了解决某项工作或某个问题，所需要有限数量的机械性或重复性指令与计算步骤。
2.最大公约数：可整除两个整数的最大整数。
3.用两个数中较大的整数除以较小的数，求得商和余数。
# coding:gbk
Num_1 = int(input("请输入一个整数： "))
Num_2 = int(input("请输入一个整数： "))
if Num_1 < Num_2:
Tmp_Num = Num_1 # 是交换而不是赋值
Num_1 = Num_2
Num_2 = Tmp_Num
while Num_2 != 0:
Tmp_Num = Num_1 % Num_2
Num_1 = Num_2
Num_2 = Tmp_Num
print('输出这两个整数的最大公约数：', Num_1)
以上为个人经验，希望能给大家一个参考，也希望大家多多支持编程网。
--结束END--
本文标题: python辗转相除法求最大公约数和最小公倍数的实现
本文链接: https://www.lsjlt.com/news/119423.html(转载时请注明来源链接)
有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
下载Word文档到电脑，方便收藏和打印～
2024-03-01
2024-03-01
2024-03-01
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
回答
回答
回答
回答
回答
回答
回答
回答
回答
回答
官方手机版
微信公众号
商务合作
0