Python基于辗转相除法求解最大公约数的方法示例

时间:2022-04-27 21:59:13

本文实例讲述了Python基于辗转相除法求解最大公约数的方法。分享给大家供大家参考,具体如下:

之前总结过一次高德纳TAOCP中的最大公约数求解,其实课后题中的算法修改要求实现的是辗转相除法求解最大公约数。

这个题目我最初的理解理解错了,自然也没有做出标准答案。现在按照标准答案的解答写一下相应的代码实现:

?
1
2
3
4
5
6
7
8
9
10
11
12
# -*- coding:utf-8 -*-
#! python2
def MaxCommDivisor(m,n):
  while m * n != 0:
    m = m % n
    if m == 0:
      return n
    else:
      n = n % m
      if n == 0:
        return m
print(MaxCommDivisor(55,120))

程序的执行结果:

Python基于辗转相除法求解最大公约数的方法示例

交换一下两个数字的位置,代码如下:

?
1
2
3
4
5
6
7
8
9
10
11
12
# -*- coding:utf-8 -*-
#! python2
def MaxCommDivisor(m,n):
  while m * n != 0:
    m = m % n
    if m == 0:
      return n
    else:
      n = n % m
      if n == 0:
        return m
print(MaxCommDivisor(120,55))

程序的执行结果:

Python基于辗转相除法求解最大公约数的方法示例

题目提示中提到了会降低效率,通过上面的代码来看,效率的损失应该是在除法以及判断上。在此,把之前算法的代码拿过来对比一下:

?
1
2
3
4
5
6
7
8
def CommDevisor(m,n):
  r = m % n
  while r != 0:
    m = n
    n = r
    r = m % n
  return n
print(CommDevisor(120,25))

运行结果:

Python基于辗转相除法求解最大公约数的方法示例

新算法在循环中,多了一个除法以及比较操作。其实,比较的效率还是不错的,但是除法的运算会导致效率的降低。

希望本文所述对大家Python程序设计有所帮助。

原文链接:https://blog.csdn.net/grey_csdn/article/details/77414949