Rumah >pembangunan bahagian belakang >Tutorial Python >Python怎样求得最大公约数
这次给大家带来Python怎样求得最大公约数,Python求得最大公约数的注意事项有哪些,下面就是实战案例,一起来看一下。
之前总结过一次高德纳TAOCP中的最大公约数求解,其实课后题中的算法修改要求实现的是辗转相除法求解最大公约数。
这个题目我最初的理解理解错了,自然也没有做出标准答案。现在按照标准答案的解答写一下相应的代码实现:
# -*- coding:utf-8 -*- #! python2 def MaxCommpisor(m,n): while m * n != 0: m = m % n if m == 0: return n else: n = n % m if n == 0: return m print(MaxCommpisor(55,120))
程序的执行结果:
交换一下两个数字的位置,代码如下:
# -*- coding:utf-8 -*- #! python2 def MaxCommpisor(m,n): while m * n != 0: m = m % n if m == 0: return n else: n = n % m if n == 0: return m print(MaxCommpisor(120,55))
程序的执行结果:
题目提示中提到了会降低效率,通过上面的代码来看,效率的损失应该是在除法以及判断上。在此,把之前算法的代码拿过来对比一下:
def CommDevisor(m,n): r = m % n while r != 0: m = n n = r r = m % n return n print(CommDevisor(120,25))
运行结果:
新算法在循环中,多了一个除法以及比较操作。其实,比较的效率还是不错的,但是除法的运算会导致效率的降低。
相信看了本文案例你已经掌握了方法,更多精彩请关注php中文网其它相关文章!
推荐阅读:
Atas ialah kandungan terperinci Python怎样求得最大公约数. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!