怎么使用python辗转相除法求最大公约数和最小公倍数
导读:本文共1495字符,通常情况下阅读需要5分钟。同时您也可以点击右侧朗读,来听本文内容。按键盘←(左) →(右) 方向键可以翻页。
摘要: 辗转相除法求最大公约数和最小公倍数辗转相除法数学原理辗转相除法也称欧几里得算法,是用来求两个正整数的最大公约数的算法。接下来我们用实例来解释一下。假如我们需要求12和21的最大公约数,用辗转相除法是这样实现的:21/12=1(余9)12/9=1(余3)9/3=3(余0)至此,得到21与12的最大公约数为3(注意:这里的3是第二个式子取余得到的3,而非最后一个... ...
目录
(为您整理了一些要点),点击可以直达。辗转相除法求最大公约数和最小公倍数
辗转相除法数学原理
辗转相除法也称欧几里得算法,是用来求两个正整数的最大公约数的算法。接下来我们用实例来解释一下。假如我们需要求12和21的最大公约数,用辗转相除法是这样实现的:
21/12=1(余9)12/9=1(余3)9/3=3(余0)
至此,得到21与12的最大公约数为3(注意:这里的3是第二个式子取余得到的3,而非最后一个式子相除得到的),然后把两个数相乘再除以最大公约数就可以得到最小公倍数:(21*12)/ 3 = 84
python代码实现
接下来我们用python代码来实现这样一道题目:
题目:输入两个正整数,求其最大公约数和最小公倍数。
deffunc(m,n):a=mb=n#默认m>n,若不是,则交换ifm<n:m,n=n,mwhilen!=0:#对m除n取余r=m%nm=nn=rreturnm,(a*b)/m
print("正整数m与n的最大公约数与最小公倍数分别为:",func(12,21))
正整数m与n的最大公约数与最小公倍数分别为: (3, 84.0)
用递归的方式实现
defrec(m,n):#默认m>n,若不是,则交换ifm<n:m,n=n,m#终止条件ifn==0:returnm,(a*b)/m#递归部分returnrec(n,m%n)a=12b=21
print("正整数m与n的最大公约数与最小公倍数分别为:",rec(12,21))
正整数m与n的最大公约数与最小公倍数分别为: (3, 84.0)
Python3 20.辗转相除法
算法分析
1.算法定义为:在有限的步骤内解决数学问题的程序,即为了解决某项工作或某个问题,所需要有限数量的机械性或重复性指令与计算步骤。
2.最大公约数:可整除两个整数的最大整数。
3.用两个数中较大的整数除以较小的数,求得商和余数。
源代码
#coding:gbkNum_1=int(input("请输入一个整数:"))Num_2=int(input("请输入一个整数:"))ifNum_1<Num_2: Tmp_Num=Num_1#是交换而不是赋值 Num_1=Num_2 Num_2=Tmp_NumwhileNum_2!=0: Tmp_Num=Num_1%Num_2 Num_1=Num_2 Num_2=Tmp_Numprint('输出这两个整数的最大公约数:',Num_1)
结果截图
</div> <div class="zixun-tj-product adv-bottom"></div> </div> </div> <div class="prve-next-news">
怎么使用python辗转相除法求最大公约数和最小公倍数的详细内容,希望对您有所帮助,信息来源于网络。